Я пытался решить головоломку «Word Nubmers» ITA Software , используя метод грубой силы.Похоже, моя версия на Haskell более чем в 10 раз медленнее, чем версия на C # / C ++.
Ответ
Благодаря ответу Брайана О'Салливана я смог«исправить» мою программу на приемлемую производительность.Вы можете прочитать его код, который намного чище, чем мой.Я собираюсь обрисовать ключевые моменты здесь.
Int - это Int64 в Linux GHC x64.Если вы не unsafeCoerce, вы должны просто использовать Int.Это избавляет вас от необходимости fromIntegral.Выполнение Int64 в 32-битном Windows GHC просто штопать медленно, избегайте этого.(На самом деле это не вина GHC. Как упоминалось в моем блоге ниже, 64-битные целые числа в 32-битных программах в целом медленны (по крайней мере, в Windows)) -fllvm или -fvia-C дляпроизводительность. - Предпочтение от
quotRem до divMod, quotRem уже достаточно.Это дало мне ускорение на 20%. - В общем, предпочитайте от
Data.Vector до Data.Array в качестве «массива» - Свободно используйте шаблон обертка-рабочий.
Вышеуказанных пунктов было достаточно, чтобы дать мне примерно 100% прирост по сравнению с моей первоначальной версией.
В своем блоге я подробно описал пошаговый иллюстрированный пример того, какЯ повернул оригинальную программу, чтобы соответствовать программе Брайана.Там также упоминаются и другие моменты.
Оригинальный вопрос
(Это может звучать как пост "Можешь ли ты сделать работу для меня", но я утверждаю, что такой конкретный примербудьте очень поучительны, поскольку профилирование производительности на Haskell часто воспринимается как миф)
(как отмечалось в комментариях, я думаю, что я неправильно истолковал проблему. Но кого это волнует, мы можем сосредоточиться на производительности в другой проблеме)
Вот моя версия краткого описания проблемы:
A wordNumber is defined as
wordNumber 1 = "one"
wordNumber 2 = "onetwo"
wordNumber 3 = "onethree"
wordNumber 15 = "onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen"
...
Problem: Find the 51-billion-th letter of (wordNumber Infinity); assume that letter is found at 'wordNumber x', also find 'sum [1..x]'
С точки зрения императива наивный алгоритм должен иметь 2 счетчика, один для суммы чисел и один для суммыдлин.Продолжайте считать длину каждого wordNumber и «break», чтобы вернуть результат.
В C # реализован императивный метод грубой силы: http://ideone.com/JjCb3. Требуется около 1,5 минут, чтобы найти ответ намой компьютер.Есть также реализация C ++ , которая выполняется на моем компьютере за 45 секунд.
Затем я реализовал версию Haskell с перебором: http://ideone.com/ngfFq. Он не может завершить вычисление за 5минут на моей машине.(Ирония: в нем больше строк, чем в версии C #)
Вот профиль -p программы на Haskell: http://hpaste.org/49934
Вопрос: Как заставить его работать по сравнению с C #версия?Есть ли очевидные ошибки, которые я делаю?
(Примечание: я полностью осознаю, что грубое принуждение не является правильным решением этой проблемы. Я в основном заинтересован в том, чтобы версия на Haskell работала по сравнению с версией C #Прямо сейчас это как минимум в 5 раз медленнее, поэтому, очевидно, я упускаю что-то очевидное)
(Примечание 2: Кажется, что не происходит утечка пространства. Программа работает с постоянной памятью (около 2 МБ) на моем компьютере)
(Примечание 3: я компилирую с помощью `ghc -O2 WordNumber.hs)
Чтобы сделать этот вопрос более удобным для читателя, я включил" суть "двух версий.
// C#
long sumNum = 0;
long sumLen = 0;
long target = 51000000000;
long i = 1;
for (; i < 999999999; i++)
{
// WordiLength(1) = 3 "one"
// WordiLength(101) = 13 "onehundredone"
long newLength = sumLen + WordiLength(i);
if (newLength >= target)
break;
sumNum += i;
sumLen = newLength;
}
Console.WriteLine(Wordify(i)[Convert.ToInt32(target - sumLen - 1)]);
-
-- Haskell
-- This has become totally ugly during my squeeze for
-- performance
-- Tail recursive
-- n-th number (51000000000 in our problem) -> accumulated result -> list of 'zipped' left to try
-- accumulated has the format (sum of numbers, current lengths of the whole chain, the current number)
solve :: Int64 -> (Int64, Int64, Int64) -> [(Int64, Int64)] -> (Int64, Int64, Int64)
solve !n !acc@(!sumNum, !sumLen, !curr) ((!num, !len):xs)
| sumLen' >= n = (sumNum', sumLen, num)
| otherwise = solve n (sumNum', sumLen', num) xs
where
sumNum' = sumNum + num
sumLen' = sumLen + len
-- wordLength 1 = 3 "one"
-- wordLength 101 = 13 "onehundredone"
wordLength :: Int64 -> Int64
-- wordLength = ...
solution :: Int64 -> (Int64, Char)
solution !x =
let (sumNum, sumLen, n) = solve x (0,0,1) (map (\n -> (n, wordLength n)) [1..])
in (sumNum, (wordify n) !! (fromIntegral $ x - sumLen - 1))