保持排序顺序的集合 C#

Question

我有一个类Foo，其中包含一个对象列表：List<Bar>。每个Bar都有一个可以根据其排序的属性（类型为TimeSpan，表示持续时间），并且Bar是不可变的对象-也就是说，在算法运行期间，持续时间不会改变。目前，对于每个Foo，我还维护了将其按顺序排列时列表中第一个Bar（即最短持续时间的Bar）。大致如下：

public class Foo
{
    public List<Bar> AllBars { get; set; }

    public Bar FirstBar { get; set; }

    public Foo (Bar bar)
    {
        FirstBar = bar;

        AllBars = new List<Bar>() { bar };
    }

    public AddBar(Bar bar)
    {
        if(bar.Duration < FirstBar.Duration)
        {
            FirstBar = bar;
        }

        AllBars.Add(bar);
    }
}

这个类Foo在一个处理性能(速度)至关重要的算法中使用。 内存很重要，但不如速度重要。 有一个包含n个Foo的列表，每个Foo最多有m个Bar。 这个类一直到现在为止都表现得很好。 我现在希望为用户提供几个选择，这意味着我需要在列表中提供对前几个Bar的随机访问。

因此，我希望按顺序存储我的Bar，以便可以按索引顺序访问它们。 在我的Bar类中，我实现了IComparable以允许比较Bar持续时间，但我卡在选择适当数据类型上。 我看了一下System.Collections.SortedList，但（除非我错了）它似乎参考元素的键，因为它实现了IDictionary。 我可以使用什么集合来维护我的对象，使它们保持排序，并且可以按索引顺序遍历？

- 08Dc91wk

---

请尝试使用 SortedSet，但请注意它不允许重复项。 - D Stanley

你需要通过索引随机访问它们，还是只是按顺序依次访问？换句话说，你需要获取 AllBars[2] 这样的元素吗？还是只是在使用 foreach 时保持元素的顺序即可？ - D Stanley

我个人会在算法使用的时候直接订购它。维护一个标志来表示它是否需要排序，基于自上次排序以来是否有新加入的内容，然后让调用者在运行算法之前对其进行排序。最终，排序的实现是特定于此算法的，因此我认为将责任转移给它没有问题。 - Adam Houldsworth

@AlexanderKozlov 我知道，但我想了解为什么像 var sorted = list.OrderBy(_ => _).ToArray() 这样简单的东西不能在此算法之前使用。我们无法在不知道插入次数、列表大小、排序之间调用此算法的频率等情况下建议实现。 - Adam Houldsworth

这是其中一件事情，你必须决定最佳的折衷方案。如果你需要一个排序后的列表，具有索引访问和插入（也许删除）项目并保持排序顺序的能力，那么至少其中一种操作将变得很慢，以便其他操作可以快速执行。你需要弄清楚使用情况会是什么样子的。你会经常插入吗？经常读取吗？随机还是按顺序阅读？列表有多大？等等。 - Matt Burland

Answer 1

我更喜欢使用SortedSet<T>，它是一种二叉树，其中键和值是相同的对象。这意味着添加、删除和查找的时间复杂度仍然为对数级别 - O(log n) - 但您可以按顺序迭代项目。要使此集合有效，类型T必须实现IComparable<T>或您需要提供外部IComparer<T>。

- S.N

---

你打算如何从 SortedSet 中获取第 n 个元素？ - Rawling

您可以按顺序迭代。这可能是请求者需要的。现在要使它更难，由于其后备存储，无法选择第n个元素。但是，您可以使用（我还没有进行任何性能测试）Enumerable.ElementAt<TSource>()。 - S.N

@JeppeStigNielsen，SortedSet<T>和SortedDictionary<TKey,TValue>的后备存储是一个二叉树，其中键和值是同一个对象。如果我错了，请纠正我。 - S.N

@AlexanderKozlov，如果你想查看第n个元素，那么它的时间复杂度是O(n)。否则，由于二叉树未改变，时间复杂度为O(log n)。我回答了你的问题吗？ - S.N

@AlexanderKozlov SortedDictionary 的检索时间复杂度为 O(log n)，详情请见 https://dev59.com/b3NA5IYBdhLWcg3wgeEd - smartcaveman

Answer 2

如果您可以接受“值”毫无意义的话，只需使用 SortedList<Bar, object>，其中不使用值部分。

使用 yourSortedList.Add(yourBar, null) 进行添加，时间复杂度为 O(n)（列表将不得不在插入点之后移动所有条目）。使用 yourSortedList.Keys[i] 可以在 O(1) 时间内检索第 i 个条目。

有关上述说明正确性的一些“证明”，请参阅 SortedList<,>.Keys 属性文档。请注意，SortedList<,> 实际上由一个“列表”组成（即长度为 Capacity 的数组，可能会在必要时被更大的数组替换）。这与我认为是二叉搜索树的 SortedDictionary<,> 不同。

但是请注意：您将无法在 SortedList<,> 中有重复项，因此不允许列表中的两个成员以返回值为零的方式进行比较。

- Jeppe Stig Nielsen

Answer 3

为什么不直接使用List.Insert？
Insert是O(n)的，可以让你在特定的索引位置插入。
n + n 仍然是O(n)

public AddBar(Bar bar)
{
    int index = 0;    
    foreach (bar b in AllBar)
    {
       if(bar.Duration < b.Duration)
         break;
       index++;
    }
    AllBars.Insert(index, bar);
}

所以你有排序和O(1)索引
代价是O(n)添加
当前的添加也是O(n)

一个SortedList是 NlogN，然后你没有索引，因为key是Duration，而且key不唯一

一个SortedSet插入是LogN，但ToList是O(n)，所以你还是O(n)

在列表上调用Sort方法是NlogN

这回答了明确的问题：我可以使用哪种集合来维护对象使其保持排序，并以索引顺序遍历？

我认为你最好不要超过O(n)的添加。

- paparazzo

---

每次插入都将是O(N)。 - Lasse V. Karlsen

@LasseV.Karlsen，我非常清楚地说明了插入是O(n)。List.Add也是O(n)。你给我投反对票了吗？它使用O(1)索引访问进行排序。你有更好的解决方案吗？ - paparazzo