Python szybszy niż skompilowany Haskell?

Oryginalny Kod Haskell

Istnieją dwa problemy z wersją Haskell:

• używasz string IO, który buduje połączone listy znaków
• używasz nie-quicksort, który wygląda jak quicksort.

Daniel ' s ByteString Version

Jest to znacznie ulepszone, ale zauważ, że nadal wykorzystuje nieefektywne wbudowane sortowanie scalające.

Jego wersja zajmuje 8,1 sekundy (i nie obsługuje liczb ujemnych, ale to raczej nie problem dla tej eksploracji).

Uwaga

Stąd ta odpowiedź używa następujących pakietów: Vector, attoparsec, text i vector-algorithms. Zauważ również, że wersja kindalla z timsortem zajmuje 2,8 sekundy na moim komputerze (edit: i 2 sekundy z pypy).

Wersja Tekstowa

Wyrwałem wersję Daniela, przetłumaczyłem ją na Tekst (więc obsługuje różne kodowania) i dodano lepsze sortowanie za pomocą mutowalnego Vector w ST monadzie:

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')

Return To The Bytestring

Więc teraz wiemy, że możemy stworzyć bardziej ogólny program, który jest szybszy, co z szybką wersją tylko ASCii? Nie ma sprawy!

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')

Tworzenie pliku testowego

Na wszelki wypadek ciekawe, mój plik testowy został wyprodukowany przez:

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)

Jeśli zastanawiasz się, dlaczego vsort nie jest zapakowany w jakąś łatwiejszą formę na Hackage... ja też.

[[4]}bardziej Pythonistą niż Haskellitem, ale wezmę dźgnięcie:

1. Po prostu odczyt i zapisanie plików jest sporym obciążeniem w mierzonym środowisku uruchomieniowym, co prawdopodobnie jest podobne między tymi dwoma programami. Należy również uważać, aby rozgrzać pamięć podręczną dla obu programów.

2. Większość czasu poświęcasz na tworzenie kopii list i fragmentów list. Operacje listy Pythona są mocno zoptymalizowane, będąc jedną z najczęściej używanych części język i składanie list są zwykle dość wydajne, spędzając większość czasu w C-landu wewnątrz interpretera Pythona. Nie ma zbyt wielu rzeczy, które są powolne w Pythonie, ale bardzo szybkie w językach statycznych, takich jak wyszukiwanie atrybutów na instancjach obiektów.

3. Twoja implementacja Pythona wyrzuca liczby, które są równe pivotowi, więc pod koniec może sortować mniej elementów, dając mu oczywistą przewagę. (Jeżeli w zbiorze danych nie ma duplikatów sortujesz, to nie problem.) Naprawienie tego błędu prawdopodobnie wymaga wykonania kolejnej kopii większości listy w każdym wywołaniu qs(), Co spowolniłoby Pythona nieco bardziej.

4. Nie wspominasz, jakiej wersji Pythona używasz. Jeśli używasz 2.x, prawdopodobnie Haskell mógłby pokonać Pythona po prostu przełączając się na Python 3.x. :-)

Nie jestem zbyt zaskoczony, że dwa języki są w zasadzie szyi i szyi tutaj (różnica 10% nie jest godna uwagi). Za pomocą C jako benchmark wydajności, Haskell traci pewną wydajność ze względu na swój leniwy charakter funkcjonalny, podczas gdy Python traci pewną wydajność z powodu bycia językiem interpretowanym. Przyzwoity mecz.

Ponieważ Daniel Wagner opublikował zoptymalizowaną wersję Haskell przy użyciu wbudowanego sort, Oto podobnie zoptymalizowana wersja Pythona przy użyciu list.sort():

mylist = [int(x.strip()) for x in open("data")]
mylist.sort()
open("sorted", "w").write("\n".join(str(x) for x in mylist))

To jest po fakcie, ale myślę, że większość kłopotów jest w piśmie Haskell. Poniższy moduł jest dość prymitywny - należy użyć budowniczych prawdopodobnie i na pewno uniknąć śmiesznego roundtrip poprzez ciąg do pokazywania - ale jest prosty i zrobił wyraźnie lepiej niż pypy z ulepszonym Pythonem kindalla i lepiej niż 2 i 4 sek Haskell Moduły gdzie indziej na tej stronie (to zaskoczyło mnie, jak bardzo używali list, więc zrobiłem kilka więcej obrotów z listy. crank.)

$ time aa.hs        real    0m0.709s
$ time pypy aa.py   real    0m1.818s
$ time python aa.py real    0m3.103s

Używam sortowania zalecanego dla wektorów z algorytmów wektorowych. Wykorzystanie danych.Wektor.Unboxed w jakiejś formie jest teraz standardowym, naiwnym sposobem robienia tego typu rzeczy . to nowe dane.List (for Int, Double, etc.) Wszystko poza {[2] } jest irytujące zarządzanie IO, które, jak sądzę, nadal może być znacznie ulepszone, w szczególności na końcu zapisu. Czytanie i sortowanie razem trwa około 0.2 sek, jak widać po zapytaniu go o wydrukowanie tego, co w kilku indeksach zamiast zapisu do pliku, więc dwa razy więcej czasu poświęca się na pisanie, niż w czymkolwiek innym. Jeśli pypy spędza większość swojego czasu używając timsort lub czegokolwiek innego, to wygląda na to, że samo sortowanie jest zdecydowanie lepsze w Haskell, i tak samo proste -- jeśli możesz po prostu dostać się w swoje ręce na darned vector...

Nie jestem pewien, dlaczego nie ma wygodnych funkcji do odczytu i zapisu wektorów rzeczy nieboskłonowych z naturalnych formatów -- gdyby były, to będą długie na trzy linie i unikną sznurków i będą znacznie szybsze, ale może po prostu ich nie widziałem.

import qualified Data.ByteString.Lazy.Char8 as BL
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed.Mutable as M
import qualified Data.Vector.Unboxed as V
import Data.Vector.Algorithms.Radix 
import System.IO

main  = do  unsorted <- fmap toInts (BL.readFile "data")
            vec <- V.thaw unsorted
            sorted <- sort vec >> V.freeze vec
            withFile "sorted" WriteMode $ \handle ->
               V.mapM_ (writeLine handle) sorted

writeLine :: Handle -> Int -> IO ()
writeLine h int = B.hPut h $ B.pack (show int ++ "\n")

toInts :: BL.ByteString -> V.Vector Int
toInts bs = V.unfoldr oneInt (BL.cons ' ' bs) 

oneInt :: BL.ByteString -> Maybe (Int, BL.ByteString)
oneInt bs = if BL.null bs then Nothing else 
               let bstail = BL.tail bs
               in if BL.null bstail then Nothing else BL.readInt bstail

Aby śledzić @ kindall ciekawą odpowiedź, te czasy zależą zarówno od implementacji python / Haskell używasz, konfiguracji sprzętowej, na której uruchamiasz testy, i implementacji algorytmu prawo w obu językach.

Niemniej jednak możemy spróbować uzyskać kilka dobrych wskazówek na temat względnej wydajności jednej implementacji języka w porównaniu z inną, lub z jednego języka do innego języka. Z dobrze znanymi alogrytami jak qsort, jest to dobry początek.

Aby zilustrować porównanie Pythona / Pythona, przetestowałem Twój skrypt na CPython 2.7.3 i PyPy 1.8 na tej samej maszynie:

• CPython: ~8s
• PyPy: ~2,5 s

To pokazuje, że może być miejsce na ulepszenia w implementacji języka, być może skompilowany Haskell nie wykonuje co najwyżej interpretacji i kompilacji odpowiedniego kodu. Jeśli szukasz prędkości w Pythonie, rozważ również, aby przełączyć się na pypy w razie potrzeby i jeśli twój covering code pozwala ci to zrobić.

Zauważyłem pewien problem, którego inni nie zauważyli z jakiegoś powodu; zarówno Twój kod Haskell, jak i python mają to. (proszę mi powiedzieć, czy to jest naprawione w auto-optymalizacji, nic nie wiem o optymalizacji). w tym celu zademonstruję w haskell. w swoim kodzie definiujesz mniejsze i większe listy w ten sposób:

where lesser = filter (<p) xs
      greater = filter (>=p) xs

To jest złe, ponieważ porównujesz z P każdy element w xs dwa razy, raz za dostanie się na mniejszą listę i ponownie za dostanie się na większą listę. to (teoretycznie; nie sprawdzałem czasu) sprawia, że twój rodzaj używa dwa razy tyle porównań; to katastrofa. zamiast tego powinieneś utworzyć funkcję, która dzieli listę na dwie listy za pomocą predykatu, w taki sposób, że

split f xs

Jest równoważne

(filter f xs, filter (not.f) xs)

Używając tego rodzaju funkcji będziesz musiał porównać każdy element z listy raz , aby wiedzieć, po której stronie krotki ją umieścić.
ok, zróbmy to:

where
    split :: (a -> Bool) -> [a] -> ([a], [a])
    split _ [] = ([],[])
    split f (x:xs)
        |f x       = let (a,b) = split f xs in (x:a,b)
        |otherwise = let (a,b) = split f xs in (a,x:b)

Teraz wymieńmy generator mniejszy/większy z

let (lesser, greater) = split (p>) xs in (insert function here)

Pełny kod:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) =
    let (lesser, greater) = splitf (p>) xs
    in (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        splitf :: (a -> Bool) -> [a] -> ([a], [a])
        splitf _ [] = ([],[])
        splitf f (x:xs)
            |f x       = let (a,b) = splitf f xs in (x:a,b)
            |otherwise = let (a,b) = splitf f xs in (a,x:b)

Z jakiegoś powodu nie mogę naprawić gettera / mniejszej części w klauzulach where, więc musiałem to naprawić w klauzulach let. ponadto, jeśli nie jest to tail-recursive daj mi znać i napraw go dla mnie (Jeszcze Nie wiem, jak tail-recorsive działa w pełni)

Teraz powinieneś zrobić to samo dla kodu Pythona. Nie znam Pythona, więc nie mogę tego zrobić za Ciebie.

EDIT: faktycznie zdarza się już taka funkcja w Data.Lista o nazwie partycja. zauważ, że dowodzi to potrzeby tego rodzaju funkcji, ponieważ w przeciwnym razie nie byłaby zdefiniowana. to skraca kod do:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) =
    let (lesser, greater) = partition (p>) xs
    in (quicksort lesser) ++ [p] ++ (quicksort greater)

Python jest naprawdę zoptymalizowany do tego typu rzeczy. Podejrzewam, że Haskell nie jest. Oto podobne pytanie , które dostarcza bardzo dobrych odpowiedzi.