Q

什么排序算法适合这种“流式”条件？

2012-03-09 80 views 5 likes

5

我有一个缓冲区接收数据，这意味着数据就像'流'，并在'IO'有延迟。我现在的做法是当缓冲区已满时，使用qsort对缓冲区进行排序并将结果写入磁盘。但是在执行qsort时存在明显的延迟，所以我正在寻找其他一些排序算法，这些排序算法可能会在数据添加到缓冲区时开始排序，以减少总体消耗的时间。什么排序算法适合这种“流式”条件？

不知道有没有说清楚，如果需要留下任何意见，感谢

2012-03-09 Mickey Shine

+2

插入排序。真的;-)然而，“O（n lg n）”排序可以很快地对大量数据进行排序......并且如果它“大多数排序”则不一定更快（在这种情况下，快速排序实际上可能非常堕落！）。 ..所以建立一个快速的性能分析可能是值得的。 – 2012-03-09 13:39:14

A

回答

5

堆排序可将数据永久保存在部分排序条件中，因此可与插入排序相比较。但是它比O（n ）的插入排序快得多并且具有O（n log n）的最坏情况。

这是怎么回事？据推测，在某些时候，你必须停止阅读流，存储你已经排序，并开始阅读一组新的数据？

2012-03-09 13:55:37 Borodin

+0

+1堆排序，你不需要它被完全排序，以便在写入之间进行缓冲 – 2012-03-09 15:06:39

+0

是的，在我的情况下，我必须停止从流中读取并对缓冲区进行排序并将结果写入磁盘，然后再次开始读取并且重复，直到流结束 – 2012-03-09 23:48:04

+0

然后堆排序是你想要的。从流中读取数据到堆中，直到必须停止为止，然后从堆中读取并写入磁盘，直到它为空。从堆中读取的数据按排序顺序排列。 – Borodin 2012-03-10 09:52:59

2

我认为合并排序或树排序可以有很大的帮助。看看why on wikipedia。

当您可以在合理的大块中剪切大量输入时，合并排序更合适。
当您一次插入小块时，树状排序更合适。

你想要实现一个在线排序算法，即在流线型接收数据时运行的算法。通过网络搜索online algorithms，您可能会发现其他不错的算法。

在你的情况下，我会使用树排序。它没有比快速排序更好的复杂性（大多数情况下都是O(nlog n)，在很少的情况下都是O(n²)）。但它会摊销每个输入的成本。这意味着添加最后一个数据后，您必须等待的延迟时间不是订单O(nlog n)，而是O(log n)

2012-03-09 13:42:44 UmNyobe

0

您可以尝试使用我的Link Array结构。顺序添加随机数据并保持排序应该是可以的（查看表中的数字）。这是Skip list方式的变化，但有更简单的实现和逻辑（尽管跳跃列表的表现应该会更好）

2012-03-10 12:56:27 Maksee

相关问题