Ингар Р (wu_) wrote,
Ингар Р
wu_

Сравнение алгоритма Quicksort на C, OCaml, Haskell и Erlang


Для выбора используемого языка для проекта провёл небольшое экспресс-сравнение языков-кандидатов. Результаты ставлю также тут.


Критерии:
- скорость скомпилированного кода;
- размер скомпилированного кода

Сравнивал на:
- C (gcc version 4.6.3);
- OCaml (Objective Caml version 3.12.1);
- Haskell (Glasgow Haskell Compiler, Version 7.4.1);
- Erlang (Erlang R15B01, без HiPE)

в среде:
- Ubuntu Linux Release 12.04 (precise) 32-bit;
- Intel® Core™2 Duo CPU E8500 @ 3.16GHz × 2

Сравнивал алгоритм сортировки Quicksort. Размер массива данных - 10000 (int).


qs_c.c
#include <stdlib.h>  
#include <stdio.h>  
  
static void swap(void *x, void *y, size_t l) {  
   char *a = x, *b = y, c;  
   while(l--) {  
      c = *a;  
      *a++ = *b;  
      *b++ = c;  
   }  
}  
  
static void qsort8(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end) {  
   if (end > begin) {  
      void *pivot = array + begin;  
      int l = begin + size;  
      int r = end;  
      while(l < r) {  
         if (cmp(array+l,pivot) <= 0) {  
            l += size;  
         } else {  
            r -= size;  
            swap(array+l, array+r, size);  
         }  
      }  
      l -= size;  
      swap(array+begin, array+l, size);  
      qsort8(array, size, cmp, begin, l);  
      qsort8(array, size, cmp, r, end);  
   }  
}  
  
void qsort9(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) {  
   qsort8(array, size, cmp, 0, (nitems-1)*size);  
}  
  
typedef int type;  
  
int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); }  
  
main(){ /* simple test case for type=int */  
  int num_list[10000];  
  int len=sizeof(num_list)/sizeof(type);  
  char *sep="";  
  int i;  
  for(i=0; i<len; i++){  
    num_list[i]=10003-i;  
  }  
  qsort9(num_list,len,sizeof(type),type_cmp);  
  printf("sorted_num_list={");  
  for(i=0; i<len; i++){  
    printf("%s%d",sep,num_list[i]);  
    sep=", ";  
  }  
  printf("};\n");  
}


qs_ocaml.ml
let rec range i j = if i > j then [] else 10003-i :: (range (i+1) j)

let rec print_list = function 
    [] -> ()
    | e::l -> print_int e ; print_string " " ; print_list l
;;

let rec qsort list =
  match list with
  | [] -> []
  | [x] -> [x]
  | pivot::rest ->
      let rec partition left right list =
        match list with
        | [] -> qsort left @ (pivot :: qsort right)
        | head::tail -> if head <= pivot then partition (head::left) right tail
                                         else partition left (head::right) tail
      in partition [] [] rest;;


(** test **)
let a1 = range 1 10000;;
let a2 = qsort a1 ;;
print_list a2;;


qs_haskell.hs
partition:: (Ord a) => [a] -> a -> ([a],[a]) -> ([a],[a])

partition [] _ part = part -- base case

partition (x:xs) pivot (lesseq,greater) = 
  if x<= pivot then partition xs pivot (x:lesseq,greater)
               else partition xs pivot (lesseq,x:greater)

sort:: (Ord a) => [a] -> [a]
sort [] = []
sort (x:xs) = sort lesseq ++ [x] ++ sort greater where
  (lesseq,greater) = partition xs x ([],[])


qsort1 :: Ord a => [a] -> [a]
qsort1 []     = []
qsort1 (p:xs) = qsort1 lesser ++ [p] ++ qsort1 greater
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

main = print (sort([10000,9999..1]))


qs.erl
-module(qs).
-export([start/0]).

qsort([]) -> [];
qsort([X|Xs]) ->
    qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).

start() ->
    A = qsort(lists:seq(10000, 1, -1)),
    io:fwrite("~s",[io_lib:write(A)]),
    halt().


Скрипт:
erlc qs.erl
ocamlopt qs.ml -o qs_ocaml
ghc --make qs_haskell
gcc -O2 qs_c.c -o qs_c
strip -p --strip-unneeded --remove-section=.comment -o qs_ocaml_s qs_ocaml
strip -p --strip-unneeded --remove-section=.comment -o qs_haskell_s qs_haskell
strip -p --strip-unneeded --remove-section=.comment -o qs_c_s qs_c

time erl -s qs > out1
time ./qs_ocaml_s > out2
time ./qs_haskell_s > out3
time ./qs_c_s > out4

Результат:
real
time (s)
user
time (s)
sys
time (s)
exec
size (b)
time
(times of C)
exec size
(times of C)
C0.2010.2000.00054281.001.00
OCaml1.0491.0400.0041052045.2219.38
Haskell3.5483.3360.19657814817.65106.51
Erlang6.3104.5201.7001020*31.39374.52*
* plus/with Erlang runtime (2MB)
Tags: программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments