Jak zdobyć najbliższy przedmiot do mojego klucza z SortedDictionary?

Question

Obecnie używam wyszukiwania binarnego nad numerem SortedList<T,U>, a jeśli nie istnieje, otrzymuję zamiast niego najbliższy klucz dolny.

Zobaczyłem, że było dość powolne w inserting unsorted data, które robię dużo.

Czy istnieje sposób, aby zrobić coś podobnego z SortedDictionary, czy powinienem po prostu trzymać się mojego SortedList?

Answer 1

SortedList<K, V> jest bardzo powolny podczas wstawiania danych, gdy przesuwa elementy <=N w wewnętrznej tablicy za każdym razem, gdy dodawany jest nowy element. Złożoność dodawania to O(N). Niemniej jednak obsługuje wyszukiwanie binarne, które pozwala znaleźć dokładny element lub jego sąsiadów w O(log N).

Zbalansowane drzewo binarne jest najlepszą strukturą danych do rozwiązania problemu. Będziesz w stanie wykonać następujące czynności w/logarytmicznej złożoności:

1. Dodaj pozycja w O(log N) vs. O(N) w SortedList<K, V>
2. Usuń pozycję w punkcie O(log N)
3. wyszukiwania lub jego najbliższy w O(log N)

Poszukiwanie elementu lub jego najbliższej dolnej granicy w drzewie binarnym jest proste:

1. Przejdź pionowo przez drzewo od korzenia do dziecka, aby znaleźć klucz. Jeśli kluczowym węzłem jest <, przejdź do lewego elementu potomnego, w przeciwnym razie do prawego.
2. Jeśli znalazłeś klucz, powrót
3. Jeśli nie znaleziono klucza, najbliższa lewej rodzic będzie jeden szukasz (najbliższy niższy-bound)
4. Jeśli nie ma lewej rodzice, po prostu wziąć ostatni odwiedził węzeł, jest to minimalny węzeł w drzewie.

Istnieje wiele artykułów opisujących, jak zaimplementować drzewo binarne. Niemniej jednak zamierzam ponownie użyć kolekcji .NET Framework przy użyciu pewnego rodzaju hackowania :)

Teraz przedstawię wam SortedSet<T>, który sam jest czerwono-czarnym drzewem. Ma jedną wadę, nie ma możliwości szybkiego znalezienia najbliższych węzłów. Ale znamy algorytm wyszukiwania w drzewie (jest opisany w 1.) i jest on implementowany w metodzie SortedSet<T>.Contains (dekompilowany na dole *). Teraz możemy przechwycić wszystkie węzły z katalogu głównego do ostatnio odwiedzanego węzła podczas traversal za pomocą naszego niestandardowego porównywalnika. Po tym możemy znaleźć najbliższy niższy związany węzeł przy użyciu algorytmu powyżej:

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

Widać, że znalezienie najbliższego węzła nie trwa dłużej niż zwykle wyszukiwania, tj O(log N). Jest to najszybsze rozwiązanie Twojego problemu. Ta kolekcja jest równie szybka jak SortedList<K, V> w znalezieniu najbliższego i jest równie szybka jak SortedSet<T>.

Co z numerem SortedDictionary<K, V>? Jest prawie taki sam jak SortedSet<T>, z wyjątkiem jednego: każdy klucz ma wartość. Mam nadzieję, że będziesz w stanie zrobić to samo z SortedDictionary<K, V>.

* dekompilowana SortedSet<T>.Contains metoda:

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