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

Ответ 1

Короче говоря, не используйте 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

Ответ 2

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

В версии Haskell есть две проблемы:

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

Эта программа занимает 18,7 секунды для работы на моем ноутбуке Intel Core2 2,5 ГГц. (GHC 7.4 с использованием -O2)

Версия Daniel ByteString

Это значительно улучшилось, но обратите внимание, что он по-прежнему использует неэффективную встроенную сортировку слияния.

Его версия занимает 8,1 секунды (и не обрабатывает отрицательные числа, но это больше не проблема для этого исследования).

Примечание

В этом ответе используются следующие пакеты: Vector, attoparsec, text и vector-algorithms. Также обратите внимание на то, что на моем аппарате выполняется бесплатная версия с использованием timsort на 2,8 секунды (редактирование: и 2 секунды с использованием pypy).

Текстовая версия

Я сорвал версию Daniel, перевел ее в Text (так что она обрабатывает различные кодировки) и добавила лучшую сортировку с использованием изменяемого 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 секунды (а также не обрабатывает негативы)

Возврат к Bytestring

Итак, теперь мы знаем, что мы можем сделать более общую программу быстрее, как быстро сделать ASCii-версию? Нет проблем!

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... так что я.

Ответ 3

Больше Pythonista, чем Haskellite, но я возьму удар:

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

• Большая часть вашего времени потрачена на создание копий списков и фрагментов списков. Операции с списком Python сильно оптимизированы, являясь одной из наиболее часто используемых частей языка, а также, как правило, довольно эффективны для составления списков, проводя большую часть времени на C-пространстве внутри интерпретатора Python. В 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) - это зверь.

Ответ 4

Это после того факта, но я думаю, что большая часть проблемы связана с написанием Haskell. Следующий модуль довольно примитивен - нужно использовать строителей, вероятно, и, конечно же, избегать смешного roundtrip через String для показа, - но он прост и заметно лучше, чем pypy с безупречным улучшенным питоном и лучше, чем 2 и 4 сек. Модули Haskell в другом месте на этой странице (это удивило меня, сколько они использовали списки, поэтому я сделал еще пару оборотов рукоятки.)

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

Я использую класс, рекомендованный для unboxed векторов из векторных алгоритмов. Использование Data.Vector.Unbox в той или иной форме явно является стандартным, наивным способом делать такие вещи - это новый Data.List(для Int, Double и т.д.). Все, кроме sort, раздражает Управление IO, которое, я думаю, все еще будет значительно улучшено, в частности, на конец записи. Чтение и сортировка вместе занимают около 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

Ответ 5

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

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

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

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

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

Ответ 6

я заметил некоторую проблему, которую все остальные не заметили по какой-то причине; у вас есть код 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)

по какой-то причине я не могу изменить роль getter/lesser в предложениях where, поэтому я должен был сделать это в let clauses. также, если он не рекурсивный хвост, дайте мне знать и исправьте его для меня (я еще не знаю, как работает хвостохранилище)

теперь вы должны сделать то же самое для кода python. Я не знаю python, поэтому я не могу сделать это за вас.

EDIT: на самом деле такая функция уже существует в Data.List, называемом раздел. Обратите внимание, что это доказывает необходимость такой функции, потому что иначе она не будет определена. это сжимает код:

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

Ответ 7

Python действительно оптимизирован для такого рода вещей. Я подозреваю, что у Хаскелла нет. Здесь похожий вопрос, который дает некоторые очень хорошие ответы.