Подтвердить что ты не робот

Почему эта программа Haskell намного медленнее, чем эквивалентная Python?

Как часть задачи программирования, мне нужно прочитать из stdin последовательность целых чисел, разделенных пробелами (в одной строке), и напечатать сумму этих целых чисел в stdout. Эта последовательность может содержать целых 10 000 000 целых чисел.

У меня есть два решения для этого: один написан в Haskell (foo.hs), а другой эквивалентный, написанный на Python 2 (foo.py). К сожалению, (скомпилированная) программа Haskell последовательно медленнее, чем программа Python, и я затрудняюсь объяснить несоответствие производительности между двумя программами; см. раздел Benchmark ниже. Во всяком случае, я ожидал, что у Haskell хватит сил...

Что я делаю неправильно? Как я могу объяснить это несоответствие? Есть ли простой способ ускорить мой код Haskell?

(Для информации я использую MacBook Pro середины 2010 года с оперативной памятью 8 ГБ, GHC 7.8.4 и Python 2.7.9.)

foo.hs

main = print . sum =<< getIntList

getIntList :: IO [Int]
getIntList = fmap (map read . words) getLine

(скомпилирован с ghc -O2 foo.hs)

foo.py

ns = map(int, raw_input().split())
print sum(ns)

Benchmark

В дальнейшем test.txt состоит из одной строки из 10 миллионов целых чисел, разделенных пробелами.

# Haskell
$ time ./foo < test.txt 
1679257

real    0m36.704s
user    0m35.932s
sys     0m0.632s

# Python
$ time python foo.py < test.txt
1679257 

real    0m7.916s
user    0m7.756s
sys     0m0.151s
4b9b3361

Ответ 1

read медленный. Для массового разбора используйте примитивы bytestring или text или attoparsec.

Я немного сравнился. Ваша исходная версия работает на 23,9 сек на моем компьютере. Версия ниже выполнялась в 0,35 secs:

import qualified Data.ByteString.Char8 as B
import Control.Applicative
import Data.Maybe
import Data.List
import Data.Char

main = print . sum =<< getIntList

getIntList :: IO [Int]
getIntList =
    map (fst . fromJust . B.readInt) . B.words <$> B.readFile "test.txt"

Специализируя анализатор в вашем файле test.txt, я мог бы сократить время выполнения до 0,26 сек:

getIntList :: IO [Int]          
getIntList =
    unfoldr (B.readInt . B.dropWhile (==' ')) <$> B.readFile "test.txt"

Ответ 2

Прочитано медленно

Быстрое чтение, из этого ответа, приведет вас к 5,5 секундам.

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

Строки - это связанные списки

В Haskell тип String является связанным списком. Использование упакованного представления (bytestring, если вы действительно хотите только ascii, но Text также очень быстро и поддерживает unicode). Как показано в этом ответе, производительность должна быть шеей и шеей.

Ответ 3

Я бы рискнул догадаться, что большая часть вашей проблемы на самом деле words. Когда вы map read . words, то, что вы на самом деле делаете, это:

  • Отсканируйте вход, который ищет пространство, создавая список не-пробелов во время вашей работы. Существует много разных типов пробелов и проверка любого символа, который не является общим типом пространства, дополнительно включает в себя внешний вызов функции C (медленный). Я планирую исправить это когда-нибудь, но я еще не добрался до него, и даже тогда вы все равно будете строить и списывать списки без уважительной причины и проверять пробелы, когда вы действительно хотите проверить цифры.
  • Прочитайте список накопленных символов, чтобы попытаться сделать из них номер. Произведите число. Накопленный список теперь становится мусором.
  • Вернитесь к шагу 1.

Это довольно смешной способ продолжения. Я считаю, что вы можете даже лучше использовать что-то ужасное, как reads, но было бы разумнее использовать что-то вроде ReadP. Вы также можете попробовать более удобные виды вещей, такие как анализ на основе потоков; Я не знаю, поможет ли это много или нет.