Quel dictionnaire .NET prend en charge une opération "Trouver la clé la plus proche"?

Question

Je convertis du code C++ en C# et appelle std :: map :: lower_bound (k) pour trouver une entrée dans la carte dont la clé est égale ou supérieure à k. Cependant, je ne vois aucun moyen de faire la même chose avec SortedDictionary de .NET. Je suppose que je pourrais mettre en œuvre une solution de contournement en utilisant SortedList, mais malheureusement, SortedList est trop lent (O (n) pour l'insertion et la suppression de clés). Que puis-je faire?

Note: J'ai trouvé une solution de contournement qui tire parti de mon scénario particulier ... Plus précisément, mes clés sont une population dense d'entiers commençant à un peu plus de 0, donc j'ai utilisé un <TValue> comme mon dictionnaire avec le L'index de liste servant de clé, et la recherche d'une clé égale ou supérieure à k ne peut être effectuée que dans quelques itérations de boucle. Mais il serait toujours agréable de voir la réponse à la question initiale.

Answer 1

J'ai créé trois structures de données liées aux arbres B + qui fournissent cette fonctionnalité pour n'importe quel type de données: BList<T>, BDictionary<K,V> and BMultiMap<K,V>. Chacune de ces structures de données fournit des méthodes FindLowerBound() et FindUpperBound() qui fonctionnent comme les lower_bound et upper_bound de C++.

Answer 2

disons que vous avez quelque chose comme ça

Dictionary<string, int> dict = ... 
\\and you have 
k \\- is the key to find or if it is not than at least greater 
\\ you write 

var entry = dict.Where(o => o.key >= k).First(); 

Answer 3

trouver le plus proche de K:

dict.Keys.Where(i => i >= K).OrderBy(i => i).First(); 

ou beaucoup plus rapide:

public int? GetNearestKey(dict, K) 
{ 
    int? lowerK = null; 
    foreach (int key in dict.Keys) 
    { 
     if (key == K) 
     { 
      lowerK = K; 
      break; 
     } 
     else if (key >= K && (!lowerK.HasValue || key < lowerK)) 
     { 
      lowerK = key; 
     } 
    } 
    return lowerK; 
} 

Answer 4

Le problème est qu'un dictionnaire/table de hachage est conçu pour arriver à un emplacement mémoire unique basé sur une valeur d'entrée, vous aurez donc besoin d'une structure de données conçue pour adapter une plage liée à chaque valeur que vous stockez, et en même temps mettre à jour chaque intervalle correctement

Je pense que skip lists (ou arbres binaires équilibrés) peut vous aider. Bien qu'ils ne puissent pas effectuer de recherche dans O (n), ils peuvent faire logarithmiquement et encore plus rapidement que les arbres.

Je sais que ce n'est pas une bonne réponse car je ne peux pas dire que le .NET BCL contient déjà une telle classe, vous devrez malheureusement en implémenter vous-même, ou trouver un assembly tiers qui le supporte pour vous. Il semble y avoir un bon exemple à The CodeProject here, cependant.

Answer 5

Il n'y a pas d'implémentation de collection d'arbre de recherche binaire dans l'infrastructure de base, vous devrez donc en créer un ou trouver une implémentation. Comme vous l'avez noté, SortedList est la plus proche en termes de recherche, mais elle est plus lente (en raison de sa mise en œuvre sous-jacente) pour l'insertion/la suppression.

Answer 6

Je pense qu'il y a une erreur dans la question sur SortedList complexité.

SortedList a O (log (n)) complexité amortie pour inserting nouvel article. Si vous connaissez à l'avance la capacité, vous pouvez le faire dans O (Log (n)) dans le pire des cas.

Answer 7

Vous pouvez essayer le code que j'ai écrit ci-dessous. en utilisant la recherche binaire, donc en supposant que le list/array est pré-trié.

public static class ListExtensions 
{ 
    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer) 
    { 
     return GetAtMostIndex(list, value, comparer, 0, list.Count); 
    } 

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer) 
    { 
     return GetAtLeastIndex(list, value, comparer, 0, list.Count); 
    } 

    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count) 
    { 
     if (count == 0) 
     { 
      return -1; 
     } 

     int startIndex = index; 
     int endIndex = index + count - 1; 
     int middleIndex = 0; 
     int compareResult = -1; 

     while (startIndex < endIndex) 
     { 
      middleIndex = (startIndex + endIndex) >> 1; ///2 
      compareResult = comparer.Invoke(list[middleIndex], value); 

      if (compareResult > 0) 
      { 
       endIndex = middleIndex - 1; 
      } 
      else if (compareResult < 0) 
      { 
       startIndex = middleIndex + 1; 
      } 
      else 
      { 
       return middleIndex; 
      } 
     } 

     if (startIndex == endIndex) 
     { 
      compareResult = comparer.Invoke(list[startIndex], value); 

      if (compareResult <= 0) 
      { 
       return startIndex; 
      } 
      else 
      { 
       int returnIndex = startIndex - 1; 

       if (returnIndex < index) 
       { 
        return -1; 
       } 
       else 
       { 
        return returnIndex; 
       } 
      } 
     } 
     else 
     { 
      //todo: test 
      return startIndex - 1; 
     } 
    } 

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count) 
    { 
     if (count == 0) 
     { 
      return -1; 
     } 

     int startIndex = index; 
     int endIndex = index + count - 1; 
     int middleIndex = 0; 
     int compareResult = -1; 

     while (startIndex < endIndex) 
     { 
      middleIndex = (startIndex + endIndex) >> 1; ///2 
      compareResult = comparer.Invoke(list[middleIndex], value); 

      if (compareResult > 0) 
      { 
       endIndex = middleIndex - 1; 
      } 
      else if (compareResult < 0) 
      { 
       startIndex = middleIndex + 1; 
      } 
      else 
      { 
       return middleIndex; 
      } 
     } 

     if (startIndex == endIndex) 
     { 
      compareResult = comparer.Invoke(list[startIndex], value); 

      if (compareResult >= 0) 
      { 
       return startIndex; 
      } 
      else 
      { 
       int returnIndex = startIndex + 1; 

       if (returnIndex >= index + count) 
       { 
        return -1; 
       } 
       else 
       { 
        return returnIndex; 
       } 
      } 
     } 
     else 
     { 
      return endIndex + 1; 
     } 
    } 
} 

Answer 8

Il a fallu deux mois de travail, mais enfin je peux offrir au moins une solution partielle à ce problème ... Je l'appelle le Compact Patricia Trie, un dictionnaire qui offre une Sorted « Suivant plus clé "opération.

http://www.codeproject.com/KB/recipes/cptrie.aspx

Il est seulement une solution partielle puisque seuls certains types de clés sont pris en charge, à savoir byte[], string, et tous les types entiers primitifs (Int8..UInt64).De plus, le tri des chaînes est sensible à la casse.

Answer 9

Vous pouvez le faire pour SortedSet<T> avec des méthodes d'extension suivantes:

public static class SortedSetExtensions 
{ 
    public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first) 
    { 
     if(set.Count == 0) 
     { 
      first = default(T); 
      return false; 
     } 

     var minimum = set.Min; 

     if(set.Comparer.Compare(minimum, value) > 0) 
     { 
      first = default(T); 
      return false; 
     } 

     first = set.GetViewBetween(minimum, value).Max; 
     return true; 
    } 

    public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first) 
    { 
     if (set.Count == 0) 
     { 
      first = default(T); 
      return false; 
     } 

     var maximum = set.Max; 

     if (set.Comparer.Compare(maximum, value) < 0) 
     { 
      first = default(T); 
      return false; 
     } 

     first = set.GetViewBetween(value, maximum).Min; 
     return true; 
    } 
}