[Haskell-cafe] Re: (flawed?) benchmark : sort
Duncan Coutts
duncan.coutts at worc.ox.ac.uk
Mon Mar 10 00:05:34 EDT 2008
On Sun, 2008-03-09 at 23:04 -0400, Dan Doel wrote:
> On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote:
> > What do you think about this particular function?
>
> Some thoughts:
>
> 1) To get your function specifically, you could just use Data.Set.Set a
> instead of Map a ().
>
> 2) What does it do with duplicate elements in the list? I expect it deletes
> them. To avoid this, you'd need to use something like fromListWith, keeping
> track of how many duplicates there are, and expanding at the end.
>
> 3) I imagine the time taken to get any output is always O(n*log n). Various
> lazy sorts can be written (and I'd guess the standard library sort is written
> this way, although I don't know for sure) such that 'head (sort l)' is O(n),
> or O(n + k*log n) for getting the first k elements. However, Map, being a
> balanced binary tree, doesn't (I think) have the right characteristics for
> this.
Sounds to me like we should try a heap sort. As a data structure it
should have similar constant factors to Data.Map (or .Set) but a heap is
less ordered than a search tree and gives the O(n + k*log n) property.
Duncan
More information about the Haskell-Cafe
mailing list