Author 
Message 
cripp #1 / 17

"Lazy"sort ?!
Hi, I have an open question conserning sorting in general. Is there a data structure with which it would be possible, or rather fruitfull, to do the sorting in a kind a lazy way ? In pseudo code it could be like: A = my_lazy_ADT:new([5,2,4,1,3]) > [1, UnsortedTail_1] head(A) > 1 B = tail(A) > [2, UnsortedTail_2} ...and so on. If we consider lists maybe this is one kind of implementaion: (see further at http://www.***.com/ ) module(lazy_list). export([sort/1]). sort([]) > []; sort([HT]) > sort(H, T, [], [H]). sort(A, [BT], WithoutMin, WithMin) when A < B > sort(A, T, [BWithoutMin], [BWithMin]); sort(A, [BT], WithoutMin, WithMin) when A >= B > sort(B, T, WithMin, [BWithMin]); sort(A, [], WithoutMin, WithMin) > [AWithoutMin]. new(L) when list(L) > sort(L). head([HT]) > H. tail([HT]) > sort(T). This will give O(t) for each tail/1 operation, where t is the number of element at the time for the operation. And my guess for the amortized cost is O(sqrt(n)) (correct me on that one). In other words, this doesn't look too good, right. But maybe one could extended the implementation above to perform some bubble sort(or simular) during the list traverse. And after some tail/1 operations we will know that the ListTail is sorted. Any thoughts about this ? /Christofer  Christofer T?rnkvist Phone: +46 8 727 57 52 Ericsson Utveckling AB Fax:  Software Architecture Lab. http://www.***.com/


Sat, 09 Mar 2002 03:00:00 GMT 


Lars Lundgre #2 / 17

"Lazy"sort ?!
Quote:
> Hi, > I have an open question conserning sorting in general. > Is there a data structure with which it would be possible, or rather > fruitfull, to do the sorting in a kind a lazy way ?
Yes of course, try the List data structure '[a]' in haskell, or any data structure in haskell for that matter. Isn't it fun to write minimum xs = head (sort xs) and get an efficient implementation of minimum? /Lars L

Sat, 09 Mar 2002 03:00:00 GMT 


George Russel #3 / 17

"Lazy"sort ?!
Quote:
> Hi, > I have an open question conserning sorting in general. > Is there a data structure with which it would be possible, or rather > fruitfull, to do the sorting in a kind a lazy way ?
Easypeasy. You obviously need O(n) time to get the lowest item out, since you need to check all the items. So the best you can hope for is O(n) for the first one, and O(log n) for all the others. So use heap sort or balanced trees, both of which manage that. Can't be bothered to code them now though . . .

Sat, 09 Mar 2002 03:00:00 GMT 


cripp #4 / 17

"Lazy"sort ?!
Quote:
> > Hi, > > I have an open question conserning sorting in general. > > Is there a data structure with which it would be possible, or rather > > fruitfull, to do the sorting in a kind a lazy way ? > Easypeasy. You obviously need O(n) time to get the lowest item out, > since you need to check all the items. So the best you can hope for > is O(n) for the first one, and O(log n) for all the others. > So use heap sort or balanced trees, both of which manage that. > Can't be bothered to code them now though . . .
Ok, so there is nothing to gain here as far as complexity is concerned. Only for small sizes of data there might be possible to save some time, though. Probably a too small time save. BTW: Using a heap the first element is picked in O(nlog(n)) as you create (sort) the heap, and then the rest at O(log(n)). The latter expression is settled by the deleteMin operation. Best Regards /Christofer  Christofer T?rnkvist Phone: +46 8 727 57 52 Ericsson Utveckling AB Fax:  Software Architecture Lab. http://wwwsarc.ericsson.se/public


Sun, 10 Mar 2002 03:00:00 GMT 


Martin Norb{ #5 / 17

"Lazy"sort ?!
Quote: > BTW: Using a heap the first element is picked in O(nlog(n)) as you > create (sort) the heap, and then the rest at O(log(n)). > The latter expression is settled by the deleteMin operation.
You don't sort the elements when creating a heap. A heap only has a heap ordering between the elements. You can actually build a heap in O(n) time. The build function uses inplace updates, however. Picking the first element is O(log n), so finding the first element using a heap is O(n)+O(log n) = O(n). (btw, finding the first element in a well coded merge sort is also O(n)) n.  [ http://www.dtek.chalmers.se/~d95mback/ ] [ PGP: 0x453504F1 ] [ UIN: 4439498 ] Opinions expressed above are mine, and not those of my future employees.

Sun, 10 Mar 2002 03:00:00 GMT 


cripp #6 / 17

"Lazy"sort ?!
Quote:
> > BTW: Using a heap the first element is picked in O(nlog(n)) as you > > create (sort) the heap, and then the rest at O(log(n)). > > The latter expression is settled by the deleteMin operation. > You don't sort the elements when creating a heap. A heap only has a heap > ordering between the elements. You can actually build a heap in O(n) time. > The build function uses inplace updates, however.
Are you saying that you can sort in O(n) using a heap ?! Quote: > Picking the first element is O(log n), so finding the first element > using a heap is O(n)+O(log n) = O(n). > (btw, finding the first element in a well coded merge sort is also O(n)) > n. >  > [ http://www.dtek.chalmers.se/~d95mback/ ] [ PGP: 0x453504F1 ] [ UIN: 4439498 ] > Opinions expressed above are mine, and not those of my future employees.
Best Regards /Christofer  Christofer T?rnkvist Phone: +46 8 727 57 52 Ericsson Utveckling AB Fax:  Software Architecture Lab. http://wwwsarc.ericsson.se/public


Sun, 10 Mar 2002 03:00:00 GMT 


Martin Norb{ #7 / 17

"Lazy"sort ?!
Quote: > > You don't sort the elements when creating a heap. A heap only has a heap > > ordering between the elements. You can actually build a heap in O(n) time. > > The build function uses inplace updates, however. > Are you saying that you can sort in O(n) using a heap ?!
Nope. The heap takes O(n) to build, but to sort you need to remove n elements at O(log n) a piece, giving you sorting in O(n log n). Finding the smallest element can be done in O(n) though. Just build and pop the top element. n.  [ http://www.dtek.chalmers.se/~d95mback/ ] [ PGP: 0x453504F1 ] [ UIN: 4439498 ] Opinions expressed above are mine, and not those of my future employees.

Sun, 10 Mar 2002 03:00:00 GMT 


John Prevos #8 / 17

"Lazy"sort ?!
Quote:
> Are you saying that you can sort in O(n) using a heap ?! > > Picking the first element is O(log n), so finding the first element > > using a heap is O(n)+O(log n) = O(n).
No, he's saying that you can get the first element of a sort in O(n) time. Compare with searching an entire list sequentially for the minimum, also O(n) time. In fact, it's only because all subsequent steps in the heap sort cost only O(log n) that you get O(n log n). If this behavior happened all the time, you'd lost and get O(n^2). The lazy win, of course, is that if you only want the first 5 elements, the cost is O(n) + O(5 log n) = O(n)so getting the first m items of a sorted list is O(m log n) if m and n vary independently, and O(n) if m is held constant. In any case, that means you didn't do as much work as you would've to build the whole sorted rep in memory. John.

Sun, 10 Mar 2002 03:00:00 GMT 


Adam P. Jenki #9 / 17

"Lazy"sort ?!
Quote:
> > You don't sort the elements when creating a heap. A heap only has a heap > > ordering between the elements. You can actually build a heap in O(n) time. > > The build function uses inplace updates, however. > Are you saying that you can sort in O(n) using a heap ?!
No. A heap doesn't store it's elements in sorted order. The only guarantee you get from a heap is that the greatest element in the heap is always at the top. Creating the initial heap from an unsorted list takes O(n) time. Each time you remove the greatest element, the heap needs to be "reheapified", which takes O(log n) time. A heapsort works by first heapifying the list, which takes O(n) time, and then removing the max element repeatedly until the list is empty, which takes O(n log n) time. So heapsort takes O(n) + O(n log n) == O(n log n) time.  Adam P. Jenkins

Sun, 10 Mar 2002 03:00:00 GMT 


cripp #10 / 17

"Lazy"sort ?!
Quote:
> > > You don't sort the elements when creating a heap. A heap only has a heap > > > ordering between the elements. You can actually build a heap in O(n) time. > > > The build function uses inplace updates, however. > > Are you saying that you can sort in O(n) using a heap ?! > Nope. The heap takes O(n) to build, but to sort you need to remove n > elements at O(log n) a piece, giving you sorting in O(n log n). > Finding the smallest element can be done in O(n) though. Just build and > pop the top element. > n. >  > [ http://www.dtek.chalmers.se/~d95mback/ ] [ PGP: 0x453504F1 ] [ UIN: 4439498 ] > Opinions expressed above are mine, and not those of my future employees.
Ok I'm with you. Fascinating, I've never reflected upon this fact. And more surprising is that no litterature I come across pinpoint this (explicitly enough:). To select a sorting method we may not just look at the O(.) complexity for time and space and the amount of data to sort. We must also consider how we are going to use the sorted data. The heap sort now seems to be a good, if not the best, choice for a lazy style sorting. Thanks for some good answers! Best Regards /Christofer  Christofer T?rnkvist Phone: +46 8 727 57 52 Ericsson Utveckling AB Fax:  Software Architecture Lab. http://wwwsarc.ericsson.se/public


Mon, 11 Mar 2002 03:00:00 GMT 


Jerzy Karczmarczu #11 / 17

"Lazy"sort ?!
Christofer T?rnkvist commenting Martin Norb?ck: Quote: > > > Are you saying that you can sort in O(n) using a heap ?! > > Nope. The heap takes O(n) to build, but to sort you need to remove n > > elements at O(log n) a piece, giving you sorting in O(n log n). > > Finding the smallest element can be done in O(n) though. Just build and > > pop the top element. > > n. > Ok I'm with you. Fascinating, I've never reflected upon this fact. > And more surprising is that no litterature I come across pinpoint this > (explicitly enough:). To select a sorting method we may not just look > at the O(.) complexity for time and space and the amount of data to sort. > We must also consider how we are going to use the sorted data. > The heap sort now seems to be a good, if not the best, choice for a > lazy style sorting. Thanks for some good answers! > /Christofer
Would you mind *showing* a (lazy functional) implementation of the heapsort where the heap construction time is O(N)? The construction + the evaluation of the first element, of course. I probably miss some crucial trick here, but *please, don't explain, but show the implementation*. BTW. A week ago I posted some silly benchmarks, forgetting about the laziness... I apologize. So, my numbers actually yielded what some of you wanted here  the access to the first element, and not the overall sorting complexity. The insertion sort is a good candidate, it is O(N), although we have to pay first the construction of the comparison/construction thunk of length N, and then its evaluation. But it wins with the quicksort, and with a binary treesort where the insertions proceed down from the root. Full sorting is another story. This treesort seems to win (very slightly, and for large N) with the qsort both for the 1st element access and for the full sorting, but if you don't like the no. of reductions in Hugs as a reasonable criterion, inshallah... Well implemented heapsort should be better, because the tree is almost balanced (complete), and the percolation down for the heap fixing is O(logN) only for the root and then geometrically descends, making the fix O(N), this is a known theory, see e.g. http://www.engr.orst.edu/~reichwja/cs261/lecture/priq/sld013.htm but I still wait to see a good functional implementation, useful e.g. for the priority queues... ///No! Parole d'honneur, this is not my homework!/// ] Jerzy Karczmarczuk Caen, France.

Mon, 11 Mar 2002 03:00:00 GMT 


cripp #12 / 17

"Lazy"sort ?!
Quote:
> Christofer T?rnkvist commenting Martin Norb?ck: > > > > Are you saying that you can sort in O(n) using a heap ?! > > > Nope. The heap takes O(n) to build, but to sort you need to remove n > > > elements at O(log n) a piece, giving you sorting in O(n log n). > > > Finding the smallest element can be done in O(n) though. Just build and > > > pop the top element. > > > n. > > Ok I'm with you. Fascinating, I've never reflected upon this fact. > > And more surprising is that no litterature I come across pinpoint this > > (explicitly enough:). To select a sorting method we may not just look > > at the O(.) complexity for time and space and the amount of data to sort. > > We must also consider how we are going to use the sorted data. > > The heap sort now seems to be a good, if not the best, choice for a > > lazy style sorting. Thanks for some good answers! > > /Christofer > Would you mind *showing* a (lazy functional) implementation of > the heapsort where the heap construction time is O(N)? > The construction + the evaluation of the first element, of course. > I probably miss some crucial trick here, but *please, don't explain, > but show the implementation*.
I guess the term lazy doesn't fit for the heap sorting. Look at the my first posting and maybe you'll understand. With lazy I meant that at the time for start picking the sorted elements you have not allready consumed the O(nlog(n)) time complexity. For ideas on how to implement this see the bible "Purely Functional Data Structures" by Okasaki. ... Quote: > Jerzy Karczmarczuk > Caen, France.
Best Regards /Christofer  Christofer T?rnkvist Phone: +46 8 727 57 52 Ericsson Utveckling AB Fax:  Software Architecture Lab. http://wwwsarc.ericsson.se/public


Mon, 11 Mar 2002 03:00:00 GMT 


Chris Okasa #13 / 17

"Lazy"sort ?!
Quote: >Would you mind *showing* a (lazy functional) implementation of >the heapsort where the heap construction time is O(N)? >The construction + the evaluation of the first element, of course. >I probably miss some crucial trick here, but *please, don't explain, >but show the implementation*.
See Richard Bird's "Functional Algorithm Design" in Science of Computer Programming (Vol 26/Num 13), May 1996. The essential ideas are as follows (I know this is explain rather than showing the implementation, contrary to your request, but oh well...) 1. Take half the elements and create singleton trees 2. Repeat until only a single tree remains a. take two trees and an element b. combine into a new tree with the element at the root and the two trees as subtrees c. while the element is larger than one of its children, sift it down to the right location If you maintain the trees in a FIFO queue, then at step 2a you will always be combining the two smallest trees. If there are a total of 2^k1 elements, then you will end up with a perfectly balanced heap ordered tree. Otherwise, you will probably have to play a little bit with the order in which you process the elements to maintain whatever kind of balance criteria you require for your heap (probably some form of Braun tree?). If you use fancier kinds of heaps, then it is even easier to get the O(n) time bound for heap construction. For example, for binomial heaps or skew binomial heaps (or any other kind of heap where insertion takes O(1) time), you can just insert all the elements, one by one. For leftist heaps or skew heaps (or any other kind of heap where merge takes O(log n) time), you first place all the elements in singleton heaps, and then repeatedly merge the elements in pairs until only a single heap remains. Chris

Mon, 11 Mar 2002 03:00:00 GMT 


Jerzy Karczmarczu #14 / 17

"Lazy"sort ?!
Chris Okasaki on heapsorts: Quote: > See Richard Bird's "Functional Algorithm Design" in Science of > Computer Programming (Vol 26/Num 13), May 1996. > The essential ideas are as follows (I know this is explain rather > than showing the implementation, contrary to your request, but > oh well...) > 1. Take half the elements and create singleton trees > 2. Repeat until only a single tree remains > a. take two trees and an element > b. combine into a new tree with the element at the > root and the two trees as subtrees > c. while the element is larger than one of its children, sift it down > to the right location > If you maintain the trees in a FIFO queue, ...
etc. Ok, Ok, I believe all of you. I might even add another quotation of Chris Okasaki, his answer to Jon Fairbarn on the Haskell list, October 1997: * But the heapsort you give is nothing like the standard imperative * heapsort! Yes, it uses a heap, but not the binary heap used by * standard heapsort. Instead, it uses the functional equivalent * of multipass pairing heaps[1]. Larry Paulson's "ML for the * Working Programmer" includes a functional heapsort that is * much closer in spirit to the standard imperative version, and * so is probably superior for pedagogical purposes. (Although I expect * that your version will be much faster in practice.) * Chris * [1] Fredman, Sedgewick, Sleator, and Tarjan. * "The pairing heap: A new form of selfadjusting heap" * Algorithmica 1(1):111129, 1986. ======================= Very nice. ... But I would like anyway to see a nice, practical code in a lazy functional language. Just for pleasure, without any bad thoughts. Thank you. Jerzy Karczmarczuk Caen, France.

Mon, 11 Mar 2002 03:00:00 GMT 


Page 1 of 2

[ 17 post ] 

Go to page:
[1]
[2] 
1. "Lazy" compile with dope vectors
2. "definition" rather than assignment (lazy evaluation)
3. "lazy evaluation" help
4. string.join(["Tk 4.2p2", "Python 1.4", "Win32", "free"], "for")
5. sort "items" paragraphwise
6. SORTS and "I"  pt3
7. SORTS and "I"  pt2
8. problem with "sorting" in tcl
9. BEGIN{want[]={"s1o", "s2o", "s2q", "s3q"}
10. Parsing ""D""?
11. "Fifth", "Forth", zai nar?
12. Ruby "finalize", "__del__"


