Bubble sort algorithm implementations (Haskell vs. C)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Bubble sort algorithm implementations (Haskell vs. C)

Yasir Arsanukaev
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
Reply | Threaded
Open this post in threaded view
|

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

caseyh
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
Reply | Threaded
Open this post in threaded view
|

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

Mark Lentczner
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
Reply | Threaded
Open this post in threaded view
|

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

Felipe Lessa
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
Reply | Threaded
Open this post in threaded view
|

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

Yasir Arsanukaev
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
Reply | Threaded
Open this post in threaded view
|

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

Felipe Lessa
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
Reply | Threaded
Open this post in threaded view
|

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

Yasir Arsanukaev
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