Lütfen buraya ait değil düşünüyorsanız alakasız olarak işaretlemek için çekinmeyin.

Basit bir komut dosyası Python ve Haskell ile yazılmış. 1,000,000 yeni satır ayrılmış tamsayılar ile bir dosya okur, tamsayılar, hızlı sıralar bir liste halinde bu dosyayı ayrıştırmak ve daha sonra farklı bir dosya sıralanmış yazar. Bu dosya sıralanmamış aynı biçime sahip. Basit.

Burada Haskell:

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

main = do
    file <- readFile "data"
    let un = lines file
    let f = map (\x -> read x::Int ) un
    let done = quicksort f
    writeFile "sorted" (unlines (map show done))

Ve burada Python

def qs(ar):
    if len(ar) == 0:
        return ar

    p = ar[0]
    return qs([i for i in ar if i < p])   [p]   qs([i for i in ar if i > p])


def read_file(fn):
    f = open(fn)
    data = f.read()
    f.close()
    return data

def write_file(fn, data):
    f = open('sorted', 'w')
    f.write(data)
    f.close()


def main():
    data = read_file('data')

    lines = data.split('\n')
    lines = [int(l) for l in lines]

    done = qs(lines)
    done = [str(l) for l in done]

    write_file('sorted', "\n".join(done))

if __name__ == '__main__':
    main()

Çok basit. Şimdi ben Haskell kodu derleyin

$ ghc -O2 --make quick.hs

Ve ben bu iki zaman:

$ time ./quick
$ time python qs.py

Sonuçlar:

Haskell:

real    0m10.820s
user    0m10.656s
sys 0m0.154s

Python:

real    0m9.888s
user    0m9.669s
sys 0m0.203s

Nasıl Python muhtemelen yerel kod Haskell daha hızlı olabilir?

Teşekkürler

EDİT:

• Python versiyon: 2.7.1
• DZD versiyon: 7.0.4
• Mac OS X, 10.7.3
• 2.4 GHz Intel Core ı5

Liste tarafından oluşturulur

from random import shuffle
a = [str(a) for a in xrange(0, 1000*1000)]
shuffle(a)
s = "\n".join(a)
f = open('data', 'w')
f.write(s)
f.close()

Tüm sayıların benzersiz.

Orijinal Haskell Kodu

Haskell sürümü ile iki sorunu vardır:

• Karakter bağlı listeler oluşturur dize IO, kullanıyorsun
• Quicksort gibi görünen olmayan bir quicksort kullanıyorsun.

Bu program yüzde 18,7 saniye Core2 2.5 GHz Intel bilgisayarımda çalıştırmak için alır. (7.4 kullanarak O2) DZD

Daniel örneğini oluşturur bytestring Sürümü

Bu çok artırıldı, ama yine de verimsiz kullanır fark dahili sıralama birleştirme.

Onun sürüm 8.1 saniye ve negatif sayılar işlemek değil, ama bu keşif için konu dışı bir daha) alır.

Not

Buradan bu cevap üzerine aşağıdaki paketleri kullanır: Vector, attoparsec, text ve vector-algorithms. Kindall versiyonu timsort kullanarak 2.8 saniye sürer de fark benim makinede (edit: 2 saniye pypy kullanarak).

Bir Metin Sürümü

Kapalı Daniel versiyonu açmışım, Metin çeşitli kodlamalar işlediği () için çevrilmiş ve daha iyi bir değişken bir ST Vector monad: kullanarak sıralama eklendi

import Data.Attoparsec.Text.Lazy
import qualified Data.Text.Lazy as T
import qualified Data.Text.Lazy.IO as TIO
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I
import Control.Applicative
import Control.Monad.ST
import System.Environment (getArgs)

parser = many (decimal <* char '\n')

main = do
    numbers <- TIO.readFile =<< fmap head getArgs
    case parse parser numbers of
        Done t r | T.null t -> writeFile "sorted" . unlines
                                                  . map show . vsort $ r
        x -> error $ Prelude.take 40 (show x)

vsort :: [Int] -> [Int]
vsort l = runST $ do
        let v = V.fromList l
        m <- V.unsafeThaw v
        I.sort m
        v' <- V.unsafeFreeze m
        return (V.toList v')

Bu 4 saniye (ve de negatifleri ele vermez) çalışır

Bu örneğini oluşturur bytestring dönmek

Şimdi daha hızlı, daha genel bir program yapabiliriz yani, ne kadar hızlı-sadece ASCıı sürümünü yapmaya ne dersiniz? Sorun değil!

import qualified Data.ByteString.Lazy.Char8 as BS
import Data.Attoparsec.ByteString.Lazy (parse,  Result(..))
import Data.Attoparsec.ByteString.Char8 (decimal, char)
import Control.Applicative ((<*), many)
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I
import Control.Monad.ST


parser = many (decimal <* char '\n')

main = do
    numbers <- BS.readFile "rands"
    case parse parser numbers of
        Done t r | BS.null t -> writeFile "sorted" . unlines
                                                   . map show . vsort $ r

vsort :: [Int] -> [Int]
vsort l = runST $ do
        let v = V.fromList l
        m <- V.unsafeThaw v
        I.sort m
        v' <- V.unsafeFreeze m
        return (V.toList v')

Bu 2.3 saniye içinde çalışır.

Test bir Dosya üretiyor

Herkes merak ediyor diye, benim test dosyası üretilen tarafından değiştirildi

import Control.Monad.CryptoRandom
import Crypto.Random
main = do
  g <- newGenIO :: IO SystemRandom
  let rs = Prelude.take (2^20) (map abs (crandoms g) :: [Int])
  writeFile "rands" (unlines $ map show rs)

vsort Hackage biraz daha kolay form... ben de öyle paketlenmiş değil neden merak ediyorsanız