有序列表的最佳数据结构（性能）是什么？

Question

有序列表的最佳数据结构（性能）是什么？

c++algorithmsorting

5

我有一个关键部分的应用程序，它由获取数据源（无序）并按顺序对每个元素执行算法组成。目前我遵循以下算法：

- 读取源并将其放入std :: map中，使用排序元素作为键，信息作为内容。 - 使用迭代器读取映射并执行算法。

我发现map可能不是最好的数据结构，因为我只需要将数据添加到排序列表中，然后一起“烧掉”（此外，在移动设备上进行内存分配是昂贵的，所以我更愿意自己处理）。

我已经做了一些研究，正在阅读B树和Black-Red树之类的东西。它们可能是我要寻找的，但我会在这里问一下是否有人知道一个方便这项任务的数据结构。

总之，我想要一个具有以下结构：

- 快速插入。 - 快速迭代（从开始到结束）。 - 其他所有内容都不重要（既不删除也不搜索）。

快速插入比快速迭代更重要（我的分析工具如此表明:D）。

谢谢大家。

- Atridas

1

你的问题可能值得添加一个语言标签。std::map是一种红黑树。 - doctorlove

1

如果您认为存储数据很昂贵，为什么不在数据到来时直接处理它，然后将其丢弃？ - doctorlove

@doctorlove：输入是无序的。 - Marcelo Cantos

1

在特定范围内，是否为关键值？ - Regenschein

@doctorlove 我没有加入C++标签，因为我的问题不是基于语言的。今天我正在用Objective-C++实现它，但有一天我需要将其移植到Android上，而且我可能无法使用C++（我真的希望我能）。 - Atridas

@Atridas，请回答fordperfect的问题，如果键有指定范围，您可能可以在渐近意义下改进算法。 - Ivaylo Strandjev

4个回答

3

理论上更好的方法是使用堆排序。

然而，实际上，最快的方法是将您的元素附加到一个向量中，并使用快速排序对它们进行排序。

在这两种情况下，平均需要 O( N * log(N) ) 的时间，但快速排序具有较低的常数因子。

- Boris Dalstein

1

然而，如果效率至关重要，快速排序具有可怕的O(n^2)边界情况。我建议使用向量，但为了安全起见，请改用归并排序而不是快速排序。 - cgledezma

@cgledezma：这确实是一个重要的观点，但最终，一切都归结于具体情况和OP的要求以及他/她对“效率”的定义。如果已知边界情况不会发生，仍然使用向量快速排序。如果偶尔慢一些也可以接受，只要在大多数情况下尽可能高效，那么仍然使用向量快速排序。然而，如果您无法控制输入，并且需要保证始终“足够高效”，则使用向量归并排序（易于实现）或堆排序。 - Boris Dalstein

嗯，也许我误解了问题，但在我看来，元素可能是动态添加的，这意味着迭代和插入不需要按照你所做的顺序执行。在这种情况下，您将需要执行多个排序。 - Ivaylo Strandjev

@IvayloStrandjev：这不是我理解问题的方式：“我只需要将数据添加到一个排序列表中，然后一次性“烧掉”整个列表”，因此我认为操作只需在所有数据已知后执行一次。否则，使用映射或优先队列确实是一个好方法。 - Boris Dalstein

我知道这是一个旧帖子，但值得注意的是，在追加后，如果数组几乎排序完成，您不应该使用快速排序进行排序，而应该使用插入排序。 C ++的sort（）函数在开始时或如果数组很小，则几乎肯定会使用插入排序，但如果OP自己编写所有代码，则应该使用插入排序，或者可能是有序向量的二进制搜索以获取插入位置。 - physincubus

2

如果您的键值只存在于有限的一定范围内，您可能需要考虑使用桶排序算法。

- Regenschein

0

我建议编写一个跳表。它正是你所要求的 - 一个具有O(log(n))插入的排序列表。它也相对容易实现。

- Ivaylo Strandjev

2

我不会说实现起来很容易，尤其是与C++已经提供的std::vector和qsort()相比;-) 顺便说一下，std::map也具有O(log(N))插入，并且已经在C++中提供。据我所知，跳表唯一的优点是能够更有效地获取第i个元素，但似乎OP只需要遍历它们所有（无需独立访问第i个元素），因此与std::map相比没有任何有用的东西。 - Boris Dalstein

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marcelo Cantos · Accepted Answer

至少有两种高效的解决方案：

将元素追加到向量中；对向量进行排序；扫描向量。
将元素插入到优先队列中；排空它。

向量具有 O(N) 的加载时间优势（相对于优先队列的 O(N log N)）。注意，由于排序，总体时间复杂度仍为 O(N log N)。

优先队列的优点是在排空时释放内存。这不会减少最大内存占用，并且可能带来微不足道的好处，但还是值得一试的。