Python быстрее, чем скомпилированный Haskell?
У меня есть простой скрипт, написанный на Python и Haskell. Он читает файл с 1 000 000 разделенных символом новой строки целых чисел, анализирует этот файл в списке целых чисел, быстро сортирует его и затем записывает его в другой отсортированный файл. Этот файл имеет тот же формат, что и несортированный. Просто.
Вот Хаскелл:
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))
А вот и 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()
Очень просто. Теперь я компилирую код на Haskell с
$ ghc -O2 --make quick.hs
И я время эти два с:
$ time ./quick
$ time python qs.py
Результаты:
Haskell:
real 0m10.820s
user 0m10.656s
sys 0m0.154s
Python:
real 0m9.888s
user 0m9.669s
sys 0m0.203s
Как Python может быть быстрее, чем нативный код на Haskell?
Спасибо
РЕДАКТИРОВАТЬ:
- Версия Python: 2.7.1
- Версия GHC: 7.0.4
- Mac OSX, 10.7.3
- 2,4 ГГц Intel Core i5
Список, созданный
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()
Так что все числа уникальны.
7 ответов
Короче говоря, не используйте read, замещать read с такой функцией:
import Numeric
fastRead :: String -> Int
fastRead s = case readDec s of [(n, "")] -> n
Я получаю довольно справедливое ускорение:
~/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
Просто для удовольствия, приведенные выше результаты включают версию, которая использует ByteString (и, следовательно, не проходит тест "готов к XXI веку", полностью игнорируя проблему кодировки файлов) для ULTIMATE BARE-METAL SPEED. У этого также есть несколько других различий; например, он отправляется в функцию сортировки стандартной библиотеки. Полный код ниже.
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
Оригинальный код Haskell
Есть две проблемы с версией на Haskell:
- Вы используете строку ввода / вывода, которая строит связанные списки символов
- Вы используете не-быструю сортировку, которая выглядит как быстрая сортировка.
Эта программа занимает 18,7 секунды для запуска на моем ноутбуке Intel Core2 2,5 ГГц. (GHC 7.4 с использованием -O2)
Версия ByteString Дэниела
Это значительно улучшено, но обратите внимание, что оно все еще использует неэффективную встроенную сортировку слиянием.
Его версия занимает 8,1 секунды (и не обрабатывает отрицательные числа, но это больше не проблема для этого исследования).
Заметка
С этого момента в этом ответе используются следующие пакеты: Vector, attoparsec, text а также vector-algorithms, Также обратите внимание, что версия kindall, использующая timsort, занимает на моей машине 2,8 секунды (edit: и 2 секунды, используя pypy).
Текстовая версия
Я сорвал версию Даниэля, перевел ее в текст (так что она обрабатывает различные кодировки) и добавил лучшую сортировку с использованием изменяемого Vector в монаде 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')
Это выполняется за 4 секунды (и также не обрабатывает негативы)
Возврат к Бистрейнгу
Итак, теперь мы знаем, что можем сделать более общую программу, более быструю, а как насчет того, чтобы сделать версию ASCii -only быстрой? Нет проблем!
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')
Это работает за 2,3 секунды.
Создание тестового файла
На всякий случай, если кому-то интересно, мой тестовый файл был создан:
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... я тоже
Больше Pythonista, чем Haskellite, но я сделаю удар:
В вашей измеренной среде выполнения есть немало накладных расходов при чтении и записи файлов, что, вероятно, очень похоже между двумя программами. Кроме того, будьте осторожны, что вы подогрели кеш для обеих программ.
Большая часть вашего времени уходит на копирование списков и фрагментов списков. Операции со списками Python сильно оптимизированы, так как являются одной из наиболее часто используемых частей языка, и понимание списков, как правило, тоже довольно производительно, тратя большую часть своего времени на C-land внутри интерпретатора Python. Существует не так много вещей, которые медленны в Python, но быстро разбиты в статических языках, таких как поиск атрибутов в экземплярах объектов.
Ваша реализация Python отбрасывает числа, равные центральной точке, поэтому в конце она может сортировать меньше элементов, что дает очевидное преимущество. (Если в наборе данных, который вы сортируете, нет дубликатов, это не проблема.) Исправление этой ошибки, вероятно, требует создания другой копии большей части списка в каждом вызове
qs(), что замедлит Python еще немного.Вы не упоминаете, какую версию Python вы используете. Если вы используете 2.x, вы можете заставить Haskell победить Python, просто переключившись на Python 3.x.:-)
Я не слишком удивлен, что эти два языка здесь в основном по принципу "шея и шея" (разница в 10% не заслуживает внимания). Используя C в качестве эталона производительности, Haskell теряет некоторую производительность из-за своей ленивой функциональной природы, в то время как Python теряет некоторую производительность из-за интерпретации языка. Приличный матч.
Так как Даниэль Вагнер выложил оптимизированную версию на Haskell с использованием встроенного sortВот аналогично оптимизированная версия Python, использующая 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 секунды на моей машине, против 9 для исходного кода. Практически все еще шея и шея с оптимизированным Haskell. Причина: он проводит большую часть своего времени в программируемых на C библиотеках. Также TimSort (сортировка, используемая в Python) - зверь.
Это после факта, но я думаю, что большая часть проблемы заключается в написании Хаскеля. Следующий модуль довольно примитивен - нужно использовать сборщиков, вероятно, и, конечно же, избегать нелепой обратной передачи через String для показа - но он прост и работает явно лучше, чем pypy, с улучшенным python для kindall и лучше, чем 2 и 4-секундные модули Haskell в других местах. на этой странице (меня удивило, насколько они использовали списки, поэтому я сделал еще пару поворотов.)
$ time aa.hs real 0m0.709s
$ time pypy aa.py real 0m1.818s
$ time python aa.py real 0m3.103s
Я использую сортировку, рекомендованную для неупакованных векторов из векторных алгоритмов. Использование Data.Vector.Unboxed в той или иной форме, несомненно, теперь является стандартным, наивным способом сделать подобные вещи - это новый Data.List (для Int, Double и т. Д.). Все, кроме sort раздражает управление вводом-выводом, которое, я думаю, все еще будет значительно улучшено, особенно в конце записи. Чтение и сортировка вместе занимают около 0,2 с, как вы можете видеть из запроса на печать содержимого группы индексов вместо записи в файл, так что на запись уходит вдвое больше времени, чем на что-либо еще. Если pypy тратит большую часть своего времени, используя timsort или что-то еще, то похоже, что сама сортировка в Haskell, безусловно, намного лучше и такая же простая - если вы можете просто взять в руки проклятый вектор...
Я не уверен, почему нет удобных функций для чтения и записи векторов распакованных вещей из естественных форматов - если бы они были, это было бы длиной в три строки и избегало бы String и было бы намного быстрее, но, может быть, я просто прибыл не видел их.
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
Я заметил некоторую проблему, которую все остальные по какой-то причине не заметили; и ваш код на haskell, и на python имеют это. (скажите, пожалуйста, исправлено ли это в автооптимизации, я ничего не знаю об оптимизации). Для этого я продемонстрирую в Haskell. в вашем коде вы определяете меньшие и большие списки, как это:
where lesser = filter (<p) xs
greater = filter (>=p) xs
это плохо, потому что вы сравниваете с p каждый элемент в xs дважды, один раз для попадания в меньший список, и снова для попадания в больший список. это (теоретически; я не проверял время) заставляет ваш вид использовать в два раза больше сравнений; это катастрофа. вместо этого вы должны создать функцию, которая разбивает список на два списка с использованием предиката таким образом, чтобы
split f xs
эквивалентно
(filter f xs, filter (not.f) xs)
используя такую функцию, вам нужно будет только один раз сравнить каждый элемент в списке, чтобы узнать, в какую сторону кортежа его поместить.
хорошо, давайте сделаем это:
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)
Теперь давайте заменим меньший / больший генератор на
let (lesser, greater) = split (p>) xs in (insert function here)
полный код:
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)
по какой-то причине я не могу исправить получатель / меньшую часть в предложениях where, поэтому мне пришлось исправить это в предложениях let. также, если это не хвостовая рекурсия, дайте мне знать и исправить это для меня (я еще не знаю, как хвостовая рекурсивная работа полностью)
Теперь вы должны сделать то же самое для кода Python. Я не знаю Python, поэтому я не могу сделать это для вас.
РЕДАКТИРОВАТЬ: на самом деле в Data.List уже есть такая функция, которая называется разделом. обратите внимание, что это доказывает необходимость такого рода функции, потому что в противном случае она не будет определена. это сокращает код до:
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) =
let (lesser, greater) = partition (p>) xs
in (quicksort lesser) ++ [p] ++ (quicksort greater)
Чтобы ответить на интересный ответ @kindall, эти временные интервалы зависят как от используемой вами реализации Python / Haskell, так и от конфигурации оборудования, на котором вы запускаете тесты, и от реализации алгоритма, которую вы используете на обоих языках.
Тем не менее мы можем попытаться получить некоторые хорошие намеки на относительную производительность одной языковой реализации по сравнению с другой или с одного языка на другой язык. С хорошо известными алогритами, такими как qsort, это хорошее начало.
Чтобы проиллюстрировать сравнение python / python, я просто протестировал ваш скрипт на CPython 2.7.3 и PyPy 1.8 на одной машине:
- CPython: ~ 8 с
- PyPy: ~2,5 с
Это показывает, что могут быть возможности для улучшения языковой реализации, возможно, скомпилированный Haskell не выполняет в лучшем случае интерпретацию и компиляцию вашего соответствующего кода. Если вы ищете скорость в Python, подумайте также о переключении на pypy, если это необходимо, и если ваш сопроводительный код позволяет вам это сделать.
Python действительно оптимизирован для такого рода вещей. Я подозреваю, что Хаскелл не. Вот аналогичный вопрос, который дает очень хорошие ответы.