Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web development, networking and server security. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

C++ protiv C# protiv F# protiv Haskell


29. Novemar 2009. 14:36 od Fila

Budući da sam ja prvi postavio F# rešenje za Left-Truncatable Primes , C# i Haskell su se našli na tapetu i iako ovo nije najbolji primer za ozbiljno poređenje jezika, mislim da je ipak interesantan.

Dakle, krenimo iz početka, Dominik Penfold je inicijalno zapazio problem i dao efikasan algoritam usađen u C++ (39 linija):
bool IsPrime(int num) { int sqrt = 1 + sqrtf(num); for (int i=2; i<sqrt; i++) { if (num % i == 0) return false; } return true; } int NthLeftTruncatablePrime(int target) { std::vector<int> PrimeRoots; PrimeRoots.push_back(2); PrimeRoots.push_back(3); PrimeRoots.push_back(5); PrimeRoots.push_back(7); int start = 0; int tens = 10; while(true) { int end = PrimeRoots.size(); for (int i=1; i<10; i++) { for (int pos = start; pos< end; pos++) { int newprime = tens * i + PrimeRoots[pos]; if (IsPrime(newprime)) { PrimeRoots.push_back(newprime); if (PrimeRoots.size()==target) return newprime; } } } start = end; tens *= 10; } }

Izvođenje je značajno ubrzano kada su 32-o bitni intedžeri zamenjeni 64-o bitnim.
C++ kod je veoma lako promenjen u C# (35 linija):
static bool IsPrime(int num) { int sqrt = 1 + (int ) System.Math.Sqrt(num); blue">for (int i = 2; i < sqrt; i++) { if (num % i == 0) return false; } return true; } static int NthLeftTruncatedPrime(int target) { var primeRoots = new List<int>() { 2, 3, 5, 7}; int start = 0; int tens = 10; while (true) { int end = primeRoots.Count; for (int i = 1; i < 10; i++) { for (int pos = start; pos < end; pos++) { int newprime = tens * i + primeRoots[pos]; if (IsPrime(newprime)) { primeRoots.Add(newprime); if (primeRoots.Count == target) return newprime; } } } start = end; tens *= 10; } }
Konverzija u F# je samo malo nezgodnija, budući da ne postoji jednaka povratna objava, ali se slično ponašanje može postići upotrebom yield (30 linija):
let IsPrime n = if n = 1 then false else let max = n |> float |> sqrt |> int let rec Test = function | x when x > max -> true | x -> if (n % x) = 0 then false else Test (x+1) Test 2 let NthLeftTruncatablePrime n = let oneDigitPrimes = [2;3;5;7] seq { let primes = ref oneDigitPrimes for tens = 1 to 8 do let acc = ref [] for i=1 to 9 do let newPrime = i * pown 10 tens let primes' = ref !primes while (!primes').Length > 0 do let x = newPrime+(!primes').Head if IsPrime x then acc := x :: !acc yield x primes' := (!primes').Tail done done primes := !acc |> List.rev done } |> Seq.append oneDigitPrimes |> Seq.nth (n-1)
Dodatno opterećenje sastavljanjem sekvenci može se izbeći upotrebom instead recursion (25 linija uključujući IsPrime funkciju):
let NthLeftTruncatablePrime index = let rec Find digit factor primes primes' count acc = match digit, primes' with | 10, _ -> let primes = List.rev acc Find 1 (10*factor) primes primes count [] | _, [] -> Find (digit+1) factor primes primes count acc | _, prime::tail -> let k = (digit * factor) + prime let count, acc = if IsPrime k then count+1, k::acc else count, acc if count = index then k else Find digit factor primes tail count acc let primes = [2;3;5;7] if index <= 4 then List.nth primes (index-1) else Find 1 10 primes primes 4 []
Kasnije, Met Kuran (pukim slučajem još jedan bivši programmer kompjuterskih igrica) stupa na scenu sa Haskell verzijom (17 linija uklučujući komentar-mada su linije pomalo zgusnute):
isPrime :: Int -> Bool isPrime 1 = False isPrime x = null $ take 1 [n | n <- [2..upperBound x], 0 == mod x n] where upperBound = floor . sqrt . fromIntegral -- list of all left truncatable primes ltps :: [Int] ltps = ps 1 [0] where ps _ [] = [] ps m prevMag = thisMag ++ (ps (m*10) thisMag) where thisMag = primes [x*m | x <- [1..9]] prevMag where primes [] _ = [] primes (m:mgs) bases = (filter isPrime [m+x | x <- bases]) ++ (primes mgs bases)

Results Breakdown by language

Language Lines of code Performance(ms)
C++ 39 5.213
C# 35 5.332
F# sequence 30 14.075
F# recursive 25 5.412
Haskell 17 ?

Zabeleška: vreme je za sastavljanje 1000-og primerka i isti računar je korišćen za sva ispitivanja, što je bila olakšavajuća okolnost. Haskell-ovo vreme uskoro dolazi.




Published (Last edited): 08-08-2012 , source: http://www.trelford.com/blog/post/c2b2b-vs-c-vs-f-vs-haskell.aspx