c# - 如何从 SortedDictionary 中获取最接近我的键的项目？

Question

目前我正在对 SortedList<T,U> 使用二进制搜索对于一个特定的数字，如果它不存在，我会得到最接近的下限键项。

我看到它在 inserting unsorted data 中相当慢我正在做很多事情。

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

Answer 1

SortedList<K, V>在移动时插入数据真的很慢 <=N每次添加新元素时内部数组中的元素。加法的复杂度是O(N) .尽管如此，它支持二进制搜索，允许在 O(log N) 中找到确切的元素或其邻居。 .

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

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

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

1. 从根到子垂直遍历树以找到您的 key 。如果键 < 节点，则转到左子节点，否则转到右子节点。
2. 如果找到 key ，返回
3. 如果找不到键，最近的左父级将是您正在寻找的那个(最近的下界)
4. 如果没有左父节点，只取最后访问过的节点，它是树中的最小节点。

有很多文章描述了如何实现二叉树。不过，我将使用一种 hack 来重用 .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;
}