Proposal #3271: new methods for Data.Sequence

[Louis Wasserman]

Ross, fromList2 takes perhaps 3ms off the time when n=50000.  (It is
essentially a two-liner, so I consider this acceptable.)

Nevertheless, I have slightly improved the performance of the stable
heapsort; essentially, when labeling values with their index, the index is
left as a lazy thunk, but the computation is organized so computing any
index takes O(log n).  The speed increase from fromList . Data.List.sort .
toList is still but 40% of the speed increase from the heapsort.

Again, I'd like to propose a compromise: make Data.Sequence.sortBy cmp be
either fromList2 . Data.List.sortBy cmp . toList, or use the stable
pairing-heap sort, and add a second sorting method, sortBy', that is
unstable but faster.

Times (ms)
                       min      mean    +/-sd    median    max
to/from list:        113.561  119.800    5.470  118.678  139.390
pairing heap:         62.440   67.032    3.861   65.174   80.499
stable pheap:         93.402  102.253   11.854   98.529  158.922
fromList2 . toList:  110.221  118.364    6.525  116.265  136.683

Louis Wasserman
wasserman.louis at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20090719/32b21309/attachment.html