#load "unix.cma" ;; #use "sieb-ML.ml" ;; (* calc_limit gibt an, bis zu welcher Hoehe Primzahlen im Benchmark berechnet werden sollen *) let calc_limit = 10000 ;; (* Anhaengen eines einzelnen Elements "vorn" via "::" ist zeiteffizienter als Listenkonkatenation "@" - dann muss allerdings die Reihenfolge der Elemente geaendert werden, sprich Dekrementieren der Laufvariable, statt Inkrementieren wie in der originalen genlist. Der Laufzeitunterschied zwischen den Operationen "::" und "@" ist ERHEBLICH! *) let genlist2 = let rec genlist_aux acc k n = if k >= n then genlist_aux (k::acc) (k-1) n else acc in genlist_aux [] ;; (* Ein weiteres interessantes Merkmal der geringeren Platzkomplexitaet von genlist2 ist die Tatsache, dass sich damit auch Listen einer Laenge von 1.000.000 (1 Million) erzeugen lassen, waehrend bei Benutzung von genlist bereits bei einer Listenlaenge von ca. 53.000 der Stack ueberlaeuft (!). *) let allnums2 n = genlist2 n 2 ;; let rev_clever = let rec rc acc = function [] -> acc | h::t -> rc (h::acc) t in rc[] let rest2 = let rec rest_aux acc k l = match l with [] -> rev_clever acc | h::t when h mod k = 0 -> rest_aux acc k t | h::t -> rest_aux (h::acc) k t in rest_aux [] ;; let sieve2 = let rec sieve_aux acc = function [] -> rev_clever acc | h::t -> sieve_aux (h::acc) (rest2 h t) in sieve_aux [] ;; let primzahlen2 n = sieve2 (allnums2 n) ;; (* Profiler *) let profile f s = let before = Unix.gettimeofday () in let _ = f () in let after = Unix.gettimeofday () in print_string (s ^ ": " ^ string_of_float (after -. before) ^ " Sekunden.\n") ;; (* Benchmark : Vergleich mit der nicht endrekursiven Loesung *) profile (fun _ -> primzahlen calc_limit) "primzahlen" ;; profile (fun _ -> primzahlen2 calc_limit) "primzahlen2" ;; (* EOF *)