在给定索引下插入、删除和重新排列的高效C#数据结构

Question

我在C#中寻找一种高效的数据结构，它允许我保留一个项目列表(由用户订购)，而不需要重复。

我指的是用户的命令.

• 插入元素1。
• 在元素1之前插入元素2。
• 在1和2之间插入元素3，然后随意重新排列。

我将需要订单不断更新在数据库中的变化，以便我可以加载它在开始。

我需要的行动：

1. 在给定索引处插入
2. 在给定索引处删除
3. 从索引x移到索引y(如果性能没有损失，可以表示为2和1的组合)

所有这些行动都将是频繁和同样重要的。

Answer 1

我想你所说的“有效”是指渐近有效。如果不是这样，那就澄清这个问题。

索引和任意插入的结合是一个棘手的问题。

• List<T>s --它只是数组上的一个薄包装器--在末尾有O(1)插入/删除，在开头有O(n)插入/删除，还有O(1)索引。检查唯一性是O(n)。
• 链接列表具有O(1)插入/删除，前提是您已经知道要将项目放在何处，但是O(n)索引可以找到该位置。检查唯一性是O(n)
• 平衡二叉树有O(lg n)插入，删除和索引，如果你是聪明的。检查唯一性是O(n)。更有异国情调的数据结构，如手指树、跳跃者等，都是相似的。
• 散列集有O(1)插入和删除，但没有索引；检查唯一性是O(1)。

没有适合您需要的单一数据结构。我的建议是：

1. 拥抱不变。编写一个满足您需要的不可变的数据结构。这将更容易推理。
2. 编写一个平衡的二叉树--红色-黑色、AVL等--和一个哈希集的组合。散列集仅用于唯一性检查。BBT在每个节点中都有低于它的项的数量；这有助于索引。插入和删除算法对于BBT来说是正常的，除了它们还重写树的脊柱以确保项计数被正确更新之外。

这将为您提供O(1)唯一性检查和O(lg n)索引、插入和删除。

我注意到，这个数据结构给出了O(1)个问题的答案：“这个项目在集合中吗？”但O(n)回答了“它在哪里？”因此，如果您需要反索引操作是快速的，您有一个更大的问题在您的手上。

Answer 2

我想我应该使用一个列表，并取O(n)包含或单独的HashSet作为惟一性。列表很好地完成了其他所有的事情。很好，因为操作都在那里，但大多数都是O(n)。即使是10,000 O(n)也是相当快的。到目前为止，数据库调用将是最慢的部分(尝试异步)。

    class MyCollection<T> : IList<T>
    {
        private readonly IList<T> _list = new List<T>();

        public void Insert(int index, T item)
        {
            if (this.Contains(item))
                throw new IndexOutOfRangeException();
            _list.Insert(index, item);
            //make database call
        }

        // implement all the other features of IList with database calls

Answer 3

这就变成了两个问题:一个是数据库层的问题，另一个是内存中的问题。然而，我认为如果你让数据库层成为你的真相来源，你实际上可以把它带回到一个问题上。

我之所以这么说，是因为大约有100个条目是列表中活动项的最大可能数，因此您几乎可以忽略渐近复杂性。就性能而言，当您有这么多项时，最需要关注的是跨网络连接(例如到数据库)的往返旅行。

这里有一个非常简单的方法，您可以使用。这和我过去做过的事情很相似，有着相似的要求。(我不记得它是否完全相同，但足够近了。)

1. 使用数字Order列确定给定列表中项的顺序。int应该很好。
2. 当您移除一个项目时，在该项目之后，减少同一列表中所有项目的顺序。这可以用SQL中的单个UPDATE语句来完成。
3. 当您添加一个项目时，根据它添加的位置给它一个订单值，并在该项之后增加相同列表中所有项目的顺序(同样，使用一个Update语句)。
4. 将项目移动到不同位置时，请更改其顺序，然后在开始位置和结束位置之间增加或减少所有项目的顺序。
5. 每次更改时，重新加载整个项目列表，以便从数据库中显示给用户。

您可能希望使用存储的procs在单独的往返中完成更多的此工作。绝对是避免竞争条件的交易。

这样的方法可以轻松地扩展单个用户编辑单个列表的范围。如果您需要并发用户的可伸缩性，那么另一种策略(如NoSQL存储)很可能是可行的。如果您需要对许多并发用户进行缩放，编辑相同的列表，事情就会变得非常复杂，您可能需要实现消息总线和其他优点。如果您发现需要扩展到列表中的数万项，则需要重新考虑UI以及它如何与服务器通信(例如，您不希望将整个列表加载到内存中)。但是，当每个操作都由用户手动执行时，担心内存中的数据结构并不能在任何情况下达到您想要的位置。