Python más rápido que Haskell comstackdo?

Tengo un script simple escrito en Python y Haskell. Lee un archivo con 1,000,000 enteros separados de nueva línea, analiza ese archivo en una lista de enteros, lo ordena rápidamente y luego lo escribe en un archivo diferente ordenado. Este archivo tiene el mismo formato que el sin clasificar. Sencillo.

Aquí está Haskell:

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

= p) xs main = do file read x::Int ) un let done = quicksort f writeFile "sorted" (unlines (map show done))

Y aquí está Python:

 def qs(ar): if len(ar) == 0: return ar p = ar[0] return 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()

Muy simple. Ahora compilo el código de Haskell con

 $ ghc -O2 --make quick.hs 

Y cronometro esos dos con:

     $ time ./quick $ time python qs.py 

    Resultados:

    Haskell:

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

    Pitón:

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

    ¿Cómo puede Python ser más rápido que el código nativo de Haskell?

    Gracias

    EDITAR :

    • Versión de Python: 2.7.1
    • Versión GHC: 7.0.4
    • Mac OSX, 10.7.3
    • Intel Core i5 de 2.4GHz

    Lista generada por

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

    Así que todos los números son únicos.

    En resumen, no utilice read . Reemplace read con una función como esta:

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

    Tengo una aceleración bastante justa:

     ~/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 

    Solo por diversión, los resultados anteriores incluyen una versión que usa ByteString (y por lo tanto falla la prueba “listo para el siglo XXI” al ignorar totalmente el problema de las codificaciones de archivos) para VELOCIDAD MÁXIMA DE BARE-METAL. También tiene algunas otras diferencias; por ejemplo, se envía a la función de clasificación de la biblioteca estándar. El código completo está abajo.

     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 tr | BS.null t -> writeFile "sorted" . unlines . map show . sort $ r 

    El código original de Haskell

    Hay dos problemas con la versión de Haskell:

    • Estás usando la cadena IO, que crea listas de caracteres vinculadas
    • Estás utilizando un no-quicksort que parece quicksort.

    Este progtwig tarda 18.7 segundos en ejecutarse en mi computadora portátil Intel Core2 2.5 GHz. (GHC 7.4 utilizando -O2)

    Versión ByteString de Daniel

    Esto ha mejorado mucho, pero observe que aún utiliza la ineficiente ordenación de fusión incorporada.

    Su versión toma 8.1 segundos (y no maneja números negativos, pero eso no es un problema para esta exploración).

    Nota

    A partir de aquí, en esta respuesta se utilizan los siguientes paquetes: Vector , attoparsec , text y vector-algorithms . También note que la versión de kindall que usa timsort toma 2.8 segundos en mi máquina (edición: y 2 segundos usando pypy).

    Una versión de texto

    Rasgué la versión de Daniel, la traduje a Texto (para que maneje varias codificaciones) y agregué una mejor clasificación usando un Vector mutable en una mónada 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 tr | 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') 

    Esto se ejecuta en 4 segundos (y tampoco maneja negativos)

    Regreso a la Bytestring

    Así que ahora sabemos que podemos hacer un progtwig más general que sea más rápido, ¿qué hay de hacer que la versión ASCii solo sea rápida? ¡No hay problema!

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

    Esto se ejecuta en 2,3 segundos.

    Producir un archivo de prueba

    Por si alguien tiene curiosidad, mi archivo de prueba fue producido por:

     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 te estás preguntando por qué vsort no está empaquetado de forma más fácil en Hackage ... yo también.

    Más un pitonista que un haskellite, pero lo intentaré:

    1. Hay un poco de sobrecarga en su tiempo de ejecución medido simplemente leyendo y escribiendo los archivos, lo que probablemente sea bastante similar entre los dos progtwigs. Además, tenga cuidado de haber calentado la memoria caché para ambos progtwigs.

    2. La mayor parte del tiempo lo dedicas a hacer copias de listas y fragmentos de listas. Las operaciones de la lista de Python están muy optimizadas, ya que son una de las partes del lenguaje utilizadas con mayor frecuencia, y la comprensión de las listas también suele ser bastante eficaz, y pasan gran parte de su tiempo en C-land dentro del intérprete de Python. No hay muchas de las cosas que son lentas en Python, pero que son muy rápidas en los idiomas estáticos, como las búsquedas de atributos en instancias de objetos.

    3. La implementación de Python arroja números que son iguales al pivote, por lo que al final puede ordenar menos elementos, lo que le da una ventaja obvia. (Si no hay duplicados en el conjunto de datos que está clasificando, esto no es un problema). Para solucionar este error, probablemente deba hacer otra copia de la mayoría de la lista en cada llamada a qs() , lo que ralentizaría a Python. poco más.

    4. No mencionas qué versión de Python estás usando. Si está usando 2.x, probablemente podría hacer que Haskell derrote a Python simplemente cambiando a Python 3.x. 🙂

    No estoy muy sorprendido de que los dos idiomas sean básicamente cuello y cuello aquí (una diferencia del 10% no es digna de mención). Usando C como un punto de referencia de rendimiento, Haskell pierde algo de rendimiento por su naturaleza funcional perezosa, mientras que Python pierde algo de rendimiento debido a ser un lenguaje interpretado. Un partido decente.

    Desde que Daniel Wagner publicó una versión optimizada de Haskell usando la sort integrada, aquí hay una versión de Python optimizada de manera similar que usa 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 segundos en mi máquina, frente a unos 9 para el código original. Bastante aún el cuello y el cuello con el optimizado Haskell. Motivo: pasa la mayor parte de su tiempo en bibliotecas progtwigdas con C Además, TimSort (el género utilizado en Python) es una bestia.

    Esto es después del hecho, pero creo que la mayor parte del problema está en la escritura de Haskell. El siguiente módulo es bastante primitivo: uno debería usar constructores probablemente y ciertamente evite el ridículo viaje redondo a través de String para mostrar, pero es simple y lo hizo mucho mejor que pypy con el mejorado python de kindall y mejor que los módulos Haskell de 2 y 4 segundos en otros lugares. en esta página (me sorprendió lo mucho que usaban las listas, así que hice un par de vueltas más de la manivela).

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

    Estoy usando la clasificación recomendada para vectores sin caja de algoritmos vectoriales. El uso de Data.Vector.Unboxed de alguna forma es claramente la forma estándar e ingenua de hacer este tipo de cosas: es la nueva Data.List (para Int, Double, etc.) Todo menos el sort es irritante para la gestión de IO , que creo que todavía podría mejorarse masivamente, en el extremo de escritura en particular. La lectura y la clasificación juntas toman aproximadamente 0,2 segundos, como puede ver al pedir que imprima lo que hay en un montón de índices en lugar de escribir en un archivo, por lo que se gasta tanto tiempo en escribir como en cualquier otra cosa. Si el pypy pasa la mayor parte del tiempo usando timsort o lo que sea, entonces parece que la clasificación en sí es seguramente mucho mejor en Haskell, y es igual de simple: si puedes conseguir el vector endurecido …

    No estoy seguro de por qué no hay funciones convenientes para leer y escribir vectores de cosas sin caja de formatos naturales. Si las hubiera, tendrían tres líneas de largo y evitarían Cadena y serían mucho más rápidas, pero tal vez simplemente no tengo. No los he visto.

     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 

    Para dar seguimiento a la interesante respuesta de @kindall, esos tiempos dependen de la implementación de Python / Haskell que usas, la configuración de hardware en la que ejecutas las pruebas y la implementación del algoritmo en ambos idiomas.

    Sin embargo, podemos intentar obtener algunos buenos indicios de los rendimientos relativos de una implementación de lenguaje en comparación con otro, o de un idioma a otro. Con alogrithms conocidos como qsort, es un buen comienzo.

    Para ilustrar una comparación python / python, acabo de probar su script en CPython 2.7.3 y PyPy 1.8 en la misma máquina:

    • CPython: ~ 8s
    • PyPy: ~ 2.5s

    Esto muestra que puede haber espacio para mejoras en la implementación del lenguaje, tal vez Haskell comstackdo no está realizando, en el mejor de los casos, la interpretación y comstackción de su código correspondiente. Si está buscando velocidad en Python, considere también cambiar a pypy si es necesario y si su código de cobertura le permite hacerlo.

    Noté un problema que todos los demás no notaron por alguna razón; Tanto tu haskell como tu código python tienen esto. (Por favor, dime si se corrige en las optimizaciones automáticas, no sé nada de optimizaciones). Para esto lo demostraré en haskell. en su código usted define las listas menores y mayores como esta:

     where lesser = filter (=p) xs 

    esto es malo, porque se compara con p cada elemento en xs dos veces, una vez para ingresar a la lista menor y otra vez para ingresar a la lista mayor. esto (teóricamente; no he comprobado el tiempo) hace que su ordenación utilice el doble de comparaciones; esto es un desastre. en su lugar, debe hacer una función que divida una lista en dos listas usando un predicado, de tal manera que

     split f xs 

    es equivalente a

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

    utilizando este tipo de función, solo necesitará comparar cada elemento de la lista una vez para saber en qué lado de la tupla colocarlo.
    bien, vamos a hacerlo

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

    ahora vamos a reemplazar el generador menor / mayor con

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

    código completo:

     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) |fx = let (a,b) = splitf f xs in (x:a,b) |otherwise = let (a,b) = splitf f xs in (a,x:b) 

    por alguna razón no puedo corregir la parte inferior / inferior en las cláusulas where, así que tuve que corregirla en cláusulas let. también, si no es recursivo a la cola, avíseme y repárelo por mí (todavía no sé cómo funciona la recorsión de la cola completamente)

    ahora debes hacer lo mismo con el código de Python. No sé python, así que no puedo hacerlo por ti.

    EDITAR: en realidad sucede que ya existe dicha función en Data.List llamada partición. Tenga en cuenta que esto demuestra la necesidad de este tipo de función porque de lo contrario no se definiría. Esto encoge el código para:

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

    Python está realmente optimizado para este tipo de cosas. Sospecho que Haskell no lo es. Aquí hay una pregunta similar que proporciona algunas respuestas muy buenas.