Re: quicksort for linked list
Hi again. The latter half of my email seems to have been forgotten in the ensuing discussion, so I'll repost. For a linked list of any non-floating point data, radix sort is almost impossible to beat; it's iterative, fast (linear time for fixed size integers, worst case), can be stopped early for partial sorting, and has a pretty simple implementation. I've been using essentially the same radix sort implementation I posted before to sort 1000 item lists 60 times a second in a numerical application, and it barely shows up in the total time used when profiling. The other sorts I tried did not fare so well. I would much rather see this in a kernel modification than any merge/quick/heap sort implementations I've seen so far for linked lists. OTOH, this conversation seems to have wandered out of kernel-space anyway... - Jim Bruce (Examples at: http://www.cs.cmu.edu/~jbruce/sort.cc) 10-Mar-2001 Re: quicksort for linked list by David [EMAIL PROTECTED] > For modern machines, I'm not sure that quicksort on a linked list is > typically much cheaper than mergesort on a linked list. The > majority of the potential cost is likely to be in the pointer > chasing involved in bringing the lists into cache, and that will be > the same for both. Once the list is in cache, how much pointer > fiddling you do isn't so important. For lists that don't fit into > cache, the advantages of mergesort should become even greater if the > literature on tape and disk sorts applies (though multiway merges > rather than simple binary merges would be needed to minimize the > impact of memory latency). > > Given this, mergesort might be generally preferable to quicksort for > linked lists. But I haven't investigated this idea thoroughly. > (The trick described above for avoiding an explicit stack also works > for mergesort.) - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
David Wragg wrote: > For modern machines, I'm not sure that quicksort on a linked list is > typically much cheaper than mergesort on a linked list. ... > For lists that don't fit into cache, the advantages of mergesort > should become even greater if the literature on tape and disk sorts > applies (though multiway merges rather than simple binary merges would > be needed to minimize the impact of memory latency). ... > Given this, mergesort might be generally preferable to quicksort for > linked lists. But I haven't investigated this idea thoroughly. (The > trick described above for avoiding an explicit stack also works for > mergesort.) Fwiw, below is a pretty good list mergesort. It takes linear time on "nearly sorted" lists (i.e. better than classic mergesort), and degrades to O(n log n) worst case (i.e. better than quicksort). It's non-recursive and uses a small bounded stack. enjoy ;-) -- Jamie /* A macro to sort linked lists efficiently. O(n log n) worst case, O(n) on nearly sorted lists. Copyright (C) 1995, 1996, 1999 Jamie Lokier. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifndef __fast_merge_sort_h #define __fast_merge_sort_h /* {{{ Description */ /* This macro sorts singly-linked lists efficiently. To sort a doubly-linked list: sort, then traverse the forward links to regenerate the reverse links. Written by Jamie Lokier <[EMAIL PROTECTED]>, 1995-1999. Version 2.0. Properties == 1. Takes O(n) time to sort a nearly-sorted list; very fast indeed. 2. Takes O(n log n) time for worst case and for random-order average. Worst case is a reversed list. Sorting is still fast. NB: This is much faster than unmodified quicksort, which is O(n^2). 3. Requires no extra memory: sorts in place like heapsort and quicksort. Uses a small array (typically 32 pointers) on the stack. 4. Stable: equal elements are kept in the same relative order. 5. Macro so the comparisons and structure modifications are in line. You typically have a C function which calls the macro and does very little else. The sorting code is not small enough to be worth inlining in its caller; however, the comparisons and strucure modifications generally _are_ worth inlining into the sorting code. Requirements Any singly-linked list structure. You provide the structure type, and the name of the structure member to reach the next element, and the address of the first element. The last element is identified by having a null next pointer. How to sort a list == Call as `FAST_MERGE_SORT (LIST, TYPE, NEXT, LESS_THAN_OR_EQUAL_P)'. `LIST' points to the first node in the list, or can be null. Afterwards it is updated to point to the beginning of the sorted list. `TYPE' is the type of each node in the linked list. `NEXT' is the name of the structure member containing the links. In C++, this can be a call to a member function which returns a non-const reference. `LESS_THAN_OR_EQUAL_P' is the name of a predicate which, given two pointers to objects of type `TYPE', determines if the first is less than or equal to the second. The equality test is important to keep the sort stable (see earlier). The total number of items must fit in `unsigned long'. How to update a sorted list === A call is provided to sort a list, and combine that with another which is already sorted. This is useful when you've sorted a list, but later want to add some new elements. The code is optimised by assuming that the already sorted list is likely to be the larger. The already sorted list comes earlier in the input, for the purpose of stable sorting. That is, if an element in the already sorted list compares equal to one in the list to sort, the element from the already sorted list will come first in the output. Call as `FAST_MERGE_SORT_APPEND (ALREADY_SORTED, LIST, TYPE, NEXT, LESS_THAN_OR_EQUAL_P)'. `ALREADY_SORTED' points to the first node of an already sorted list, or can be null. If the list isn't sorted already, the result is undefined. `LIST' points to the first node in the list to
Re: quicksort for linked list
David Wragg wrote: For modern machines, I'm not sure that quicksort on a linked list is typically much cheaper than mergesort on a linked list. ... For lists that don't fit into cache, the advantages of mergesort should become even greater if the literature on tape and disk sorts applies (though multiway merges rather than simple binary merges would be needed to minimize the impact of memory latency). ... Given this, mergesort might be generally preferable to quicksort for linked lists. But I haven't investigated this idea thoroughly. (The trick described above for avoiding an explicit stack also works for mergesort.) Fwiw, below is a pretty good list mergesort. It takes linear time on "nearly sorted" lists (i.e. better than classic mergesort), and degrades to O(n log n) worst case (i.e. better than quicksort). It's non-recursive and uses a small bounded stack. enjoy ;-) -- Jamie /* A macro to sort linked lists efficiently. O(n log n) worst case, O(n) on nearly sorted lists. Copyright (C) 1995, 1996, 1999 Jamie Lokier. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifndef __fast_merge_sort_h #define __fast_merge_sort_h /* {{{ Description */ /* This macro sorts singly-linked lists efficiently. To sort a doubly-linked list: sort, then traverse the forward links to regenerate the reverse links. Written by Jamie Lokier [EMAIL PROTECTED], 1995-1999. Version 2.0. Properties == 1. Takes O(n) time to sort a nearly-sorted list; very fast indeed. 2. Takes O(n log n) time for worst case and for random-order average. Worst case is a reversed list. Sorting is still fast. NB: This is much faster than unmodified quicksort, which is O(n^2). 3. Requires no extra memory: sorts in place like heapsort and quicksort. Uses a small array (typically 32 pointers) on the stack. 4. Stable: equal elements are kept in the same relative order. 5. Macro so the comparisons and structure modifications are in line. You typically have a C function which calls the macro and does very little else. The sorting code is not small enough to be worth inlining in its caller; however, the comparisons and strucure modifications generally _are_ worth inlining into the sorting code. Requirements Any singly-linked list structure. You provide the structure type, and the name of the structure member to reach the next element, and the address of the first element. The last element is identified by having a null next pointer. How to sort a list == Call as `FAST_MERGE_SORT (LIST, TYPE, NEXT, LESS_THAN_OR_EQUAL_P)'. `LIST' points to the first node in the list, or can be null. Afterwards it is updated to point to the beginning of the sorted list. `TYPE' is the type of each node in the linked list. `NEXT' is the name of the structure member containing the links. In C++, this can be a call to a member function which returns a non-const reference. `LESS_THAN_OR_EQUAL_P' is the name of a predicate which, given two pointers to objects of type `TYPE', determines if the first is less than or equal to the second. The equality test is important to keep the sort stable (see earlier). The total number of items must fit in `unsigned long'. How to update a sorted list === A call is provided to sort a list, and combine that with another which is already sorted. This is useful when you've sorted a list, but later want to add some new elements. The code is optimised by assuming that the already sorted list is likely to be the larger. The already sorted list comes earlier in the input, for the purpose of stable sorting. That is, if an element in the already sorted list compares equal to one in the list to sort, the element from the already sorted list will come first in the output. Call as `FAST_MERGE_SORT_APPEND (ALREADY_SORTED, LIST, TYPE, NEXT, LESS_THAN_OR_EQUAL_P)'. `ALREADY_SORTED' points to the first node of an already sorted list, or can be null. If the list isn't sorted already, the result is undefined. `LIST' points to the first node in the list to be sorted, or
Re: quicksort for linked list
Hi again. The latter half of my email seems to have been forgotten in the ensuing discussion, so I'll repost. For a linked list of any non-floating point data, radix sort is almost impossible to beat; it's iterative, fast (linear time for fixed size integers, worst case), can be stopped early for partial sorting, and has a pretty simple implementation. I've been using essentially the same radix sort implementation I posted before to sort 1000 item lists 60 times a second in a numerical application, and it barely shows up in the total time used when profiling. The other sorts I tried did not fare so well. I would much rather see this in a kernel modification than any merge/quick/heap sort implementations I've seen so far for linked lists. OTOH, this conversation seems to have wandered out of kernel-space anyway... - Jim Bruce (Examples at: http://www.cs.cmu.edu/~jbruce/sort.cc) 10-Mar-2001 Re: quicksort for linked list by David [EMAIL PROTECTED] For modern machines, I'm not sure that quicksort on a linked list is typically much cheaper than mergesort on a linked list. The majority of the potential cost is likely to be in the pointer chasing involved in bringing the lists into cache, and that will be the same for both. Once the list is in cache, how much pointer fiddling you do isn't so important. For lists that don't fit into cache, the advantages of mergesort should become even greater if the literature on tape and disk sorts applies (though multiway merges rather than simple binary merges would be needed to minimize the impact of memory latency). Given this, mergesort might be generally preferable to quicksort for linked lists. But I haven't investigated this idea thoroughly. (The trick described above for avoiding an explicit stack also works for mergesort.) - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Sat, Mar 10, 2001 at 07:50:06PM +0100, Martin Mares wrote: > Hello! > > > Well, not really in this situation, after a simple modification. It is > > trivial to show that using "shorter interval sorted first" approach one > > can bound an amount of an extra memory, on stack or otherwise, and by a > > rather small number. > > By O(log N) which is in reality a small number :) Assuming that we sort a full range of 32-bit numbers (pointers on a 32-bit CPU, for example, are numbers of that kind but usually a range can be narrowed down quite substantially) then with a bit of a careful programming you need, I think, something like 16 extra 4-byte words or maybe even a bit less. I do not remember precisely, as I was doing this exercise a long time ago, but even if this is 32, and you need carefuly constructed example to need them all these extra cells, I still think that this is not a huge amount of memory. Especially when every element of a list you are sorting is likely quite a bit bigger. Exponents are something which grows these numbers pretty fast. :-) Michal - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
[EMAIL PROTECTED] (Rogier Wolff) writes: > Quicksort however is an algorithm that is recursive. This means that > it can use unbounded amounts of stack -> This is not for the kernel. The implementation of Quicksort for arrays demands a recursive implementation, but for doubly-linked lists there is a trick that leads to an iterative implementation. You can implement Quicksort recursively for singly linked lists, so in a doubly-linked list you have a spare link in each node while you are doing the sort. You can hide the stack in those links, so the implementation doesn't need to be explicitly recursive. At the end of the sort, the "next" links are correct, so you have to go through and fix up the "prev" links. > Quicksort however is an algorithm that is good for large numbers of > elements to be sorted: the overhead of a small set of items to sort is > very large. Is the "normal" case indeed "large sets"? Good implementations of Quicksort actually give up on Quicksort when the list is short, and use an algorithm that is faster for that case (measurements are required to find out where the boundary between a short list and a long list lies). If the full list to be sorted is short, Quicksort will never be involved. If that happens to be the common case, then fine. > Quicksort has a very bad "worst case": quadratic sort-time. Are you > sure this won't happen? Introsort avoids this by modifying quicksort to resort to a mergesort when the recursion gets too deep. For modern machines, I'm not sure that quicksort on a linked list is typically much cheaper than mergesort on a linked list. The majority of the potential cost is likely to be in the pointer chasing involved in bringing the lists into cache, and that will be the same for both. Once the list is in cache, how much pointer fiddling you do isn't so important. For lists that don't fit into cache, the advantages of mergesort should become even greater if the literature on tape and disk sorts applies (though multiway merges rather than simple binary merges would be needed to minimize the impact of memory latency). Given this, mergesort might be generally preferable to quicksort for linked lists. But I haven't investigated this idea thoroughly. (The trick described above for avoiding an explicit stack also works for mergesort.) > Isn't it easier to do "insertion sort": Keep the lists sorted, and > insert the item at the right place when you get the new item. Easier? Yes. Slower? Yes. Does its being slow matter? Depends on the context. David Wragg - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Hello! > Well, not really in this situation, after a simple modification. It is > trivial to show that using "shorter interval sorted first" approach one > can bound an amount of an extra memory, on stack or otherwise, and by a > rather small number. By O(log N) which is in reality a small number :) Have a nice fortnight -- Martin `MJ' Mares <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> http://atrey.karlin.mff.cuni.cz/~mj/ "Dijkstra probably hates me." -- /usr/src/linux/kernel/sched.c - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Oliver Xymoron <[EMAIL PROTECTED]> writes: > On Fri, 9 Mar 2001, Rogier Wolff wrote: > > > Quicksort however is an algorithm that is recursive. This means that > > it can use unbounded amounts of stack -> This is not for the kernel. > > It is of course bounded by the input size, but yes, it can use O(n) > additional memory in the worst case. There's no particular reason this > memory has to be on the stack - it's just convenient. You only need O(log n) additional memory if you sort the shortest sublist before the longest one (and turn the second recursive call into a loop). As log n is certainly less that 64, one can even consider that Quicksort only uses a bounded amount of memory. -- Jerome - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Hello! Well, not really in this situation, after a simple modification. It is trivial to show that using "shorter interval sorted first" approach one can bound an amount of an extra memory, on stack or otherwise, and by a rather small number. By O(log N) which is in reality a small number :) Have a nice fortnight -- Martin `MJ' Mares [EMAIL PROTECTED] [EMAIL PROTECTED] http://atrey.karlin.mff.cuni.cz/~mj/ "Dijkstra probably hates me." -- /usr/src/linux/kernel/sched.c - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
[EMAIL PROTECTED] (Rogier Wolff) writes: Quicksort however is an algorithm that is recursive. This means that it can use unbounded amounts of stack - This is not for the kernel. The implementation of Quicksort for arrays demands a recursive implementation, but for doubly-linked lists there is a trick that leads to an iterative implementation. You can implement Quicksort recursively for singly linked lists, so in a doubly-linked list you have a spare link in each node while you are doing the sort. You can hide the stack in those links, so the implementation doesn't need to be explicitly recursive. At the end of the sort, the "next" links are correct, so you have to go through and fix up the "prev" links. Quicksort however is an algorithm that is good for large numbers of elements to be sorted: the overhead of a small set of items to sort is very large. Is the "normal" case indeed "large sets"? Good implementations of Quicksort actually give up on Quicksort when the list is short, and use an algorithm that is faster for that case (measurements are required to find out where the boundary between a short list and a long list lies). If the full list to be sorted is short, Quicksort will never be involved. If that happens to be the common case, then fine. Quicksort has a very bad "worst case": quadratic sort-time. Are you sure this won't happen? Introsort avoids this by modifying quicksort to resort to a mergesort when the recursion gets too deep. For modern machines, I'm not sure that quicksort on a linked list is typically much cheaper than mergesort on a linked list. The majority of the potential cost is likely to be in the pointer chasing involved in bringing the lists into cache, and that will be the same for both. Once the list is in cache, how much pointer fiddling you do isn't so important. For lists that don't fit into cache, the advantages of mergesort should become even greater if the literature on tape and disk sorts applies (though multiway merges rather than simple binary merges would be needed to minimize the impact of memory latency). Given this, mergesort might be generally preferable to quicksort for linked lists. But I haven't investigated this idea thoroughly. (The trick described above for avoiding an explicit stack also works for mergesort.) Isn't it easier to do "insertion sort": Keep the lists sorted, and insert the item at the right place when you get the new item. Easier? Yes. Slower? Yes. Does its being slow matter? Depends on the context. David Wragg - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Sat, Mar 10, 2001 at 07:50:06PM +0100, Martin Mares wrote: Hello! Well, not really in this situation, after a simple modification. It is trivial to show that using "shorter interval sorted first" approach one can bound an amount of an extra memory, on stack or otherwise, and by a rather small number. By O(log N) which is in reality a small number :) Assuming that we sort a full range of 32-bit numbers (pointers on a 32-bit CPU, for example, are numbers of that kind but usually a range can be narrowed down quite substantially) then with a bit of a careful programming you need, I think, something like 16 extra 4-byte words or maybe even a bit less. I do not remember precisely, as I was doing this exercise a long time ago, but even if this is 32, and you need carefuly constructed example to need them all these extra cells, I still think that this is not a huge amount of memory. Especially when every element of a list you are sorting is likely quite a bit bigger. Exponents are something which grows these numbers pretty fast. :-) Michal - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, Mar 09, 2001 at 12:52:22PM +0100, Rogier Wolff wrote: > > Quicksort however is an algorithm that is recursive. This means that > it can use unbounded amounts of stack -> This is not for the kernel. Well, not really in this situation, after a simple modification. It is trivial to show that using "shorter interval sorted first" approach one can bound an amount of an extra memory, on stack or otherwise, and by a rather small number. This assumes that one knows what one is sorting - which is obviously the case here. Also my copy of Reingold, Nivergelt, Deo from 1977 presents a "non-recursive" variant of quicksort as a kind of an "old hat" solution. One would think that this piece of information would spread during those years. :-) It is a simple exercise anyway. > Quicksort has a very bad "worst case": quadratic sort-time. Are you > sure this won't happen? This is much more serious objection. You can nearly guarantee in an itended application that somebody will find a way to feed you packets which will ensure the worst case behaviour. The same gotcha will probably kill quite a few other ways to sort here. Michal - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, 9 Mar 2001, Rogier Wolff wrote: > Quicksort however is an algorithm that is recursive. This means that > it can use unbounded amounts of stack -> This is not for the kernel. It is of course bounded by the input size, but yes, it can use O(n) additional memory in the worst case. There's no particular reason this memory has to be on the stack - it's just convenient. > Isn't it easier to do "insertion sort": Keep the lists sorted, and > insert the item at the right place when you get the new item. Assuming you get your items in sorted order, this is also O(N^2). -- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, 9 Mar 2001, Alan Cox wrote: > > Quicksort works just fine on a linked list, as long as you broaden > > your view beyond the common array-based implementations. See > > "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I > > would recommend using a radix sort for linked lists in most situations > > (sorry for the C++, but it was handy...). > > In a network environment however its not so good. Quicksort has an N^2 > worst case and the input is controlled by a potential enemy. It's not too hard to patch that up, eg quickersort. N^2 isn't too bad for short queues anyway especially considering the complexity of the alternatives. > Im dubious about anyone doing more than simple bucket sorting for packets. Assume you mean sorting into hash buckets as opposed to "count the number of occurrences of each type of element in a narrow range, discarding the actual element". Most hashes are subvertible too and probably don't fair any better than N^2. -- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, 9 Mar 2001, Helge Hafting wrote: > Manoj Sontakke wrote: > > > > 1. Is quicksort on doubly linked list is implemented anywhere? I need it > > for sk_buff queues. > > I cannot see how the quicksort algorithm could work on a doubly > linked list, as it relies on being able to look > up elements directly as in an array. > > You can probably find algorithms for sorting a linked list, but > it won't be quicksort. Here ya go (wrote this a few years ago): // This function is so cool. template void list::qsort(iter l, iter r, cmpfunc *cmp, void *data) { if(l==r) return; iter i(l), p(l); for(i++; i!=r; i++) if(cmp(*i, *l, data)<0) i.swap(++p); l.swap(p); qsort(l, p, cmp, data); qsort(++p, r, cmp, data); } Iters are essentially list pointers with increment operations. This is a fairly direct adaptation of the quicksort in K, actually. -- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, Mar 09, 2001 at 01:08:57PM +0530, Manoj Sontakke wrote: > Hi > Sorry, these questions do not belog here but i could not find any > better place. > > 1. Is quicksort on doubly linked list is implemented anywhere? I need it > for sk_buff queues. I would suggest that you use merge sort. It is ideally suited for sorting linked lists, and it always has N log N running time. I dont know of an existing implementation in the kernel sources, but it should be easy to write one. I did a google search on "merge sort" "linked list" and it comes up with lots of links. Here is a good one: http://www.ddj.com/articles/1998/9805/9805p/9805p.htm?topic=java Hope this helps, Jim - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
In article <[EMAIL PROTECTED]> you write: > Quicksort however is an algorithm that is recursive. This means that > it can use unbounded amounts of stack -> This is not for the kernel. Maybe a heapsort, then. It is guaranteed O(n*log n), even for worst case, and non-recursive. Yet it implies a significantly larger amount of comparisons than quicksort (about twice, I think). Insertion sort will be better anyway for small sets of data (for 5 or less elements). --Thomas Pornin - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Helge Hafting wrote: > Manoj Sontakke wrote: > > > > Hi > > Sorry, these questions do not belog here but i could not find any > > better place. > > > > 1. Is quicksort on doubly linked list is implemented anywhere? I need it > > for sk_buff queues. > > I cannot see how the quicksort algorithm could work on a doubly > linked list, as it relies on being able to look > up elements directly as in an array. It took me a few moments to realize, but quicksort is one algorithm that DOES NOT rely on directly accessing array elements. qsort (items) { if (numberof (items) <= 1) return. pivot = chose_pivot (items) for (all items) if (curitem < pivot) put on the left of pivot else put on the right of pivot qsort (items on the left of pivot); qsort (items on the right of pivot); } All operations are easily done on lists, not only on arrays. Actually, the array-implementation has a few thingies to avoid having to move the half the array on the scan of one item. With a list that is not an issue. If you know how you chose your pivot, one of the "puts" can be nil. (for example, chose the pivot as the leftmost item. All other items are already on the right. So "put on the left of pivot" is "unlink (curitem), relink_to_the_left (pivot, curitem)", but put on the right is "/* nothing to be done */". Quicksort however is an algorithm that is recursive. This means that it can use unbounded amounts of stack -> This is not for the kernel. Quicksort however is an algorithm that is good for large numbers of elements to be sorted: the overhead of a small set of items to sort is very large. Is the "normal" case indeed "large sets"? Quicksort has a very bad "worst case": quadratic sort-time. Are you sure this won't happen? Isn't it easier to do "insertion sort": Keep the lists sorted, and insert the item at the right place when you get the new item. Roger. -- ** [EMAIL PROTECTED] ** http://www.BitWizard.nl/ ** +31-15-2137555 ** *-- BitWizard writes Linux device drivers for any device you may have! --* * There are old pilots, and there are bold pilots. * There are also old, bald pilots. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
> Quicksort works just fine on a linked list, as long as you broaden > your view beyond the common array-based implementations. See > "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I > would recommend using a radix sort for linked lists in most situations > (sorry for the C++, but it was handy...). In a network environment however its not so good. Quicksort has an N^2 worst case and the input is controlled by a potential enemy. Im dubious about anyone doing more than simple bucket sorting for packets. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Quicksort works just fine on a linked list, as long as you broaden your view beyond the common array-based implementations. See "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I would recommend using a radix sort for linked lists in most situations (sorry for the C++, but it was handy...). 9-Mar-2001 Re: quicksort for linked list by Helge [EMAIL PROTECTED] > Manoj Sontakke wrote: > > > > Hi > > Sorry, these questions do not belog here but i could not find any > > better place. > > > > 1. Is quicksort on doubly linked list is implemented anywhere? I need it > > for sk_buff queues. > > I cannot see how the quicksort algorithm could work on a doubly > linked list, as it relies on being able to look > up elements directly as in an array. > > You can probably find algorithms for sorting a linked list, but > it won't be quicksort. It's quicksort as long as you do pivot/split, the array gymnastics that most implementations do to avoid updating array elements isn't really critical to its operation. > 1. find out how many elements there are. (Count them if necessary) > 2. Allocate a pointer array of this size. > 3. fill the pointer array with pointers to list members. > 4. quicksort the pointer array > 5. Traverse the pointer array and set the links for each >list member to point to next/previous element pointed >to by the array. Now you have a sorted linked list! I think a radix sort like the following would work better with about the same (or less) storage, provided you're comparing ints (this is for a kernel modification after all, right?). You just need to determine the number of passes to cover all the bits in the numbers you want to sort. - Jim Bruce #define RADIX_BITS 6 #define RADIX (1 << RADIX_BITS) #define RADIX_MASK (RADIX - 1) struct item *radix_sort(struct item *list,int passes) // Sort list, largest first { struct item *tbl[RADIX],*p,*pn; int slot,shift; int i,j; // Handle trivial cases if(!list || !list->next) return(list); // Initialize table for(j=0; jnext; slot = ((p->key) >> shift) & RADIX_MASK; p->next = tbl[slot]; tbl[slot] = p; p = pn; } // integrate back into partially ordered list list = NULL; for(j=0; jnext; p->next = list; list = p; p = pn; } } } // fix prev pointers in list list->prev = NULL; p = list; while(pn = p->next){ pn->prev = p; p = pn; } return(list); } - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Manoj Sontakke wrote: > > Hi > Sorry, these questions do not belog here but i could not find any > better place. > > 1. Is quicksort on doubly linked list is implemented anywhere? I need it > for sk_buff queues. I cannot see how the quicksort algorithm could work on a doubly linked list, as it relies on being able to look up elements directly as in an array. You can probably find algorithms for sorting a linked list, but it won't be quicksort. You can however quicksort the list _if_ you have room enough for an additional data structure: 1. find out how many elements there are. (Count them if necessary) 2. Allocate a pointer array of this size. 3. fill the pointer array with pointers to list members. 4. quicksort the pointer array 5. Traverse the pointer array and set the links for each list member to point to next/previous element pointed to by the array. Now you have a sorted linked list! Steps 1,2,3 & 5 are all O(n), better than the O(nlgn) for quicksort. Helge Hafting - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Manoj Sontakke wrote: Hi Sorry, these questions do not belog here but i could not find any better place. 1. Is quicksort on doubly linked list is implemented anywhere? I need it for sk_buff queues. I cannot see how the quicksort algorithm could work on a doubly linked list, as it relies on being able to look up elements directly as in an array. You can probably find algorithms for sorting a linked list, but it won't be quicksort. You can however quicksort the list _if_ you have room enough for an additional data structure: 1. find out how many elements there are. (Count them if necessary) 2. Allocate a pointer array of this size. 3. fill the pointer array with pointers to list members. 4. quicksort the pointer array 5. Traverse the pointer array and set the links for each list member to point to next/previous element pointed to by the array. Now you have a sorted linked list! Steps 1,2,3 5 are all O(n), better than the O(nlgn) for quicksort. Helge Hafting - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Quicksort works just fine on a linked list, as long as you broaden your view beyond the common array-based implementations. See "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I would recommend using a radix sort for linked lists in most situations (sorry for the C++, but it was handy...). 9-Mar-2001 Re: quicksort for linked list by Helge [EMAIL PROTECTED] Manoj Sontakke wrote: Hi Sorry, these questions do not belog here but i could not find any better place. 1. Is quicksort on doubly linked list is implemented anywhere? I need it for sk_buff queues. I cannot see how the quicksort algorithm could work on a doubly linked list, as it relies on being able to look up elements directly as in an array. You can probably find algorithms for sorting a linked list, but it won't be quicksort. It's quicksort as long as you do pivot/split, the array gymnastics that most implementations do to avoid updating array elements isn't really critical to its operation. 1. find out how many elements there are. (Count them if necessary) 2. Allocate a pointer array of this size. 3. fill the pointer array with pointers to list members. 4. quicksort the pointer array 5. Traverse the pointer array and set the links for each list member to point to next/previous element pointed to by the array. Now you have a sorted linked list! I think a radix sort like the following would work better with about the same (or less) storage, provided you're comparing ints (this is for a kernel modification after all, right?). You just need to determine the number of passes to cover all the bits in the numbers you want to sort. - Jim Bruce #define RADIX_BITS 6 #define RADIX (1 RADIX_BITS) #define RADIX_MASK (RADIX - 1) struct item *radix_sort(struct item *list,int passes) // Sort list, largest first { struct item *tbl[RADIX],*p,*pn; int slot,shift; int i,j; // Handle trivial cases if(!list || !list-next) return(list); // Initialize table for(j=0; jRADIX; j++) tbl[j] = NULL; for(i=0; ipasses; i++){ // split list into buckets shift = RADIX_BITS * i; p = list; while(p){ pn = p-next; slot = ((p-key) shift) RADIX_MASK; p-next = tbl[slot]; tbl[slot] = p; p = pn; } // integrate back into partially ordered list list = NULL; for(j=0; jRADIX; j++){ p = tbl[j]; tbl[j] = NULL; // clear out table for next pass while(p){ pn = p-next; p-next = list; list = p; p = pn; } } } // fix prev pointers in list list-prev = NULL; p = list; while(pn = p-next){ pn-prev = p; p = pn; } return(list); } - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Quicksort works just fine on a linked list, as long as you broaden your view beyond the common array-based implementations. See "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I would recommend using a radix sort for linked lists in most situations (sorry for the C++, but it was handy...). In a network environment however its not so good. Quicksort has an N^2 worst case and the input is controlled by a potential enemy. Im dubious about anyone doing more than simple bucket sorting for packets. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
Helge Hafting wrote: Manoj Sontakke wrote: Hi Sorry, these questions do not belog here but i could not find any better place. 1. Is quicksort on doubly linked list is implemented anywhere? I need it for sk_buff queues. I cannot see how the quicksort algorithm could work on a doubly linked list, as it relies on being able to look up elements directly as in an array. It took me a few moments to realize, but quicksort is one algorithm that DOES NOT rely on directly accessing array elements. qsort (items) { if (numberof (items) = 1) return. pivot = chose_pivot (items) for (all items) if (curitem pivot) put on the left of pivot else put on the right of pivot qsort (items on the left of pivot); qsort (items on the right of pivot); } All operations are easily done on lists, not only on arrays. Actually, the array-implementation has a few thingies to avoid having to move the half the array on the scan of one item. With a list that is not an issue. If you know how you chose your pivot, one of the "puts" can be nil. (for example, chose the pivot as the leftmost item. All other items are already on the right. So "put on the left of pivot" is "unlink (curitem), relink_to_the_left (pivot, curitem)", but put on the right is "/* nothing to be done */". Quicksort however is an algorithm that is recursive. This means that it can use unbounded amounts of stack - This is not for the kernel. Quicksort however is an algorithm that is good for large numbers of elements to be sorted: the overhead of a small set of items to sort is very large. Is the "normal" case indeed "large sets"? Quicksort has a very bad "worst case": quadratic sort-time. Are you sure this won't happen? Isn't it easier to do "insertion sort": Keep the lists sorted, and insert the item at the right place when you get the new item. Roger. -- ** [EMAIL PROTECTED] ** http://www.BitWizard.nl/ ** +31-15-2137555 ** *-- BitWizard writes Linux device drivers for any device you may have! --* * There are old pilots, and there are bold pilots. * There are also old, bald pilots. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
In article [EMAIL PROTECTED] you write: Quicksort however is an algorithm that is recursive. This means that it can use unbounded amounts of stack - This is not for the kernel. Maybe a heapsort, then. It is guaranteed O(n*log n), even for worst case, and non-recursive. Yet it implies a significantly larger amount of comparisons than quicksort (about twice, I think). Insertion sort will be better anyway for small sets of data (for 5 or less elements). --Thomas Pornin - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, Mar 09, 2001 at 01:08:57PM +0530, Manoj Sontakke wrote: Hi Sorry, these questions do not belog here but i could not find any better place. 1. Is quicksort on doubly linked list is implemented anywhere? I need it for sk_buff queues. I would suggest that you use merge sort. It is ideally suited for sorting linked lists, and it always has N log N running time. I dont know of an existing implementation in the kernel sources, but it should be easy to write one. I did a google search on "merge sort" "linked list" and it comes up with lots of links. Here is a good one: http://www.ddj.com/articles/1998/9805/9805p/9805p.htm?topic=java Hope this helps, Jim - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, 9 Mar 2001, Helge Hafting wrote: Manoj Sontakke wrote: 1. Is quicksort on doubly linked list is implemented anywhere? I need it for sk_buff queues. I cannot see how the quicksort algorithm could work on a doubly linked list, as it relies on being able to look up elements directly as in an array. You can probably find algorithms for sorting a linked list, but it won't be quicksort. Here ya go (wrote this a few years ago): // This function is so cool. templateclass T void listT::qsort(iter l, iter r, cmpfunc *cmp, void *data) { if(l==r) return; iter i(l), p(l); for(i++; i!=r; i++) if(cmp(*i, *l, data)0) i.swap(++p); l.swap(p); qsort(l, p, cmp, data); qsort(++p, r, cmp, data); } Iters are essentially list pointers with increment operations. This is a fairly direct adaptation of the quicksort in KR, actually. -- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, 9 Mar 2001, Alan Cox wrote: Quicksort works just fine on a linked list, as long as you broaden your view beyond the common array-based implementations. See "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I would recommend using a radix sort for linked lists in most situations (sorry for the C++, but it was handy...). In a network environment however its not so good. Quicksort has an N^2 worst case and the input is controlled by a potential enemy. It's not too hard to patch that up, eg quickersort. N^2 isn't too bad for short queues anyway especially considering the complexity of the alternatives. Im dubious about anyone doing more than simple bucket sorting for packets. Assume you mean sorting into hash buckets as opposed to "count the number of occurrences of each type of element in a narrow range, discarding the actual element". Most hashes are subvertible too and probably don't fair any better than N^2. -- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, 9 Mar 2001, Rogier Wolff wrote: Quicksort however is an algorithm that is recursive. This means that it can use unbounded amounts of stack - This is not for the kernel. It is of course bounded by the input size, but yes, it can use O(n) additional memory in the worst case. There's no particular reason this memory has to be on the stack - it's just convenient. Isn't it easier to do "insertion sort": Keep the lists sorted, and insert the item at the right place when you get the new item. Assuming you get your items in sorted order, this is also O(N^2). -- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: quicksort for linked list
On Fri, Mar 09, 2001 at 12:52:22PM +0100, Rogier Wolff wrote: Quicksort however is an algorithm that is recursive. This means that it can use unbounded amounts of stack - This is not for the kernel. Well, not really in this situation, after a simple modification. It is trivial to show that using "shorter interval sorted first" approach one can bound an amount of an extra memory, on stack or otherwise, and by a rather small number. This assumes that one knows what one is sorting - which is obviously the case here. Also my copy of Reingold, Nivergelt, Deo from 1977 presents a "non-recursive" variant of quicksort as a kind of an "old hat" solution. One would think that this piece of information would spread during those years. :-) It is a simple exercise anyway. Quicksort has a very bad "worst case": quadratic sort-time. Are you sure this won't happen? This is much more serious objection. You can nearly guarantee in an itended application that somebody will find a way to feed you packets which will ensure the worst case behaviour. The same gotcha will probably kill quite a few other ways to sort here. Michal - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/