Trouver efficacement la clé de dictionnaire la plus proche

J’ai un tas de paires de dates et de valeurs monétaires dans un SortedDictionary , correspondant aux soldes de prêts calculés dans le futur à des dates de composition définies par contrat. Existe-t-il un moyen efficace de trouver une clé de date la plus proche d’une valeur donnée? (Plus précisément, la clé la plus proche inférieure ou égale à la cible). Le but est de stocker uniquement les données aux points où la valeur a changé, mais de répondre efficacement à la question “quel était le solde à la date du x?” pour toute date dans la plage.

Une question similaire a été posée ( Quel dictionnaire .NET prend en charge une opération “Trouver la clé la plus proche”? ) Et la réponse était “non” à l’époque, du moins parmi les personnes qui ont répondu, mais c’était il y a presque 3 ans.

La question Comment trouver un point entre deux clés dans le dictionnaire sortingé présente la solution évidente consistant à itérer naïvement à travers toutes les clés. Je me demande s’il existe une fonction de cadre intégrée permettant de tirer parti du fait que les clés sont déjà indexées et sortingées en mémoire – ou bien d’une classe de collection de cadre intégrée qui se prêterait mieux à ce type de requête.

SortedDictionary étant sortingé sur la clé, vous pouvez créer une liste sortingée de clés avec

 var keys = new List(dictionary.Keys);

puis effectuez efficacement une recherche binary dessus:

 var index = keys.BinarySearch(key);

Comme l’indique la documentation, si index est positif ou égal à zéro, la clé existe. s’il est négatif, alors ~index est l’index où la key serait trouvée si elle existait. Par conséquent, l’index de la clé existante “immédiatement plus petite” est ~index - 1 . Assurez-vous que vous gérez correctement le cas où la key est plus petite que toutes les clés existantes et ~index - 1 == -1 .

Bien entendu, l’approche ci-dessus n’a de sens que si les keys sont construites une fois, puis interrogées à plusieurs resockets; dans la mesure où cela implique une itération sur toute la séquence de clés et une recherche binary en plus de cela, il ne sert à rien d’essayer cela si vous n’effectuez qu’une recherche une fois. Dans ce cas, même une itération naïve serait préférable.

Mettre à jour

Comme le souligne correctement digEmAll, vous pouvez également passer à SortedList afin que la collection Keys implémente IList (ce que SortedDictionary.Keys ne fait pas). Cette interface fournit suffisamment de fonctionnalités pour effectuer manuellement une recherche binary, de sorte que vous pouvez par exemple prendre ce code et en faire une méthode d’extension sur IList .

N’oubliez pas non plus que SortedList est moins performant que SortedDictionary lors de la construction si les éléments ne sont pas insérés dans l’ordre déjà sortingé, bien que dans ce cas particulier, il est fort probable que les dates soient insérées dans un ordre chronologique (sortingé) parfait.

Donc, cela ne répond pas directement à votre question, car vous avez spécifiquement demandé quelque chose d’intégré dans le framework .NET, mais face à un problème similaire, j’ai trouvé la solution suivante qui fonctionnait le mieux, et je voulais la poster ici pour d’autres. chercheurs.

J’ai utilisé le TreeDictionary des collections C5 ( GitHub / NuGet ), qui est une implémentation d’un arbre rouge-noir.

Il dispose de méthodes Predecessor / TryPredecessor et WeakPredessor / TryWeakPredecessor (ainsi que de méthodes similaires pour les successeurs) permettant de rechercher facilement les éléments les plus proches d’une clé.

Je pense que les RangeFrom / RangeTo / RangeFromTo , qui vous permettent de récupérer une plage de paires clé-valeur entre clés, sont plus utiles dans votre cas.

Notez que toutes ces méthodes peuvent également être appliquées à la collection TreeDictionary.Keys , ce qui vous permet également de travailler uniquement avec les clés.

C’est vraiment une mise en œuvre très soignée, et quelque chose comme cela mérite d’être dans la BCL.

Il n’est pas possible de rechercher efficacement la clé la plus proche avec SortedList , SortedDictionary ou tout autre type .NET “intégré”, si vous devez entrelacer des requêtes avec des insertions (à moins que vos données ne soient sortingées à l’avance ou que la collection soit toujours petite). .

Comme je l’ai mentionné dans l’autre question que vous avez mentionnée, j’ai créé trois structures de données liées aux arbres B + qui fournissent une fonctionnalité de recherche de la clé la plus proche pour tout type de données sortingable: BList , BDictionary et BMultiMap . Chacune de ces structures de données fournit des FindLowerBound() et FindUpperBound() qui fonctionnent comme les commandes lower_bound et upper_bound C ++.

  public static DateTime RoundDown(DateTime dateTime) { long remainingTicks = dateTime.Ticks % PeriodLength.Ticks; return dateTime - new TimeSpan(remainingTicks); }