我记得,从一开始,最流行的实现方法std::list<>::sort()是以自下而上的方式实现的经典Merge Sort算法(另请参阅是什么让gcc std :: list排序实现如此之快？).
我记得有人恰如其分地将这种策略称为"洋葱链"方法.
至少这是GCC实现C++标准库的方式(例如,参见这里).这就是旧版Dimkumware在标准库的MSVC版本中的STL,以及所有版本的MSVC到VS2013的情况.
但是,随VS2015提供的标准库突然不再遵循此排序策略.VS2015附带的库使用自上而下的 Merge Sort 的相当简单的递归实现.这让我感到很奇怪,因为自上而下的方法需要访问列表的中点才能将其分成两半.由于std::list<>不支持随机访问,找到该中间点的唯一方法是逐字遍历列表的一半.此外,在最开始时,有必要知道列表中的元素总数(在C++ 11之前不一定是O(1)操作).
尽管如此,std::list<>::sort()在VS2015确实如此.以下是该实现的摘录,它定位中点并执行递归调用
...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...
正如您所看到的,他们只是无意中使用std::next了遍历列表的前半部分并到达_Mid迭代器.
我想知道这种转变背后的原因是什么？我所看到的是std::next在每个递归级别上重复调用看似明显的低效率.天真的逻辑说这是慢的.如果他们愿意支付这种价格,他们可能希望获得回报.那他们得到了什么？我没有立即将此算法视为具有更好的缓存行为(与原始自下而上方法相比).我没有立即看到它在预先排序的序列上表现得更好.
当然,由于C++ 11 std::list<>基本上需要存储其元素数,这使得上面的效率略高,因为我们总是提前知道元素数.但这仍然不足以证明每个递归级别的顺序扫描是正确的.
(不可否认,我没有试图相互竞争实施.也许有一些惊喜.)
我有一个链表实现,我正在尝试Mergesort和QuickSort算法.
我不明白为什么std :: list中的排序操作如此之快.查看linux下的std :: list,它似乎也是链表,而不是基于数组的列表.
我尝试的合并排序几乎与Dave Gamble的版本相同: 合并排序链接列表
另外,我想我会尝试一个基于此代码的简单快速排序:http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml
令人惊讶的是,使用std :: list和sort对1000万个随机数进行排序比其他任何一个快10倍.
对于那些提出要求的人,是的,我需要为这个项目使用我自己的列表类.
我一直在寻找一个自然的 mergesort实现(链接列表)一段时间,但没有运气.
这里我们有递归和迭代实现,但我不知道如何将其转换为自然合并.
在最佳情况下,如何检查运行以获得O(n)复杂度？它不一定是C/C++,可以是任何语言甚至是伪代码.
谢谢.
是否有任何算法使其链接列表的并行排序值得？
众所周知,Merge Sort是用于排序链表的最佳算法.
大多数合并排序都是根据数组来解释的,每一半都是递归排序的.这将使并行化变得微不足道:独立地对每一半进行排序然后合并两半.
但链表没有"中途"点; 链表一直持续到结束:
头→[a]→[b]→[c]→[d]→[e]→[f]→[g]→[h]→[i]→[j]→...
我现在已经执行了一次实现以获得计数,然后递归地分割计数,直到我们将节点与它进行比较NextNode.递归负责记住两半的位置.
这意味着链表的MergeSort在列表中线性前进.由于它似乎要求通过列表线性进展,我认为它不能并行化.我能想象的唯一方法是:
O(n)O(n/2)O(n log n)但即使我们在单独的线程中并行排序(a,b)和(c,d),我也会认为NextNode重新排序期间的错误共享会破坏任何并行化的优点.
有没有用于排序链表的并行算法？
以下是对数组执行合并排序的标准算法:
algorithm Merge-Sort
input:
an array, A (the values to be sorted)
an integer, p (the lower bound of the values to be sorted)
an integer, r (the upper bound of the values to be sorted)
define variables:
an integer, q (the midpoint of the values to be sorted)
q …sorting algorithm parallel-processing performance linked-list
Vec提供了一种排序方法(通过Deref实现),但LinkedList没有.在Rust标准库中是否存在允许对LinkedLists 进行排序的通用算法？
我发现的大多数归并排序示例都在单个线程中运行。这首先就抵消了使用合并排序算法的一些优势。有人可以展示使用多线程在 java 中编写合并排序算法的正确方法吗？
该解决方案应使用最新版本的 java 的适用功能。Stackoverflow 上已有的许多解决方案都使用普通线程。我正在寻找一个演示 ForkJoin 与 RecursiveTask 的解决方案，这似乎是 RecursiveTask 类的主要用例。
重点应该是展示一种具有卓越性能特征的算法，包括尽可能的时间和空间复杂度。
注意：所提议的重复问题都不适用，因为两者都没有提供使用递归任务的解决方案，而这正是该问题所要求的。
我们的任务是使用基本函数（例如入队、出队、查看、仅清空）以 O(n log n) 的时间对队列进行排序。此外，我们可以使用另一个队列来帮助我们。不允许使用其他数据结构。
很难找到解决方案，因为我觉得这可能是分而治之问题的修改，但我无法使用 4 个基本函数找到解决方案。
是否有可能收到一些提示来解决这个问题？
有没有办法首先排序然后搜索链接的对象列表中的对象.我想你的排序方式和二进制搜索之一你觉得怎么样？谢谢