Quale dizionario .NET supporta un'operazione "trova la chiave più vicina"?

Question

Sto convertendo un codice C++ in C# e chiama std :: map :: lower_bound (k) per trovare una voce nella mappa la cui chiave è uguale o maggiore di k. Tuttavia, non vedo alcun modo per fare la stessa cosa con SortedDictionary di .NET. Sospetto di poter implementare una soluzione alternativa utilizzando SortedList, ma purtroppo SortedList è troppo lento (O (n) per l'inserimento e l'eliminazione delle chiavi). Cosa posso fare?

Nota: ho trovato una soluzione utilizzando che si avvale della mia particolare scenario ... In particolare, le chiavi sono una densa popolazione di interi a partire da poco più di 0, quindi ho usato un elenco <TValue> come il mio dizionario con la elenca l'indice che funge da chiave e la ricerca di una chiave uguale o maggiore di k può essere eseguita solo in alcune iterazioni di ciclo. Ma sarebbe comunque bello vedere la risposta alla domanda originale.

Answer 1

Ho creato tre strutture dati relative agli alberi B + che forniscono questa funzionalità per qualsiasi tipo di dati: BList<T>, BDictionary<K,V> and BMultiMap<K,V>. Ognuna di queste strutture dati fornisce i metodi FindLowerBound() e FindUpperBound() che funzionano come C++ lower_bound e upper_bound.

Answer 2

diciamo che avete qualcosa di simile

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

trovare più vicino a K:

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

o molto più veloce:

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

Il problema è che un dizionario/tabella hash è progettato per arrivare a una posizione di memoria unica basata su un valore di input, quindi avrai bisogno di una struttura dati progettata per adattare un intervallo relativo a ciascun valore memorizzato e allo stesso tempo aggiornare ogni intervallo correttamente

Penso che skip lists (o alberi binari bilanciati) possano aiutarti. Sebbene non possano eseguire ricerche in O (n), possono fare logaritmicamente e comunque più velocemente degli alberi.

So che questa non è una risposta corretta poiché non posso dire che .NET BCL contenga già una classe di questo tipo, sfortunatamente dovrai implementarne una da solo o trovare un assembly di terze parti che lo supporti per te. Sembra che ci sia un bell'esempio su The CodeProject here, però.

Answer 5

Non esiste un'implementazione di raccolta dell'albero di ricerca binario nel framework di base, quindi è necessario crearne uno o trovare un'implementazione. Come hai notato, SortedList è il più vicino in termini di ricerca, ma è più lento (a causa dell'implementazione dell'array sottostante) per l'inserimento/eliminazione.

Answer 6

Penso che ci sia un errore nella domanda sulla complessità SortedList.

SortedList ha O (log (n)) complessità ammortizzata per inserting nuovo elemento. Se si conosce in anticipo la capacità può essere eseguita in O (Log (n)) nel peggiore dei casi.

Answer 7

Puoi provare il codice che ho scritto qui sotto. usando la ricerca binaria, assumendo quindi che la lista/matrice sia preordinata.

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

Ci sono voluti un paio di mesi di lavoro, ma alla fine posso offrire almeno una soluzione parziale a questo problema ... Io lo chiamo il Compact trie patricia, un dizionario ordinato che offre un "Trova successivo più grande chiave "operazione.

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

E 'solo una soluzione parziale poiché solo alcuni tipi di chiavi sono supportati, cioè byte[], string, e tutti i tipi interi primitivi (Int8..UInt64).Inoltre, l'ordinamento delle stringhe fa distinzione tra maiuscole e minuscole.

Answer 9

Si può fare questo per SortedSet<T> con i seguenti metodi di estensione:

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