Welches .NET-Wörterbuch unterstützt die Operation "Nächsten Schlüssel finden"?

Question

Ich konvertiere etwas C++ - Code in C# und ruft std :: map :: lower_bound (k) auf, um einen Eintrag in der Map zu finden, dessen Schlüssel gleich oder größer als k ist. Ich sehe jedoch keine Möglichkeit, das gleiche mit .NET SortedDictionary zu tun. Ich vermute, ich könnte eine Abhilfe mit SortedList implementieren, aber leider ist SortedList zu langsam (O (n) zum Einfügen und Löschen von Schlüsseln). Was kann ich tun?

Hinweis: Ich fand eine Abhilfe mit diesem Vorteil von meinem speziellen Szenario nimmt ... Insbesondere meine Schlüssel sind eine dichte Population von ganzen Zahlen bei knapp über 0 beginnen, so habe ich eine Liste <TValue> als meinen Wörterbuch mit der Listenindex, der als der Schlüssel dient, und das Suchen nach einem Schlüssel, der gleich oder größer als k ist, kann in nur wenigen Schleifeniterationen durchgeführt werden. Aber es wäre trotzdem schön, die ursprüngliche Frage beantwortet zu sehen.

Answer 1

Ich habe drei Datenstrukturen in Bezug auf B + -Bäume erstellt, die diese Funktionalität für jeden Datentyp bereitstellen: BList<T>, BDictionary<K,V> and BMultiMap<K,V>. Jede dieser Datenstrukturen stellt FindLowerBound() und FindUpperBound() Methoden zur Verfügung, die wie C++ lower_bound und upper_bound funktionieren.

Answer 2

sagen wir, Sie haben so etwas wie dieses

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

nächsten finden bis K:

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

oder viel schneller:

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

Das Problem ist, dass ein Wörterbuch/Hash-Tabelle wurde entwickelt, um basierend auf einem Eingabewert zu einem eindeutigen Speicherort zu gelangen, so dass Sie eine Datenstruktur benötigen, die entwickelt wurde Platzieren Sie einen Bereich für jeden Wert, den Sie speichern, und aktualisieren Sie gleichzeitig jedes Intervall korrekt

Ich denke, skip lists (oder balancierte Binärbäume) können Ihnen helfen. Obwohl sie in O (n) keine Suchvorgänge durchführen können, können sie logarithmisch und noch schneller als Bäume arbeiten.

Ich weiß, das ist keine richtige Antwort, da ich nicht sagen kann, dass die .NET BCL bereits eine solche Klasse enthält, müssen Sie leider selbst eine implementieren, oder finden Sie eine 3rd Party Assembly, die es für Sie unterstützt. Es scheint jedoch ein schönes Beispiel bei The CodeProject here zu sein.

Answer 5

Es gibt keine binäre Suchbaumsammelimplementierung im Basisframework, daher müssen Sie entweder eine Implementierung erstellen oder eine finden. Wie Sie bereits angemerkt haben, ist SortedList hinsichtlich der Suche am nächsten, ist aber langsamer (aufgrund der zugrunde liegenden Array-Implementierung) zum Einfügen/Löschen.

Answer 6

Ich denke, es gibt einen Fehler in der Frage SortedList Komplexität.

SortedList hat O (log (n)) amortisierte Komplexität für inserting neuen Artikel. Wenn Sie im Voraus wissen, die Kapazität kann in O (Log (n)) im schlimmsten Fall durchgeführt werden.

Answer 7

Sie können den Code versuchen, den ich unten schrieb. es unter Verwendung der binären Suche, also unter der Annahme, dass die Liste/das Array vorsortiert ist.

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

Es dauerte ein paar Monate Arbeit, aber schließlich kann ich zumindest eine Teillösung für dieses Problem bieten ... Ich nenne es die Compact Patricia Trie, ein sortiertes Wörterbuch, das eine „nächste größere finden Angebote Schlüssel "Betrieb.

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

Es ist nur eine Teillösung, da nur bestimmte Arten von Schlüsseln werden unterstützt, nämlich byte[], string und alle primitiven Integer-Typen (Int8..UInt64).Bei der Sortierung von Zeichen wird die Groß-/Kleinschreibung beachtet.

Answer 9

Sie können dies für SortedSet<T> mit folgenden Erweiterungsmethoden:

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; 
    } 
}