Efficace de trouver le plus proche de clé de dictionnaire

J'ai un tas de paires de dates et valeurs monétaires dans un SortedDictionary<DateTime, decimal>, correspondant à des soldes de prêts calculé dans l'avenir, au contrat défini par compoundage dates. Est-il un moyen efficace pour trouver une date clé qui est la plus proche à une valeur donnée? (Plus précisément, le plus proche de la clé inférieure ou égale à la cible). Le point est de ne stocker que les données lorsque la valeur a changé, mais efficace de répondre à la question "quel a été le bilan sur x date?" pour n'importe quelle date dans la gamme.

Une question semblable a été posée ( Qu'est-ce .NET dictionnaire prend en charge une "trouver le plus proche de la clé" opération? ) et la réponse était "non" à l'époque, au moins de la population qui a répondu, mais c'était presque 3 ans.

La question Comment trouver le point entre les deux clés de tri dictionnaire présente la solution la plus évidente de la naïveté de itérer sur toutes les touches. Je me demande si dans le cadre de la fonction existe pour tirer avantage du fait que les touches sont déjà indexés et classés dans la mémoire -- ou bien un construit-dans le Cadre de la collection de la catégorie qui se prête mieux à ce genre de requête.

  • Mais les clés d'un dictionnaire ne sont PAS triés dans la mémoire. C'est pourquoi vous ne pouvez pas faire une "le plus proche" ou de se "inférieur ou égal à" sur un dictionnaire.
  • La question liée a mentionner au sujet de SortedList<K, V> structure. Je voudrais aller avec qui.
InformationsquelleAutor Joshua Honig | 2012-09-13
  1. 23

    Depuis SortedDictionary est trié sur la clé, vous pouvez créer une liste triée des touches avec

    var keys = new List<DateTime>(dictionary.Keys);

    puis effectuer efficacement recherche binaire sur elle:

    var index = keys.BinarySearch(key);

    Que dit la documentation, si index est positif ou nul alors la clé existe; si elle est négative, alors ~index est l'index où key serait trouvé à la si elle existait. Par conséquent, l'indice de la "immédiatement petits" clé existante est ~index - 1. Assurez-vous de gérer correctement le cas limite où key est plus petite que toutes les clés existantes et ~index - 1 == -1.

    Bien sûr, l'approche ci-dessus vraiment n'a de sens que si keys est construit qu'une seule fois et ensuite interrogé à plusieurs reprises; car il implique une itération sur l'ensemble de la séquence de touches et de faire une recherche binaire sur le dessus de qui il n'y a aucun intérêt à essayer cette option si vous envisagez de ne rechercher qu'une seule fois. Dans ce cas, même naïf itération serait mieux.

    Mise à jour

    Comme digEmAll correctement points, on peut aussi passer à la SortedList<DateTime, decimal> de sorte que le Touches collection met en œuvre IList<T> (qui SortedDictionary.Les touches qui ne fonctionne pas). Cette interface fournit suffisamment de fonctionnalités pour effectuer une recherche binaire sur manuellement, de sorte que vous pouvez prendre par exemple ce code et d'en faire une méthode d'extension sur IList<T>.

    Vous devez également garder à l'esprit que SortedList effectue pire que SortedDictionary lors de la construction si les articles ne sont pas insérés dans le déjà-de l'ordre de tri, bien que dans ce cas particulier, il est très probable que les dates sont insérées dans l'ordre chronologique (tri) de l'ordre qui serait parfait.

    • OP pourrait aussi passer à la SortedList<> (pour éviter la conversion d'une Liste<>) et ensuite utiliser cette méthode --> LINK
    • C'est une très bonne suggestion, d'autant plus que probable que la collection est construite sur un très SortedListconviviale. Je l'ai insérée dans la réponse.
    • Parfait. Il est exact que les listes seront remplies dans l'ordre, mais être interrogé à de nombreuses reprises et pas dans l'ordre les différentes permutations possibles des prêts et des contrats sont calculés.
    InformationsquelleAutor Jon
  2. 8

    Donc, ce n'est pas directement répondre à votre question, parce que vous avez spécifiquement demandé quelque chose, intégré à la .NET framework, mais face à un problème similaire, j'ai trouvé la solution suivante pour travailler mieux, et je voulais le poster ici pour d'autres chercheurs.

    J'ai utilisé le TreeDictionary<K, V> de la C5 Collections (GitHub/NuGet), qui est une implémentation d'un rouge-noir arbre.

    Il a Predecessor/TryPredecessor et WeakPredessor/TryWeakPredecessor méthodes (ainsi que des méthodes similaires pour successeurs), afin de trouver facilement le plus proche des éléments à une clé.

    Plus utile dans votre cas, je pense, est le RangeFrom/RangeTo/RangeFromTo méthodes qui vous permettent de récupérer une série de clé-valeur entre les paires de clés.

    Noter que toutes ces méthodes peuvent également être appliquées à la TreeDictionary<K, V>.Keys collection, qui vous permettent de travailler uniquement avec les touches et.

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

    • Utilisation => Prédécesseur , (diff1), (Valeur) , (diff2), Successeur => si diff1 < diff2 ensuite utiliser Prédécesseur méthode.
    InformationsquelleAutor Riko
  3. 1

    Il n'est pas possible efficace de trouver le plus proche de clé avec SortedList, SortedDictionary ou tout autre "built-in" .Type de NET, si vous avez besoin d'intercaler des requêtes avec des inserts (à moins que vos données arrivent pré-triés, ou la collection est toujours petit).

    Comme je l'ai dit sur l'autre question que vous l'avez mentionné, j'ai créé trois structures de données liées à B+ arbres qui fournissent trouver-plus-proche-clé fonctionnalités pour n'importe quel sortable type de données: BList<T>, BDictionary<K,V> et BMultiMap<K,V>. Chacune de ces structures de données fournissent FindLowerBound() et FindUpperBound() méthodes qui fonctionnent comme le C++ lower_bound et upper_bound.

    • Très jolie mise en œuvre, puis-je prolonger SparseAList à l'appui de qword la taille de l'index? Il serait très bien Si il n'y avait long version de ce.
    • Hmm, il semble que toutes les interfaces sont conçues pour 32-bits - mais si vous souhaitez fork sur GitHub et de faire une version 64 bits, n'hésitez pas. Malheureusement, je ne pense pas qu'une seule version est assez, que 64-bit indices permettrait d'accroître l'utilisation de la mémoire jusqu'à 50%, et non tous les clients voudraient que. Le plus gros problème est que tous ALists sont dérivées à partir de AListBase, qui utilise AListInner/AListInnerBase, qui contient 32 bits d'index. Donc il semble que la version 64 bits devraient éliminer la classe de base et de reproduire l'ensemble de son code.
    • Remarque: vous pouvez utiliser LeMP pour éviter physiquement reproduisant le code (donc la duplication de tous les bogues restants). Au lieu de cela, vous pouvez utiliser using d'introduire de nouveaux noms pour les index (using index = int; using uindex = uint) et ensuite utiliser LeMP faire trouver et remplacer des opérations sur la version 32 bits du code pour générer une version 64 bits. Si vous créez un question nous pouvons parler plus sur la façon dont cette approche pourrait fonctionner. Remarque: LeMP et SparseAList sont définies dans la même repo.
    InformationsquelleAutor Qwertie
  4. 0
        public static DateTime RoundDown(DateTime dateTime)
    {
        long remainingTicks = dateTime.Ticks % PeriodLength.Ticks;
        return dateTime - new TimeSpan(remainingTicks);
    }
    • Vous devez fournir quelques explications sur ce que votre code est en train de faire. Ne vous contentez pas de code postal.
    • Je pensais que c'était évident. Utilisé arrondie DateTimes comme vos clés, et d'utiliser la même méthode pour look-ups. PeriodLength peut être une semaine, un jour, une heure, 5 minutes, ou que ce soit régulier longueur de la période dont vous avez besoin. Si PeriodLength n'est pas une constante de l'application, plus génériques, la solution serait d'accepter periodLength en tant que paramètre.
    InformationsquelleAutor ChrisG65