Вопрос по python, haskell – Python быстрее, чем скомпилированный Haskell?

43

У меня есть простой скрипт, написанный на Python и Haskell. Он считывает файл с 1 000 000 разделенных новой строкой целых чисел, анализирует этот файл в списке целых чисел, быстро сортирует его и затем записывает его в другой отсортированный файл. Этот файл имеет тот же формат, что и несортированный. Просто

Вот Хаскель:

<code>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))
</code>

А вот и Python:

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

Очень просто. Теперь я компилирую код на Haskell с помощью

<code>$ ghc -O2 --make quick.hs
</code>

И я провожу эти два с:

<code>$ time ./quick
$ time python qs.py
</code>

Полученные результаты

Haskell:

<code>real    0m10.820s
user    0m10.656s
sys 0m0.154s
</code>

Python:

<code>real    0m9.888s
user    0m9.669s
sys 0m0.203s
</code>

Как Python может быть быстрее, чем нативный код на Haskell?

Благодарност

РЕДАКТИРОВАТ:

Python версия: 2.7.1 Версия GHC: 7.0.4Mac OSX, 10.7.3 2,4 ГГц Intel Core i5

List генерируется

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

Так что все числа уникальны.

Какие версии GHC и Python вы используете? Я получаю исключение, когда пытаюсь запустить ваш код Python (Python 2.6.5 --- я не Pythonista). dave4420
Клоп в реализации Python? Вы строите подсписки сi > p а такжеi < p. Как насчет того, когдаi = p? gnud
Обратите внимание, что вы в основном синхронизируете ввод-вывод и конвертируете между целыми числами и строками. Замена звонка наquicksort сid на моей машине только сокращает время работы на ~ 30%. hammar
Ну, я думаю, что большая часть времени выполнения Python тратится на код C, который объединяет списки Python (динамические массивы, на случай, если кто-то не знает).cProfile должен сказать тебе, правда ли это. user395760
Как 9,9 быстрее, чем 10,8? Простая ошибка чтения HD может привести к разнице в десять раз. aib

Ваш Ответ

7   ответов
40

Короче, не используйте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 (и, следовательно, не проходит тест "готов к 21-му веку", полностью игнорируя проблему кодировки файлов) для 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
@ HonzaPokorny Да,cabal install attoparsec сначала из командной строки. Daniel Wagner
@ HonzaPokorny Возможно, файл был не в том формате, который распознал синтаксический анализатор - возможно, вы работаете в Windows, или в конце файла нет новой строки, или что-то подобное. Без наличия фактического файла в руке (а не, например, результата копирования и вставки в онлайн-каталог для вставки), отладка практически невозможна. Daniel Wagner
Что-нибудь особенное, что мне нужно сделать, чтобы скомпилировать это? Я получаюCould not find module Data.Attoparsec.ByteString.Char8'` Honza Pokorny
Python 2, когда используется, как в сценарии OP, тоже наплевать на кодировку, так что я думаю, что это справедливо:) Niklas B.
Компилирует нормально, но у меня не работает. Жалуется наNon-exhaustive patterns in case. Я на самом деле не Хаскеллер. Honza Pokorny
49

Оригинальный код Haskell

Есть две проблемы с версией на Haskell:

Вы используете строку ввода-вывода, которая создает связанные списки символов Вы используете не-быструю сортировку, которая выглядит как быстрая сортировка.

Этой программе на моем ноутбуке Intel Core2 2,5 ГГц требуется 18,7 секунды. (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 упакован не так просто ... как и я.

Жиль: / Stackoverflow.com вопросы / 7717691 / ... Thomas M. DuBuisson
Создание окончательной версии, которая в восемь раз быстрее оригинальной ... неплохо для рабочего дня! Daniel Wagner
"Вы используете не-быструю сортировку, которая выглядит как быстрая сортировка." Не могли бы вы рассказать об этом подробнее? Gilles
@ Viclib Так? «Его собственная определенная функция сортировки» не является быстрой сортировкой. Thomas M. DuBuisson
Но он использует свою собственную функцию сортировки ... MaiaVictor
2

эти временные интервалы зависят как от используемой вами реализации Python / Haskell, так и от конфигурации оборудования, на котором вы запускаете тесты, и от реализации алгоритма, которую вы используете на обоих языках.

Тем не менее мы можем попытаться получить некоторые хорошие намеки на относительную производительность одной языковой реализации по сравнению с другой или с одного языка на другой язык. С хорошо известными алогритами, такими как qsort, это хорошее начало.

Чтобы проиллюстрировать сравнение python / python, я только что протестировал ваш скрипт на CPython 2.7.3 и PyPy 1.8 на одной машине:

CPython: ~ 8 сPyPy: ~ 2,5 с

Это показывает, что могут быть возможности для улучшения языковой реализации, возможно, скомпилированный Haskell не выполняет в лучшем случае интерпретацию и компиляцию вашего соответствующего кода. Если вы ищете скорость в Python, подумайте также о переключении на pypy, если это необходимо, и если ваш сопроводительный код позволяет вам сделать это.

30

В измеряемом времени выполнения есть немало накладных расходов при чтении и записи файлов, что, вероятно, очень похоже на две программы. Кроме того, будьте осторожны, чтобы вы подогрели кеш для обеих программ.

Большая часть вашего времени уходит на создание списков и фрагментов списков. Операции со списками 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) является Зверь.

Каким-то образом пропустил это. kindall
Хорошие наблюдения, только одна вещь, касающаяся # 4: он называет компилятор и флаги:ghc -O2 --make quick.hs user395760
Не могли бы вы объяснить свой четвертый пункт? inf
Ну да, это было именно то, о чем я думал. Почему Python 3 медленнее, чем Python 2? Есть ли у вас какие-либо ссылки / материалы, на которые я мог бы взглянуть? inf
Ну, Python и Haskell теперь близки к одинаковой скорости, поэтому, если вы переключитесь на более медленную версию Python (например, 3.x), версия Python может отставать от версии на Haskell. kindall
9

но я думаю, что большая часть проблемы заключается в написании Хаскеля. Следующий модуль довольно примитивен - нужно использовать сборщиков, вероятно, и, конечно же, избегать нелепой обратной передачи через 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
1

что Хаскелл не. Вот похожий вопрос это дает очень хорошие ответы.

2

которую все остальные по какой-то причине не заметили; и ваш код на 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)
cf. Stackoverflow.com / а / 9550430/849891:) Will Ness

Похожие вопросы