¿Cómo obtener el elemento más cercano a mi clave desde SortedDictionary?

Question

Actualmente estoy usando una búsqueda binaria sobre un SortedList<T,U> para un número específico, y si no existe, obtengo el elemento clave de enlace inferior más cercano en su lugar.

Vi que era bastante lento en inserting unsorted data que estoy haciendo mucho.

¿Hay alguna manera de hacer algo similar con SortedDictionary, o debería seguir con mi SortedList?

Answer 1

SortedList<K, V> es muy lento al insertar datos a medida que cambia los elementos <=N en la matriz interna cada vez que se agrega un nuevo elemento. La complejidad de la suma es O(N). Sin embargo, es compatible con la búsqueda binaria que permite encontrar el elemento exacto o sus vecinos en O(log N).

El árbol binario equilibrado es la mejor estructura de datos para resolver su problema. Usted será capaz de realizar las siguientes operaciones w/complejidad logarítmica:

1. Añadir elemento en O(log N) vs O(N) en SortedList<K, V>
2. elemento Quitar en el punto O(log N)
3. búsqueda o su más cercano en O(log N)

Buscando elemento o su más cercana con destino a menor en árbol binario es simple:

1. Vaya verticalmente a través del árbol de raíz a hijo para encontrar su clave. Si el nodo clave es <, vaya al secundario izquierdo, de lo contrario a la derecha.
2. Si has encontrado la clave, volver
3. Si no encontró clave, padre que ha quedado más cerca es el que usted está buscando (la más cercana límite inferior)
4. Si no hay padres izquierda, acaba de tomar la última visita nodo, es un nodo mínimo en el árbol.

Hay muchos artículos que describen cómo implementar el árbol binario. Sin embargo, voy a reutilizar la colección .NET Framework utilizando una especie de truco :)

Ahora, voy a presentarles SortedSet<T> que en sí es un árbol rojo-negro. Tiene un inconveniente, no tiene la capacidad de encontrar rápidamente los nodos más cercanos. Pero conocemos el algoritmo de búsqueda en árbol (se describe en 1.) y se implementa en el método SortedSet<T>.Contains (descompilado en la parte inferior *). Ahora podemos capturar todos los nodos desde la raíz hasta el último nodo visitado durante el recorrido usando nuestro comparador personalizado. Después de que podamos encontrar más próximo nodo de límite inferior que utilizan algoritmo anterior:

public class LowerBoundSortedSet<T> : SortedSet<T> { 

    private ComparerDecorator<T> _comparerDecorator; 

    private class ComparerDecorator<T> : IComparer<T> { 

     private IComparer<T> _comparer; 

     public T LowerBound { get; private set; } 

     private bool _reset = true; 

     public void Reset() 
     { 
      _reset = true; 
     } 

     public ComparerDecorator(IComparer<T> comparer) 
     { 
      _comparer = comparer; 
     } 

     public int Compare(T x, T y) 
     { 
      int num = _comparer.Compare(x, y); 
      if (_reset) 
      { 
       LowerBound = y; 
      } 
      if (num >= 0) 
      { 
       LowerBound = y; 
       _reset = false; 
      } 
      return num; 
     } 
    } 

    public LowerBoundSortedSet() 
     : this(Comparer<T>.Default) {} 

    public LowerBoundSortedSet(IComparer<T> comparer) 
     : base(new ComparerDecorator<T>(comparer)) { 
     _comparerDecorator = (ComparerDecorator<T>)this.Comparer; 
    } 

    public T FindLowerBound(T key) 
    { 
     _comparerDecorator.Reset(); 
     this.Contains<T>(key); 
     return _comparerDecorator.LowerBound; 
    } 
} 

se ve que la búsqueda de nodo más cercano no toma más de búsqueda habitual, es decir O(log N). Entonces, esta es la solución más rápida para su problema. Esta colección es tan rápida como SortedList<K, V> en encontrar más cercana y es tan rápida como SortedSet<T> además.

¿Qué hay de SortedDictionary<K, V>? Es casi lo mismo que SortedSet<T> excepto una cosa: cada tecla tiene un valor. Espero que puedas hacer lo mismo con SortedDictionary<K, V>.

* decompilados SortedSet<T>.Contains método:

public virtual bool Contains(T item) 
{ 
    return this.FindNode(item) != null; 
} 

internal virtual SortedSet<T>.Node FindNode(T item) 
{ 
    for (SortedSet<T>.Node node = this.root; node != null; { 
    int num; 
    node = num < 0 ? node.Left : node.Right; 
    } 
) 
    { 
    num = this.comparer.Compare(item, node.Item); 
    if (num == 0) 
     return node; 
    } 
    return (SortedSet<T>.Node) null; 
}