如何从SortedDictionary获取最接近我的钥匙的物品？ [英] How to get the closest item to my key from a SortedDictionary?

问题描述

当前，我在 SortedList< T，U> 上使用二进制搜索来查找特定数字，如果不存在，我会得到最接近的而是绑定键项。

Currently I'm using a binary search over a SortedList<T,U> for a specific number, and if it doesn't exist I get the closest lower-bound key-item instead.

我看到插入大量未排序的数据，我正在这样做。

I saw that it was rather slow in inserting unsorted data which I'm doing a lot of.

有没有办法做类似的事情使用 SortedDictionary ，还是我应该坚持我的 SortedList ？

Is there a way to do something similar with the SortedDictionary, or should I just stick to my SortedList?

推荐答案

SortedList< K，V> 在插入数据时确实很慢，因为它移位<每次添加新元素时，内部数组中的= N 个元素。加法的复杂度为 O（N）。不过，它支持二进制搜索，该搜索允许在 O（log N）中找到确切的元素或其邻居。

SortedList<K, V> is really slow when inserting data as it shifts <=N elements in internal array each time a new element is added. The complexity of addition is O(N). Nevertheless it supports binary search which allows to find exact element or its neighbors in O(log N).

平衡二进制树是解决问题的最佳数据结构。
您将可以执行对数复杂性的以下操作：

Balanced binary tree is the best data structure to solve your problem. You'll be able to to do the following operations w/ logarithmic complexity:

1. 在 O（log N）与 SortedList< K，V> O（N） c>


2. 删除 O（log N）


3. 搜索项或其最近的项在 O（log N）

1. Add item in O(log N) vs. O(N) in SortedList<K, V>
2. Remove item in O(log N)
3. Search item or its nearest in O(log N)

中查找元素或其最近的下限-在二叉树中绑定很简单：

Looking for element or its nearest lower-bound in binary tree is simple:

1. 从树根到子树垂直穿过树，以查找密钥。如果键<节点，然后转到左侧的子节点，否则转到右侧的子节点。


2. 如果找到了密钥，则返回


3. 如果未找到密钥，则最靠近左侧父级将是您要查找的父级（最近的下界）


4. 如果没有左父级，只需取最后一个访问的节点，它是树中的最小节点。
li>

1. Go vertically through the tree from root to child in order to find your key. If key < node, then go to left child, otherwise to the right one.
2. If you found the key, return
3. If key not found, nearest left parent will be the one you are looking for (nearest lower-bound)
4. If there is no left parents, just take the last visited node, it is minimal node in the tree.

有许多文章描述了如何实现二叉树。尽管如此，我还是要使用一种技巧来重用.NET Framework集合：）

There are many articles describing how to implement binary tree. Nevertheless I'm going to reuse .NET Framework collection using a kind of hack :)

现在，我要向您介绍 SortedSet< T> 本身是红黑树。它有一个缺点，它无法快速找到最近的节点。但是我们知道在树中进行搜索的算法（在1中进行了描述），并且是在 SortedSet< T>中实现的。包含方法（在底部*反编译）。现在，我们可以使用自定义比较器捕获遍历过程中从根到最后访问的节点的所有节点。之后，我们可以使用上面的算法找到最近的下界节点：

Now, I'm gonna present to you SortedSet<T> which itself is red-black tree. It has one drawback, it has no ability to find nearest nodes quickly. But we know the algorithm of search in tree (it's described in 1.) and it is implemented in SortedSet<T>.Contains method (decompiled at the bottom*). Now we can capture all nodes from root to the last visited node during traversal using our custom comparer. After that we can find nearest lower-bound node using algorithm above:

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

您会发现查找最近的节点所花费的时间不比平时多搜索，即 O（log N）。因此，这是解决您问题的最快解决方案。该集合的查找速度与 SortedList< K，V> 一样快，与 SortedSet< T> 一样快。

You see that finding nearest node takes no more than usual search, i.e. O(log N). So, this is the fastest solution for your problem. This collection is as fast as SortedList<K, V> in finding nearest and is as fast as SortedSet<T> in addition.

SortedDictionary< K，V> 呢？它与 SortedSet< T> 几乎相同，不同之处在于：每个键都有一个值。希望您能够对 SortedDictionary< K，V> 进行同样的操作。

What about SortedDictionary<K, V>? It is almost the same as SortedSet<T> except one thing: each key has a value. I hope you will be able to do the same with SortedDictionary<K, V>.

*反编译的 SortedSet< T>。包含方法：

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

这篇关于如何从SortedDictionary获取最接近我的钥匙的物品？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！