Hello. I have written 2 implementation of bubble sort algorithm in C
and Haskell. Haskell implementation: module Main where main = do contents <- readFile "./data" print "Data loaded. Sorting.." let newcontents = bubblesort contents writeFile "./data_new_ghc" newcontents print "Sorting done" bubblesort list = sort list [] False rev = reverse -- separated. To see rev2 = reverse -- who calls the routine sort (x1:x2:xs) acc _ | x1 > x2 = sort (x1:xs) (x2:acc) True sort (x1:xs) acc flag = sort xs (x1:acc) flag sort [] acc True = sort (rev acc) [] False sort _ acc _ = rev2 acc I've compared these two implementations having run both on file with size of 20 KiB. C implementation took about a second, Haskell — about 1 min 10 sec. I have also profiled the Haskell application: Compile for profiling: C:\Temp> ghc -prof -auto-all -O --make Main Profile: C:\Temp> Main.exe +RTS -p and got these http://hpaste.org/fastcgi/hpaste.fcgi/view?id=24190#a24190 This is a pseudocode of the algorithm: procedure bubbleSort( A : list of sortable items ) defined as: do swapped := false for each i in 0 to length(A) - 2 inclusive do: if A[i] > A[i+1] then swap( A[i], A[i+1] ) swapped := true end if end for while swapped end procedure 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. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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 |
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 |
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 |
Felipe Lessa <felipe.lessa <at> 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 |
On Mon, Mar 22, 2010 at 01:08:39AM +0000, kingping wrote:
> Here's my C implementation: > http://hpaste.org/fastcgi/hpaste.fcgi/view?id=24191#a24191 I don't know how much difference in time there would be, but you should use lists in C and/or mutable arrays in Haskell, otherwise you are comparing apples to oranges. Comparision of algorithms should use the same data structures, unless you're asking for a comparision of "idiomatic" implementations. Cheers, -- Felipe. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Felipe Lessa <felipe.lessa <at> gmail.com> writes:
> > On Mon, Mar 22, 2010 at 01:08:39AM +0000, kingping wrote: > > Here's my C implementation: > > http://hpaste.org/fastcgi/hpaste.fcgi/view?id=24191#a24191 > > I don't know how much difference in time there would be, but you > should use lists in C and/or mutable arrays in Haskell, otherwise > you are comparing apples to oranges. Comparision of algorithms > should use the same data structures, unless you're asking for a > comparision of "idiomatic" implementations. Yes, you're right. However then I'd like to ask what would suit my needs better Data.Vector, Data.Array or something other. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |