Сумма всех чисел от одного до миллиарда в Haskell
В настоящее время я догоняю Haskell, и я до сих пор впечатлен. В качестве супер простого теста я написал программу, которая вычисляет сумму до миллиарда. Чтобы избежать создания списка, я написал функцию, которая должна быть хвостовой рекурсивной
summation start upto
| upto == 0 = start
| otherwise = summation (start+upto) (upto-1)
main = print $ summation 0 1000000000
запустив это с -O2, я получаю на моей машине время около ~ 20 секунд, что меня удивило, так как я думал, что компилятор будет более оптимизирован. Для сравнения я написал простую программу на С++
#include <iostream>
int main(int argc, char *argv[]) {
long long result = 0;
int upto = 1000000000;
for (int i = 0; i < upto; i++) {
result += i;
}
std::cout << result << std::end;
return 0;
}
компиляция с clang++ без оптимизации времени выполнения ~ 3 сек. Поэтому мне было интересно, почему мое решение Haskell так медленно. У кого-нибудь есть идея?
В OSX:
clang++ --version:
Apple LLVM version 7.0.2 (clang-700.1.81)
Target: x86_64-apple-darwin15.2.0
Thread model: posix
ghc --version:
The Glorious Glasgow Haskell Compilation System, version 7.10.3
Ответы
Ответ 1
Добавление подписи типа сократило мое время выполнения с 14.35 секунд до 0.27. Теперь он быстрее, чем С++ на моей машине. Не следует полагаться на дефолт по типу, когда имеет значение производительность. Ints не предпочтительнее, скажем, для моделирования домена в веб-приложении, но они великолепны, если вам нужен жесткий цикл.
module Main where
summation :: Int -> Int -> Int
summation start upto
| upto == 0 = start
| otherwise = summation (start+upto) (upto-1)
main = print $ summation 0 1000000000
[1 of 1] Compiling Main ( code/summation.hs, code/summation.o )
Linking bin/build ...
500000000500000000
14.35user 0.06system 0:14.41elapsed 100%CPU (0avgtext+0avgdata 3992maxresident)k
0inputs+0outputs (0major+300minor)pagefaults 0swaps
Linking bin/build ...
500000000500000000
0.27user 0.00system 0:00.28elapsed 98%CPU (0avgtext+0avgdata 3428maxresident)k
0inputs+0outputs (0major+171minor)pagefaults 0swaps
Ответ 2
Пропустите выпад, если вы не хотите увидеть неоптимизированный (не-O2) вид.
Давайте посмотрим на оценку:
summation start upto
| upto == 0 = start
| otherwise = summation (start+upto) (upto-1)
main = print $ summation 0 1000000000
- >
summation 0 1000000000
- >
summations (0 + 1000000000) 999999999
- >
summation (0 + 1000000000 + 999999999) 999999998
- >
summation (0 + 1000000000 + 999999999 + 999999998) 999999997
Забастовкa >
EDIT: я не видел, что вы скомпилировали с -O2, поэтому выше не происходит. Аккумулятор, даже без каких-либо аннотаций строгости, в большинстве случаев достаточно с правильными уровнями оптимизации.
О нет! Вы храните один миллиард номеров в большом банке, который вы не оцениваете! Tisk! Существует множество решений с использованием аккумуляторов и строгости - кажется, что большинство ответов stackoverflow с чем-либо рядом с этим вопросом будет достаточным, чтобы научить вас в дополнение к библиотечным функциям, таким как fold{l,r}, которые помогут вам избежать написания собственных примитивных рекурсивных функций. Поскольку вы можете посмотреть вокруг и/или спросить об этих концепциях, я перейду к преследованию с этим ответом.
Если вы действительно хотите сделать это правильно, то вы бы использовали список и узнали, что компиляторы Haskell могут выполнять "обезлесение", что означает, что список миллиардов элементов никогда не выделяется:
main = print (sum [0..1000000000])
Тогда:
% ghc -O2 x.hs
[1 of 1] Compiling Main ( x.hs, x.o )
Linking x ...
% time ./x
500000000500000000
./x 16.09s user 0.13s system 99% cpu 16.267 total
Прохладный, но почему 16 секунд? По умолчанию эти значения являются целыми (целые числа GMP для компилятора GHC) и медленнее, чем машина Int. Используется Int!
% cat x.hs
main = print (sum [0..1000000000] :: Int)
[email protected] /tmp% ghc -O2 x.hs && time ./x
500000000500000000
./x 0.31s user 0.00s system 99% cpu 0.311 total
