¿Qué diccionario .NET admite una operación de "encontrar la clave más cercana"?

Question

Estoy convirtiendo algunos códigos C++ a C# y llama a std :: map :: lower_bound (k) para encontrar una entrada en el mapa cuya clave sea igual o mayor que k. Sin embargo, no veo ninguna forma de hacer lo mismo con SortedDictionary de .NET. Sospecho que podría implementar una solución con SortedList, pero lamentablemente SortedList es demasiado lento (O (n) para insertar y eliminar claves). ¿Que puedo hacer?

Nota: Encontré una solución que aprovecha mi situación particular ... Específicamente, mis claves son una población densa de enteros comenzando en un poco más de 0, así que utilicé una lista <TValue> como mi diccionario con el el índice de lista que sirve como clave, y la búsqueda de una clave igual o mayor que k se puede hacer en solo unas pocas iteraciones de bucle. Pero aún sería bueno ver respondida la pregunta original.

Answer 1

Creé tres estructuras de datos relacionadas con árboles B + que proporcionan esta funcionalidad para cualquier tipo de datos: BList<T>, BDictionary<K,V> and BMultiMap<K,V>. Cada una de estas estructuras de datos proporciona FindLowerBound() y FindUpperBound() métodos que funcionan como los de C++ lower_bound y upper_bound.

Answer 2

digamos que usted tiene algo como esto

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

encuentra más cercana a K:

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

o mucho más rápido:

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

El problema es que un diccionario/tabla hash está diseñado para llegar a una ubicación de memoria única basada en un valor de entrada, por lo que necesitará una estructura de datos diseñada para acomodar un rango relacionado con cada valor que almacena, y al mismo tiempo actualizar cada intervalo correctamente

Creo que skip lists (o árboles binarios balanceados) pueden ayudarlo. Aunque no pueden realizar búsquedas en O (n), pueden hacerlo logarítmicamente y aún más rápido que los árboles.

Sé que esta no es una respuesta adecuada, ya que no puedo decir que el .NET BCL ya contenga una clase de este tipo, desafortunadamente tendrá que implementar una usted mismo o buscar un ensamblado de terceros que la admita. Sin embargo, parece haber un buen ejemplo en The CodeProject here.

Answer 5

No existe una implementación de colección de árbol de búsqueda binaria en el marco base, por lo que tendrá que crear una o encontrar una implementación. Como ha señalado, SortedList es el más cercano en términos de búsqueda, pero es más lento (debido a su implementación de matriz subyacente) para la inserción/eliminación.

Answer 6

Creo que hay un error en la pregunta sobre la complejidad SortedList.

SortedList tiene O (log (n)) complejidad amortizada para inserting artículo nuevo. Si sabe de antemano la capacidad, puede hacerlo en O (Log (n)) en el peor de los casos.

Answer 7

Puede probar el código que escribí a continuación. usando búsqueda binaria, por lo tanto, suponiendo que la lista/matriz está preordenada.

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

Me tomó un par de meses de trabajo, pero al final me puede ofrecer al menos una solución parcial a este problema ... Yo lo llamo el compacto Patricia Trie, un diccionario ordenada que ofrece una "Buscar siguiente más grande clave "operación.

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

es sólo una solución parcial, ya que sólo ciertos tipos de claves son compatibles, es decir, byte[], string, y todos los tipos de enteros primitivos (Int8..UInt64).Además, la clasificación de cadenas distingue entre mayúsculas y minúsculas.

Answer 9

Puede hacer esto para SortedSet<T> con los métodos de extensión siguientes:

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