Python más rápido que compilado Haskell?
quicksort (7)
En resumen, no use read . Reemplace la 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 no ByteString prueba "lista para el siglo XXI" ignorando por completo el problema de las codificaciones de archivos) para la VELOCIDAD BARE-METAL MÁXIMA. También tiene algunas otras diferencias; por ejemplo, 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 t r | BS.null t -> writeFile "sorted" . unlines . map show . sort $ r
Tengo un script simple escrito tanto en Python como en Haskell. Lee un archivo con 1,000,000 de enteros separados por 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
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))
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]) + [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()
Muy simple. Ahora compilo el código Haskell con
$ ghc -O2 --make quick.hs
Y yo vez a 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 es posible que Python sea más rápido que el código nativo Haskell?
Gracias
EDITAR :
- Versión de Python: 2.7.1
- Versión de GHC: 7.0.4
- Mac OSX, 10.7.3
- Intel Core i5 de 2,4 GHz
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()
Entonces todos los números son únicos.
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 sin duda evitar el ridículo viaje de ida y vuelta a través de String para mostrarlo, pero es simple e hizo mucho mejor que pypy con el mejorado Python de Kindall y mejor que los módulos Haskell de 2 y 4 segundos en esta página (me sorprendió lo mucho que usaban listas, así que hice un par de giros 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 el tipo recomendado para vectores sin caja de algoritmos vectoriales. El uso de Data.Vector.Unboxed de alguna forma ahora 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 gestión de IO , que podría pensar que aún se mejora masivamente, en el extremo de la escritura en particular. La lectura y la ordenación juntas tardan unos 0,2 segundos, como se puede ver al solicitar que se imprima lo que hay en un montón de índices en lugar de escribir en un archivo, por lo que se gasta el doble de tiempo que en cualquier otra cosa. Si el padre está pasando la mayor parte del tiempo usando timsort o lo que sea, parece que la clasificación en sí misma es mucho mejor en Haskell, y lo más simple, si puede poner sus manos sobre el vector zurcido ...
No estoy seguro de por qué no hay funciones convenientes para leer y escribir vectores de elementos no empaquetados de formatos naturales; si los hubiera, esto sería de tres líneas y evitaría String y sería mucho más rápido, pero tal vez solo lo tengo. los has 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
Más un Pythonista que un Haskellite, pero daré una puñalada:
Hay un poco de sobrecarga en el tiempo de ejecución medido simplemente leyendo y escribiendo los archivos, que es probablemente bastante similar entre los dos programas. Además, tenga cuidado de haber calentado el caché para ambos programas.
La mayor parte de su tiempo lo dedica a hacer copias de listas y fragmentos de listas. Las operaciones de la lista de Python están muy optimizadas, siendo una de las partes más utilizadas del idioma, y las listas de comprensión también suelen ser bastante efectivas, pasando gran parte de su tiempo en C-land dentro del intérprete de Python. No hay muchas cosas que se ralentizan en Python pero sí rápidas en los lenguajes estáticos, como las búsquedas de atributos en instancias de objetos.
La implementación de Python descarta los números que son iguales al pivote, por lo que al final puede clasificar menos elementos, lo que le da una ventaja obvia. (Si no hay duplicados en el conjunto de datos que está ordenando, esto no es un problema). La reparación de este error probablemente requiera hacer otra copia de la mayor parte de la lista en cada llamada a
qs(), lo que ralentizaría a Python. poco más.No mencionas qué versión de Python estás usando. Si está utilizando 2.x, probablemente consiga que Haskell venza a Python simplemente cambiando a Python 3.x. :-)
No estoy demasiado sorprendido de que los dos idiomas sean básicamente de cuello y cuello aquí (una diferencia del 10% no es digna de mención). Utilizando C como punto de referencia de rendimiento, Haskell pierde algo de rendimiento por su naturaleza funcional, mientras que Python pierde algo de rendimiento debido a que es un lenguaje interpretado. Una pareja decente.
Dado que Daniel Wagner publicó una versión optimizada de Haskell utilizando el tipo incorporado, 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 aproximadamente 9 para el código original. Todavía bastante al cuello con el Haskell optimizado. Motivo: pasa la mayor parte del tiempo en bibliotecas programadas en C. Además, TimSort (el género utilizado en Python) es una bestia.
Para dar seguimiento a la respuesta interesante de @kindall, esos tiempos dependen de la implementación de Python / Haskell que utilice, la configuración de hardware en la que ejecuta las pruebas y la implementación del algoritmo en ambos idiomas.
Sin embargo, podemos tratar de obtener algunos buenos indicios del rendimiento relativo de la implementación de un idioma en comparación con otro, o de un idioma a otro. Con alogritos 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 compilado. Haskell no está realizando a lo sumo la interpretación y compilación de su código correspondiente. Si está buscando velocidad en Python, considere cambiar a pypy si es necesario y si su código de cobertura le permite hacerlo.
Python está realmente optimizado para este tipo de cosas. Sospecho que Haskell no lo es. Aquí hay una pregunta similar que ofrece algunas muy buenas respuestas.
noté algún problema que los demás no notaron por alguna razón; tanto tu haskell como tu código python tienen esto. (dígame si está corregido en las optimizaciones automáticas, no sé nada sobre optimizaciones). para esto demostraré en Haskell. en su código usted define las listas cada vez menores como esta:
where lesser = filter (<p) xs
greater = filter (>=p) xs
esto es malo, porque se compara con p cada elemento en xs dos veces, una para entrar en la lista menor y otra vez para entrar en la lista más grande. esto (teóricamente, no he comprobado el tiempo) hace que tu género use 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 forma que
split f xs
es equivalente a
(filter f xs, filter (not.f) xs)
usando este tipo de función solo necesitarás comparar cada elemento en la lista una vez para saber en qué lado de la tupla ponerlo.
Está bien, hagámoslo:
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)
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)
|f x = 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 getter / lesser en las cláusulas where, así que tuve que corregirlo en las cláusulas let. Además, si no es recursivo de la cola, avíseme y solucione el problema (aún no sé cómo funciona la cola-rectora).
ahora deberías hacer lo mismo con el código python. No conozco a Python, así que no puedo hacerlo por ti.
EDITAR: realmente ya existe esa función en Data.List llamada partition. tenga en cuenta que esto demuestra la necesidad de este tipo de función porque de lo contrario no se definiría. esto reduce el código a:
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) =
let (lesser, greater) = partition (p>) xs
in (quicksort lesser) ++ [p] ++ (quicksort greater)
El código original de Haskell
Hay dos problemas con la versión de Haskell:
- Está utilizando cadena IO, que crea listas de caracteres vinculadas
- Está utilizando una conexión no rápida que se parece a la oferta rápida.
Este programa toma 18.7 segundos para ejecutarse en mi computadora portátil Intel Core2 2.5 GHz. (GHC 7.4 usando -O2)
Versión ByteString de Daniel
Esto es mucho mejor, pero note que todavía usa el tipo de combinación incorporada ineficiente.
Su versión demora 8.1 segundos (y no maneja números negativos, pero eso no es un problema para esta exploración).
Nota
A partir de ahora, esta respuesta utiliza 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
Arranqué 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 de 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'')
Esto se ejecuta en 4 segundos (y tampoco maneja los negativos)
Volver a la Bytestring
Entonces, ahora sabemos que podemos hacer un programa más general que sea más rápido, ¿qué tal hacer que la versión de ASCii-only 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 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'')
Esto funciona en 2.3 segundos.
Produciendo un archivo de prueba
En caso de que alguien tenga 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 preguntas por qué vsort no está empaquetado de alguna forma más fácil en Hackage ... yo también.