Предупреждение о спойлере: это связано с Problem 14 от Project Euler.Почему этот простой алгоритм haskell настолько медленный?
Следующий код занимает около 15 секунд для запуска. У меня есть нерекурсивное решение Java, которое работает за 1 секунду. Я думаю, я должен был бы получить этот код намного ближе к этому.
import Data.List
collatz a 1 = a
collatz a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
main = do
print ((foldl1' max) . map (collatz 1) $ [1..1000000])
Я профилированный с +RHS -p и заметил, что выделенная память велика, и растет как входные растет. За n = 100,000 выделено 1gb (!), Для n = 1,000,000 13gb (!!).
С другой стороны, -sstderr показывает, что, хотя было выделено большое количество байтов, общий объем использования памяти составлял 1 мб, а производительность составляла 95% +, поэтому, возможно, 13 ГБ является красно-серой.
Я могу придумать несколько возможностей:
Что-то не так строго, как это должно быть. Я уже обнаружил
foldl1', но, может быть, мне нужно сделать больше? Можно отметитьcollatz, как строгий (это вообще имеет смысл?collatzне хвост вызова оптимизации. Я думаю, что это должно быть, но не знают способ, чтобы подтвердить.компилятор не делает некоторые оптимизации, я думаю, что это надо - например, только два результата
collatzдолжны находиться в памяти в любой момент времени (макс и тока)
Любые предложения
?Это почти дубликат Why is this Haskell expression so slow?, хотя я буду замечать, что быстрое решение Java не должно выполнять никаких заметок. Есть ли способы ускорить это, не прибегая к этому?
Для справки, вот мой выход профилирования:
Wed Dec 28 09:33 2011 Time and Allocation Profiling Report (Final)
scratch +RTS -p -hc -RTS
total time = 5.12 secs (256 ticks @ 20 ms)
total alloc = 13,229,705,716 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
collatz Main 99.6 99.4
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF Main 208 10 0.0 0.0 100.0 100.0
collatz Main 215 1 0.0 0.0 0.0 0.0
main Main 214 1 0.4 0.6 100.0 100.0
collatz Main 216 0 99.6 99.4 99.6 99.4
CAF GHC.IO.Handle.FD 145 2 0.0 0.0 0.0 0.0
CAF System.Posix.Internals 144 1 0.0 0.0 0.0 0.0
CAF GHC.Conc 128 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.Internals 119 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 113 5 0.0 0.0 0.0 0.0
И -sstderr:
./scratch +RTS -sstderr
525
21,085,474,908 bytes allocated in the heap
87,799,504 bytes copied during GC
9,420 bytes maximum residency (1 sample(s))
12,824 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 40219 collections, 0 parallel, 0.40s, 0.51s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 35.38s (36.37s elapsed)
GC time 0.40s ( 0.51s elapsed)
RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 35.79s (36.88s elapsed) %GC time 1.1% (1.4% elapsed) Alloc rate 595,897,095 bytes per MUT second
Productivity 98.9% of total user, 95.9% of total elapsed
И решение Java (не мое, взят из форумов Проекта Эйлера с запоминанием удалено):
public class Collatz {
public int getChainLength(int n)
{
long num = n;
int count = 1;
while(num > 1)
{
num = (num%2 == 0) ? num >> 1 : 3*num+1;
count++;
}
return count;
}
public static void main(String[] args) {
Collatz obj = new Collatz();
long tic = System.currentTimeMillis();
int max = 0, len = 0, index = 0;
for(int i = 3; i < 1000000; i++)
{
len = obj.getChainLength(i);
if(len > max)
{
max = len;
index = i;
}
}
long toc = System.currentTimeMillis();
System.out.println(toc-tic);
System.out.println("Index: " + index + ", length = " + max);
}
}
Удивительно, что GHC не оптимизирует (с n 2) по (rshift n 1), как и любой уважающий себя компилятор C. Есть ли причина? –
@solrize: Меня это тоже удивило. – ehird