Haskell: Почему Int работает хуже, чем Word64, и почему моя программа намного медленнее, чем C?
Я читал статьюкак медленно Хаскелл играет с гипотезой КоллатцаЭто означает, что если вы продолжите умножать три и плюс один на нечетное число или делите четное число на два, вы в конечном итоге получите единицу. Например, 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
Программа, приведенная в этой статье, предназначена для расчета самой длинной последовательности Коллатца в заданном диапазоне. Версия C:
#include <stdio.h>
int main(int argc, char **argv) {
int max_a0 = atoi(argv[1]);
int longest = 0, max_len = 0;
int a0, len;
unsigned long a;
for (a0 = 1; a0 <= max_a0; a0++) {
a = a0;
len = 0;
while (a != 1) {
len++;
a = ((a%2==0)? a : 3*a+1)/2;
}
if (len > max_len) {
max_len = len;
longest = a0;
}
}
printf("(%d, %d)\n", max_len, longest);
return 0;
}
Компилируясь с Clang O2, он работает на моем компьютере в течение 0,2 с.
Версия на Haskell, приведенная в этой статье, генерирует всю последовательность в виде списка в явном виде, а затем вычисляет длину промежуточного списка. Это в 10 раз медленнее, чем версия на C. Однако, поскольку автор использовал LLVM в качестве бэкэнда, который я не установил, я не смог воспроизвести это. Используя GHC 7.8 и бэкэнд по умолчанию, он работает 10 секунд на моем Mac, что в 50 раз медленнее, чем версия C.
Затем я пишу версию, используя хвостовую рекурсию и не генерируя промежуточный список:
collatzNext :: Int -> Int
collatzNext a
| even a = a `div` 2
| otherwise = (3 * a + 1) `div` 2
collatzLen :: Int -> Int
collatzLen n = collatzIter n 0
where
collatzIter 1 len = len
collatzIter n len = collatzIter (collatzNext n) (len + 1)
main = do
print $ maximum $ [collatzLen x | x <- [1..1000000]]
Скомпилированный с GHC 7.8 и O2, он работает в течение 2 секунд, в 10 раз медленнее, чем версия C.
Интересно, когда я изменилсяInt
в аннотации типаWord
, он потратил только 1с, в 2 раза быстрее!
Я попробовал BangPatterns для явной строгой оценки, но заметного прироста производительности заметить не удалось - я думаю, строгий анализ GHC достаточно умен, чтобы справиться с таким простым сценарием.
Мои вопросы:
ПочемуWord
версия так быстрее по сравнению сInt
один?Почему эта программа на Haskell такая медленная по сравнению с C?