Оповещение спойлера: это связано сЗадача 14 от проекта Эйлер.

Следующий код занимает около 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 1 ГБ выделяется (!), Дляn = 1,000,000 13 ГБ (!!) выделяется.

Тогда снова,-sstderr показывает, что хотя было выделено много байтов, общее использование памяти составило 1 МБ, а производительность составила 95% и более, поэтому, возможно, 13 ГБ - это красная сельдь.

Я могу думать о нескольких возможностях:

Что-то не так строго, как должно быть. Я уже обнаружилfoldl1', но, может быть, мне нужно сделать больше? Можно ли отметитьcollatz как строгий (разве это имеет смысл?

collatz не оптимизировать хвостовой вызов. Я думаю, что это должно быть, но не знаю, как подтвердить.

Я думаю, что компилятор не выполняет некоторые оптимизации - например, только два результатаcollatz должны быть в памяти в любое время (максимальный и текущий)

Какие-либо предложения?

Это в значительной степени дубликатПочему это выражение Хаскелла такое медленное?Правда, отмечу, что быстрое 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

И -сстдерр:

./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 (не мое, взятое с форумов Project Euler с удаленной памяткой):

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 );
  }
}