8

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

我看到插入未排序的数据相当慢，我经常这样做。

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

4

1 回答 1

14

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. 如果找到钥匙，请返回
  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;
}
于 2012-07-27T21:45:58.913 回答