如何从SortedDictionary获取最接近我的键的项目？

Question

目前我正在使用SortedList<T,U>针对特定数字的二进制搜索,如果它不存在,我将获得最接近的下限键项.

我看到插入未分类数据的速度相当慢,我正在做很多事情.

有没有办法做类似的事情SortedDictionary,或者我应该坚持我的SortedList？

Answer 1

SortedList<K, V>插入数据时非常慢,因为<=N每次添加新元素时它都会在内部数组中移动元素.添加的复杂性是O(N).然而,它支持二进制搜索,允许在中找到确切的元素或其邻居O(log N).

平衡二叉树是解决问题的最佳数据结构.您将能够以对数复杂度执行以下操作:

1. 在O(log N)vs. O(N)中添加项目SortedList<K, V>
2. 删除项目 O(log N)
3. 搜索项目或其最近的 O(log N)

在二叉树中查找元素或其最近的下界很简单:

1. 从根到孩子垂直穿过树,以便找到你的钥匙.如果key <node,则转到left child,否则转到right.
2. 如果找到钥匙,请返回
3. 如果未找到密钥,则最近的左侧父级将是您要查找的密钥(最近的下限)
4. 如果没有左父母,只需占用最后一个访问过的节点,它就是树中的最小节点.

有很多文章描述了如何实现二叉树.不过我将使用一种黑客重用.NET Framework集合:)

现在,我要告诉你SortedSet<T>哪个本身就是红黑树.它有一个缺点,它无法快速找到最近的节点.但我们知道树中的搜索算法(在1中描述)并且它在SortedSet<T>.Contains方法中实现(在底部反编译*).现在,我们可以使用自定义比较器在遍历期间捕获从根到最后访问节点的所有节点.之后我们可以使用上面的算法找到最近的下界节点:

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>.

怎么样SortedDictionary<K, V>？SortedSet<T>除了一件事之外几乎相同:每个键都有一个值.我希望你能够做同样的事情SortedDictionary<K, V>.

*反编译SortedSet<T>.Contains方法:

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