用于链表的Mergesort算法 [英] Mergesort algorithm for linked lists
问题描述
嗨伙计们！
每个人都知道如何对数组进行排序（例如快速排序，堆垛等）。
对于链表，mergesort是典型的选择。
虽然我在寻找
链表的mergesort的优化实现，但我找不到一个。我读了一些关于Mcilroy'
"乐观合并排序'的内容。并研究了一些实现，但他们
是针对数组的。有没有人知道Mcilroys优化是否适用于
真正的链接列表？
最后，我想出了我自己的实现（见下文）到
表现相当不错。算法是我自己的想法 - 至少我不知道是否
之前其他任何人都想过这个。
算法是本地化的。它保持一堆排序长度并尝试
尽快合并小块。这利用了一个CPU
缓存。
以下是我的问题：
* - 是我的实现新/正版或有其他人出现
* *之前有这个吗？
* - 它与其他优化实现的比较（在那里提供）
* *是这样的）？我希望听到更好的实现！
* - 优化快速排序时，通常会尝试使用插入排序
* *等小部件。我尝试为mergesort做同样的事情
* *下面，我。即用插入排序对小块长度~10进行排序。
* *它实际上变慢了:(我不太明白为什么。
感谢您的任何评论！
Joerg
PS：你可以在
* *找到这个实现* * http://www.die-Schoens.de/prg/ testsort.tgz
--------------------- snip --------- ---------------------
#include< stddef.h / * * for NULL ** /
typedef struct linkedlist_t linkedlist_t;
struct linkedlist_t {
* linkedlist_t * Next;
* int Key;
};
#define NATURAL / * *识别自然运行** /
linkedlist_t * mergesort（linkedlist_t * list ）
{
* struct {
* * linkedlist_t * list;
* * unsigned int size;
#ifdef NATURAL
* * unsigned int level;
#endif
*} stack [sizeof（int）* 8];
* int nstack;
* for（nstack = -1; ; ）{
* * linkedlist_t * plist，* qlist，* curr;
* * unsigned int psize，qsize;
* * / * *我们还是可以从堆栈中合并列表吗？ ** /
* * if（nstack< 1 ||（
#ifdef NATURAL
* * * * * * * * * * * * stack [nstack - 1] .level！= stack [nstack] .level
#else
* * * * * * * * * * * * stack [nstack - 1] .size！= stack [nstack] .size
#endif
* * * * * * * * * * * *&& list ！= NULL））{
* * * / * ** *推送堆栈中的元素*** * /
* * * if（list = = NULL）
* * * * / * *这是我们打破循环的地方。我们现在有nstack == 0 ** /
* * * *休息;
* * * / * ** *推送列表长度为1 * ** * /
* * * curr = list;
* * * psize = 1;
* * * list = list->下一个;
#ifdef NATURAL
* * * / * *检查自然运行** /
* * * for（plist = curr; list！= NULL; plist = list，list = list-> Next，
++ psize）
* * * * if（list-> Key< plist-> Key）
* * * * * break;
* * * / * *正确终止运行** /
* * * plist-> Next = NULL;
#else
* * * / * *正确终止列表** /
* * * curr-> Next = NULL;
#endif
* * * / * ** *在堆栈上推送此运行*** * /
* * * ++ nstack;
* * * stack [nstack] .list = curr ;
* * * stack [nstack] .size = psize;
#ifdef NATURAL
* * * stack [nstack] .level = 0;
#endif
* * *继续;
* *}
* * / * ** *合并堆栈中的前两个条目*** * /
* * plist = stack [nstack] .list; psize = stack [nstack] .size;
* * --nstack;
* * qlist = stack [nstack] .list; qsize = stack [nstack] .size;
* * / * ** *设置新的堆栈元素。这也简化了主循环
以下** * /
* * if（qlist-> Key< plist-> Key）{
* * * curr = qlist;
* * * qlist = qlist->下一步; --qsize;
* *}否则{
* * * curr = plist;
* * * plist = plist-> Next ; --psize;
* *}
* * stack [nstack] .list = curr;
* * / * *元素数量只是总和** /
* * stack [nstack] .size + = stack [nstack + 1] .size;
#ifdef NATURAL
* * stack [nstack] .level ++;
#endif
* * / * ** *这里是主要的合并循环*** * /
* * while（psize 0&& qsize 0）{
* * * if（qlist-> Key < plist-> Key）{
* * * * curr-> Next = qlist; curr = qlist;
* * * * qlist = qlist->下一步; * --qsize;
* * *}否则{
* * * * curr-> Next = plist; curr = plist;
* * * * plist = plist-> Next ;; * - psize;
* * *}
* *}
* * / * *将余数添加到结果列表** /
* * if（psize 0）{
* * * curr-> Next = plist;
* *} else {
* * * curr-> Next = qlist;
* *}
*}
* / * *这里我们处理list == NULL ** /
*返回nstack == 0的情况？ stack [nstack] .list：NULL;
}
-------------------- snap --- --------------------
Joerg Schoen写道：
< blockquote class =post_quotes>
>
每个人都知道如何排序数组（例如quicksort，heapsort等）
对于链表，mergesort是典型的选择。
虽然我在寻找
链接列表的mergesort的优化实现，但我找不到一个。我读了一些关于Mcilroy'
"乐观合并排序'的内容。并研究了一些实现，但他们
是针对数组的。有没有人知道Mcilroys的优化是否适用于真正的链接列表？
最后，我想出了我自己的实现（见下文）
似乎表现得相当不错。算法是我自己的想法 - 至少
我不知道其他人是否已经提出过这个问题。
算法是本地化的。它保持一堆排序长度
并尝试尽快合并小块。这需要一个CPU缓存的优势。
....剪码...
对我来说太复杂了。在wdfreq.c中有大约60行b $ b行的示例，包括注释，而这又是hashlib.zip中的一个示例
应用程序。请参阅：
< http://cbfalconer.home.att.net/download/>
-
< http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
每次都是对的男人不太可能做得太多。
- Francis Crick，共同发现DNA
没有什么比行动中的愚蠢更令人惊讶了。
- Thomas Matthews
" Joerg Schoen" < jo ************ @ online.dewrote in message
news：ep ********** @ online.de ...
>
- 我的实现是新的/正版还是有其他人出现
之前用这个？
您的实施不太可能是唯一的。有人在某处可能已经完成了它。从理论上和实际上来说，搜索和排序都是非常好的探讨
主题。
但即使你实际实现它的一小部分是独一无二的，
没人会关心，你在历史上的位置也不确定。
一般来说，人们只关心它是否解决了一个值得的实际问题
很多钱，或者为理论问题增加洞察力或解决方案。如果你有一个O（n log n）排序算法的重新实现，那么没有人需要关心
。
现在，如果你开发一个通用的O（log n）排序算法...会有更多的听众。
使用链接列表进行合并似乎没有与使用数组合并
根本不同。
相关问题：我们讨论过bubble-sort今天在课堂上。我有这个新的排序，我发现最后一个元素而不是第一个元素 - 我想
我称之为摇滚排序。我会获得诺贝尔奖吗？
排序已经得到很好的探索。以下是您的反对意见：
http://en.wikipedia.org/wiki/Category:Sort_algorithms
-
David T. Ashley（dt * @ e3ft .com）
http://www.e3ft.com （咨询主页）
http://www.dtashley.com （个人主页）
http://gpl.e3ft.com （GPL出版物和项目）
" David T. Ashley"写道：
>
.... snip ...
>
现在，如果你开发一个通用的O（log n）排序算法......那么
将会有更多的听众。
它们存在。见Sedgewick。需要更多硬件。
>
使用链接列表合并似乎没有根本不同
而不是使用数组合并。
您可以在不干扰/移动/复制实际数据的情况下使用它，并且
列表通常是未知的最方便的输入机制/>
卷。另外mergesort没有最坏的情况，而且很稳定。
-
< http://www.cs.auckland.ac.nz/ ~pgut001 / pubs / vista_cost.txt>
每次都是对的男人不太可能做得太多。
- 弗朗西斯·克里克，共同发现DNA
没有什么比行动中的愚蠢更令人惊讶了。
- Thomas Matthews
Hi folks!
Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.)
For linked lists, mergesort is the typical choice.
While I was looking for a optimized implementation of mergesort for
linked lists, I couldn''t find one. I read something about Mcilroy''s
"Optimistic Merge Sort" and studied some implementation, but they
were for arrays. Does anybody know if Mcilroys optimization is applicable to
truly linked lists at all?
Eventually, I came up with my own implementation (see below) which seems to
perform quite well. The algorithm is my own idea - at least I don''t know if
anybody else has come up with this before.
The algorithm is localized. It maintains a stack of sorting length and tries
to merge small pieces as soon as possible. This takes advantage of a CPU
caches.
Here are my questions about it:
*- Is my implementation new/genuine or has somebody else come up
* *with this before?
*- How does it compare with other optimized implementations (provided there
* *are such)? I would like to hear from better implementations!
*- When optimizing quicksort, one usually tries to use insertion sort
* *and the like for SMALL parts. I tried to do the same for the mergesort
* *below, i. e. sort small pieces of length ~ 10 with insertion sort.
* *It actually became slower :( I don''t quite understand why.
Thanks for any comments!
Joerg
PS: You can find this implementation at
* * * * http://www.die-Schoens.de/prg/testsort.tgz
--------------------- snip ------------------------------
#include <stddef.h/* *for NULL **/
typedef struct linkedlist_t linkedlist_t;
struct linkedlist_t {
* linkedlist_t *Next;
* int Key;
};
#define NATURAL /* *recognize natural runs **/
linkedlist_t *mergesort(linkedlist_t *list)
{
* struct {
* * linkedlist_t *list;
* * unsigned int size;
#ifdef NATURAL
* * unsigned int level;
#endif
* } stack[sizeof(int) * 8];
* int nstack;
* for(nstack = -1 ; ; ) {
* * linkedlist_t *plist, *qlist, *curr;
* * unsigned int psize, qsize;
* * /* *Can we or do we have to merge lists from the stack? **/
* * if(nstack < 1 || (
#ifdef NATURAL
* * * * * * * * * * * *stack[nstack - 1].level != stack[nstack].level
#else
* * * * * * * * * * * *stack[nstack - 1].size != stack[nstack].size
#endif
* * * * * * * * * * * *&& list != NULL)) {
* * * /* ** *Push element(s) on the stack *** */
* * * if(list == NULL)
* * * * /* *This is where we break the loop. We have nstack == 0 now **/
* * * * break;
* * * /* ** *Push lists of length 1 *** */
* * * curr = list;
* * * psize = 1;
* * * list = list->Next;
#ifdef NATURAL
* * * /* *Check for a natural run **/
* * * for(plist = curr ; list != NULL ; plist = list, list = list->Next,
++psize)
* * * * if(list->Key < plist->Key)
* * * * * break;
* * * /* *Properly terminate the run **/
* * * plist->Next = NULL;
#else
* * * /* *Properly terminate list **/
* * * curr->Next = NULL;
#endif
* * * /* ** *Push this run on the stack *** */
* * * ++nstack;
* * * stack[nstack].list = curr;
* * * stack[nstack].size = psize;
#ifdef NATURAL
* * * stack[nstack].level = 0;
#endif
* * * continue;
* * }
* * /* ** *Merge top two entries from stack *** */
* * plist = stack[nstack].list; psize = stack[nstack].size;
* * --nstack;
* * qlist = stack[nstack].list; qsize = stack[nstack].size;
* * /* ** *Set up new stack element. This also simplifies the main loop
below ** */
* * if(qlist->Key < plist->Key) {
* * * curr = qlist;
* * * qlist = qlist->Next; --qsize;
* * } else {
* * * curr = plist;
* * * plist = plist->Next; --psize;
* * }
* * stack[nstack].list = curr;
* * /* *Number of elements is just the sum **/
* * stack[nstack].size += stack[nstack + 1].size;
#ifdef NATURAL
* * stack[nstack].level++;
#endif
* * /* ** *Here is the main merging loop *** */
* * while(psize 0 && qsize 0) {
* * * if(qlist->Key < plist->Key) {
* * * * curr->Next = qlist; curr = qlist;
* * * * qlist = qlist->Next; * --qsize;
* * * } else {
* * * * curr->Next = plist; curr = plist;
* * * * plist = plist->Next;; *--psize;
* * * }
* * }
* * /* *Add remainder to result list **/
* * if(psize 0) {
* * * curr->Next = plist;
* * } else {
* * * curr->Next = qlist;
* * }
* }
* /* *Here we treat the case of list == NULL **/
* return nstack == 0 ? stack[nstack].list : NULL;
}
-------------------- snap -----------------------
Joerg Schoen wrote:>
Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.)
For linked lists, mergesort is the typical choice.
While I was looking for a optimized implementation of mergesort for
linked lists, I couldn''t find one. I read something about Mcilroy''s
"Optimistic Merge Sort" and studied some implementation, but they
were for arrays. Does anybody know if Mcilroys optimization is
applicable to truly linked lists at all?
Eventually, I came up with my own implementation (see below) which
seems to perform quite well. The algorithm is my own idea - at least
I don''t know if anybody else has come up with this before.
The algorithm is localized. It maintains a stack of sorting length
and tries to merge small pieces as soon as possible. This takes
advantage of a CPU caches..... snip code ...
Too long and complicated for me. There is an example in about 60
lines, including comments, in wdfreq.c, which in turn is an example
application in hashlib.zip. See:
<http://cbfalconer.home.att.net/download/>
--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
"Joerg Schoen" <jo************@online.dewrote in message
news:ep**********@online.de...>
- Is my implementation new/genuine or has somebody else come up
with this before?It is unlikely that your implementation is unique. Somebody somewhere has
probably done it before. Searching and sorting are very well explored
topics, both theoretically and practically.
But even if your actual implementation of a small aspect of it is unique,
nobody will care, and your place in history is not assured.
Generally, people will only care if it solves a practical problem worth a
lot of money, or adds insight or a solution to a theoretical problem. If
you have a reimplementation of an O(n log n) sorting algorithm, nobody will
care.
Now, if you develop a general O(log n) sorting algorithm ... there will be
more listeners.
Merging using linked lists doesn''t seem fundamentally different than merging
using arrays.
Related question: We discussed the "bubble-sort" in class today. I have
this new sort where I find the last element instead of the first--I think
I''ll call it the "rock-sort". Will I get the Nobel prize or something?
Sorting has been well explored. Here is what you''re up against:
http://en.wikipedia.org/wiki/Category:Sort_algorithms
--
David T. Ashley (dt*@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)
"David T. Ashley" wrote:>.... snip ...
>
Now, if you develop a general O(log n) sorting algorithm ... there
will be more listeners.They exist. See Sedgewick. Need more hardware though.
>
Merging using linked lists doesn''t seem fundamentally different
than merging using arrays.You use it without disturbing/moving/copying the actual data, and
lists are often the most convenient input mechanism for unknown
volume. In addition mergesort has no worst case, and is stable.
--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
这篇关于用于链表的Mergesort算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
