Bubble sort algorithm implementations (Haskell vs. C)

7 messages
Open this post in threaded view
|

Bubble sort algorithm implementations (Haskell vs. C)

Open this post in threaded view
|

Re: Bubble sort algorithm implementations (Haskell vs. C)

 You may want to use a mutable array. >The performance may suffer from the memory allocation for the list. I >wonder if it's possible to make Haskell implementation work faster >without changing the algorithm (there's are actually a few tricks to >make it work faster, but neither implementations have these >optimizations). >I'm interested not in particular algorithm performance but rather in >performance of its implementations in various languages. I compiled >the Haskell implementation in GHC (Haskell Platform 2009.2.0.2), which >is the latest available from the site. If you are interested in its performance in various languages you may want to implement the Bubble Sort the "best" way in each language. -- Regards, Casey _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

Re: Bubble sort algorithm implementations (Haskell vs. C)

 In reply to this post by Yasir Arsanukaev You might express the algorithm more directly in Haskell, without the reverse calls: bubblesort :: (Ord a) => [a] -> [a] bubblesort []      = [] bubblesort (x0:xs) = case bubble x0 xs of     (xs', True)  -> bubblesort xs'     (xs', False) -> xs'     where bubble x1 (x2:xs) | x1 <= x2  = merge x1 False \$ bubble x2 xs                             | otherwise = merge x2 True  \$ bubble x1 xs           bubble x1 []                  = ([x1], False)           merge x s (xs, s') = (x:xs, s || s') Here, the local bubble function does the job of bubbling a value through, and the merge function handles both rebuilding the new, bubbled list, and the swap flag. The case expression in bubblesort is a direct expression in Haskell of "bubble through the list once, and if we swapped anything, do it again". This version clocks in at about 35% faster than your original.         - Mark P.S.: Code and driver Main files can be found here:         http://bitbucket.org/mtnviewmark/haskell-playground/src/tip/cafe/Mark Lentczner http://www.ozonehouse.com/mark/IRC: mtnviewmark _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

Re: Bubble sort algorithm implementations (Haskell vs. C)

 In reply to this post by Yasir Arsanukaev On Sun, Mar 21, 2010 at 03:39:08PM +1000, Yasir Arsanukaev wrote: > I'm interested not in particular algorithm performance but rather in > performance of its implementations in various languages. Is your C program using lists or arrays?  These are different algorithms. -- Felipe. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

Re: Bubble sort algorithm implementations (Haskell vs. C)

 Felipe Lessa gmail.com> writes: > > On Sun, Mar 21, 2010 at 03:39:08PM +1000, Yasir Arsanukaev wrote: > > I'm interested not in particular algorithm performance but rather in > > performance of its implementations in various languages. > > Is your C program using lists or arrays?  These are different > algorithms. > > -- > Felipe. > Here's my C implementation: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=24191#a24191_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe