Python plus rapide que Haskell compilé?

Question

Je dispose d'un script simple écrit à la fois en Python et en Haskell. Il lit un fichier contenant 1 000 000 d'entiers séparés par des sauts de ligne, analyse ce fichier pour en faire une liste d'entiers, les trie rapidement, puis les écrit dans un autre fichier trié. Ce fichier a le même format que le non trié. Simple.

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

Et voici 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()

Très simple. Maintenant je compile le code Haskell avec

$ ghc -O2 --make quick.hs

Et je les mesure avec le temps :

$ time ./quick
$ time python qs.py

Résultats:

Haskell:

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

Python:

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

Comment Python peut-il être plus rapide que le code natif Haskell?

Merci

ÉDITER:

• Version Python: 2.7.1
• Version GHC: 7.0.4
• Mac OSX, 10.7.3
• Intel Core i5 2.4GHz

Liste générée par

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

Donc tous les numéros sont uniques.

Answer 1

Le code Haskell d'origine

Il y a deux problèmes avec la version Haskell :

• Vous utilisez le IO de chaîne, qui construit des listes chaînées de caractères
• Vous utilisez un quicksort non-quicksort qui ressemble à quicksort.

Ce programme prend 18.7 secondes pour s'exécuter sur mon ordinateur portable Intel Core2 2,5 GHz (GHC 7.4 utilisant -O2)

Version ByteString de Daniel

C'est beaucoup amélioré, mais notez qu'il utilise toujours le tri fusion intégré inefficace.

Sa version prend 8.1 secondes (et ne gère pas les nombres négatifs, mais c'est plus un non-problème pour cette exploration).

Remarque

À partir de maintenant, cette réponse utilise les packages suivants : Vector, attoparsec, text et vector-algorithms. Remarquez également que la version de kindall utilisant timsort prend 2.8 secondes sur ma machine (modifié : et 2 secondes en utilisant pypy).

Une version Text

J'ai copié la version de Daniel, je l'ai traduite en Text (pour qu'elle gère divers encodages) et j'ai ajouté un meilleur tri en utilisant un Vector mutable dans un monade ST :

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

Cela s'exécute en 4 secondes (et ne gère pas les négatifs non plus)

Retour au Bytestring

Maintenant que nous savons que nous pouvons créer un programme plus général qui est plus rapide, qu'en est-il de rendre la version uniquement ASCII rapide ? Pas de problème !

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

Cela s'exécute en 2.3 secondes.

Production d'un fichier de test

Au cas où quelqu'un serait curieux, mon fichier de test a été produit par :

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)

Si vous vous demandez pourquoi vsort n'est pas emballé de manière plus simple sur Hackage... moi aussi.

Answer 2

En bref, n'utilisez pas read. Remplacez read par une fonction comme celle-ci :

import Numeric

fastRead :: String -> Int
fastRead s = case readDec s of [(n, "")] -> n

J'obtiens une accélération assez significative :

~/programming% time ./test.slow
./test.slow  9.82s user 0.06s system 99% cpu 9.901 total
~/programming% time ./test.fast
./test.fast  6.99s user 0.05s system 99% cpu 7.064 total
~/programming% time ./test.bytestring
./test.bytestring  4.94s user 0.06s system 99% cpu 5.026 total

Juste pour le plaisir, les résultats ci-dessus incluent une version qui utilise ByteString (et échoue ainsi au test "prête pour le 21e siècle" en ignorant totalement le problème des encodages de fichiers) pour UNE VITESSE AU PLUS HAUT NIVEAU. Il comporte également quelques autres différences ; par exemple, il envoie vers la fonction de tri de la bibliothèque standard. Le code complet est ci-dessous.

import qualified Data.ByteString as BS
import Data.Attoparsec.ByteString.Char8
import Control.Applicative
import Data.List

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

reallyParse p bs = case parse p bs of
    Partial f -> f BS.empty
    v -> v

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

Answer 3

Plus Pythonista qu'Haskellite, mais je vais essayer :

1. Il y a pas mal de surcharge dans le temps d'exécution mesuré juste en lisant et écrivant les fichiers, ce qui est probablement assez similaire entre les deux programmes. De plus, veillez à avoir préchauffé le cache pour les deux programmes.

2. La plupart de votre temps est passé à faire des copies de listes et de fragments de listes. Les opérations de liste Python sont fortement optimisées, étant l'une des parties les plus utilisées du langage, et les compréhensions de liste sont généralement assez performantes aussi, passant une grande partie de leur temps dans le monde C à l'intérieur de l'interpréteur Python. Il n'y a pas beaucoup de choses qui sont lentes en Python mais extrêmement rapides dans les langages statiques, comme les recherches d'attributs sur les instances d'objets.

3. Votre implémentation Python jette les nombres qui sont égaux au pivot, donc à la fin il peut trier moins d'éléments, ce qui lui donne un avantage évident. (S'il n'y a pas de doublons dans l'ensemble de données que vous triez, ce n'est pas un problème.) Corriger ce bogue nécessite probablement de faire une autre copie de la plupart de la liste dans chaque appel à qs(), ce qui ralentirait un peu Python.

4. Vous ne mentionnez pas quelle version de Python vous utilisez. Si vous utilisez la 2.x, vous pourriez probablement faire en sorte qu'Haskell batte Python simplement en passant à Python 3.x. :-)

Je ne suis pas trop surpris que les deux langages soient pratiquement à égalité ici (une différence de 10 % n'est pas remarquable). En utilisant C comme mesure de performance, Haskell perd un peu de performances pour sa nature fonctionnelle paresseuse, tandis que Python en perd un peu en raison de son interprétation. Un match correct.

Étant donné que Daniel Wagner a publié une version Haskell optimisée utilisant le sort intégré, voici une version Python également optimisée utilisant 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))

3,5 secondes sur ma machine, contre environ 9 pour le code original. Toujours à peu près à égalité avec l'Haskell optimisé. Raison : il passe la plupart de son temps dans des bibliothèques programmées en C. De plus, TimSort (le tri utilisé en Python) est une bête.

Answer 4

Ceci est un fait accompli, mais je pense que la plupart des problèmes se trouvent dans l'écriture en Haskell. Le module suivant est assez primitif - on devrait probablement utiliser des constructeurs et éviter certainement le retour ridicule via String pour l'affichage - mais c'est simple et a nettement mieux fonctionné que pypy avec le Python amélioré de kindall et mieux que les modules Haskell à 2 et 4 secondes ailleurs sur cette page (cela m'a surpris de voir à quel point ils utilisaient des listes, donc j'ai fait quelques tours supplémentaires de manivelle.)

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

Je me sers du tri recommandé pour les vecteurs non boxés de vector-algorithms. L'utilisation de Data.Vector.Unboxed sous une forme quelconque est clairement désormais la manière standard et naïve de faire ce genre de chose - c'est le nouveau Data.List (pour Int, Double, etc.) Tout sauf le sort est une gestion de l'IO irritante, qui pourrait, je pense, encore être massivement améliorée, en particulier en écriture. La lecture et le tri ensemble prennent environ 0,2 seconde comme vous pouvez le voir en demandant d'afficher ce qui se trouve à plusieurs index au lieu d'écrire dans un fichier, donc deux fois plus de temps sont consacrés à l'écriture que dans tout autre chose. Si le pypy passe la plupart de son temps à utiliser timsort ou autre, alors il semble que le tri lui-même est sûrement massivement meilleur en Haskell, et tout aussi simple - si vous pouvez simplement mettre la main sur le fichu vecteur...

Je ne suis pas sûr pourquoi il n'y a pas de fonctions pratiques pour lire et écrire des vecteurs de choses non boxées dans des formats naturels - s'il y en avait, cela ne prendrait que trois lignes et éviterait String et serait beaucoup plus rapide, mais peut-être que je ne les ai tout simplement pas vues.

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

Answer 5

Python est vraiment optimisé pour ce genre de chose. Je soupçonne que Haskell ne l'est pas. Voici une question similaire qui fournit de très bonnes réponses.