[note, the thread is almost a month old]
Bernie Pope wrote:
>
> On 23/10/2007, at 8:09 AM, Thomas Hartman wrote:
>>
>> (Prelude sort, which I think is mergesort, just blew the stack.)
>
> GHC uses a "bottom up" merge sort these days.
>
> It starts off by creating a list of singletons, then it repe
On 10/23/07, Thomas Hartman <[EMAIL PROTECTED]> wrote:
>
>
> Actually I can't compile it, with or without -O2. loads fine into ghci,
> but when I try to create an executable I get
>
> ghc quicksort.hs -o quicksort
> quicksort.o: In function `r1Nc_info': undefined reference to
> `QuickCheckzm1zi0zi1
It has been noted in a few places that the 2 line quicksort demo in the
Introduction section of the haskell wiki
http://www.haskell.org/haskellwiki/Introduction
isn't a "real" quicksort, and wouldn't scale well with longer lists.
Interested, and wanting to put my recently learned test data gener
Bernie Pope wrote:
>
> On 23/10/2007, at 8:09 AM, Thomas Hartman wrote:
>>
>>
>> (Prelude sort, which I think is mergesort, just blew the stack.)
>
> GHC uses a "bottom up" merge sort these days.
>
> It starts off by creating a list of singletons, then it repeatedly merges
> adjacent pairs of list
[EMAIL PROTECTED] writes:
> 1. Avoid two pass filtering.
> 2. Avoid unecessary (++), with an accumulator. For example:
Also, I find that
3. Accumulate equal elements, too
pa (y:ys) s e b = case compare x y of ...
to be a good choice. Otherwise, quicksort easily grows towards
quadratic i
On 23/10/2007, at 8:09 AM, Thomas Hartman wrote:
(Prelude sort, which I think is mergesort, just blew the stack.)
GHC uses a "bottom up" merge sort these days.
It starts off by creating a list of singletons, then it repeatedly
merges adjacent pairs of lists until there
is only one list l
> I wonder if there are "tricks" or lore that could be applied to get better
> results or insight.
>
> t.
Just a quick note, I doubt ghc -e does any optimizations. You'd probably
get better results by putting these tests in files and compiling with -O2.
In particular I wonder whether that would
Thomas Hartman writes:
another point: "deforested" treesort is slower.
The commented indicated that
-- If you deforest this algorithm (removing the intermediate tree
structure) you are left with
treeSort' [] = []
treeSort' (x:xs) = treeSort' (filter (<= x) xs) ++ [x] ++ treeSort'
(filter (
another point: "deforested" treesort is slower.
[EMAIL PROTECTED]:~/ProjectRepos/learning/quicksort>time ghc -e "test
treeSort' 6" quicksort
100
real4m3.615s
user1m59.525s
sys 0m0.587s
The commented indicated that
-- If you deforest this algorithm (removing the intermediate tr
It has been noted in a few places that the 2 line quicksort demo in the
Introduction section of the haskell wiki
http://www.haskell.org/haskellwiki/Introduction
isn't a "real" quicksort, and wouldn't scale well with longer lists.
Interested, and wanting to put my recently learned test data gen
10 matches
Mail list logo
