История изменений

Исправление quasimoto, 01.07.13 20:46 (текущая версия) :

С iostream'ом вообще вряд ли получится пройти на spoj.

Оно делается accepted, но уже не в топе, а в ... bottom, короче :) Неохота даже смотреть в чём там дело.

Ты кстати, на spoj запостил? Сколько получилось по времени?

13 место — ~1sec / ~5MB. Там много таких решений — наверно все пишут одно и то же тупо на std::map/std::multiset.

Моя реализация такая

(let ((*standard-input*  (sb-sys:make-fd-stream 0 :input  t :buffering :full))
      (*standard-output* (sb-sys:make-fd-stream 1 :output t :buffering :full))
      (*trace-output* *error-output*))
  (time (homo))
  (finish-output))

➜  spoj  ./homo-gen-in 10 10 | \time sbcl --noinform --noprint --disable-debugger --load "homo.lisp" > /dev/null
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  109,052 processor cycles
  0 bytes consed
  
0.26user 0.02system 0:00.29elapsed 97%CPU (0avgtext+0avgdata 207584maxresident)k
0inputs+0outputs (0major+6395minor)pagefaults 0swaps
➜  spoj  ./homo-gen-in 10000000 10 | \time sbcl --noinform --noprint --disable-debugger --load "homo.lisp" > /dev/null
Evaluation took:
  10.413 seconds of real time
  10.317433 seconds of total run time (10.200450 user, 0.116983 system)
  [ Run times consist of 0.192 seconds GC time, and 10.126 seconds non-GC time. ]
  99.08% CPU
  20,779,739,936 processor cycles
  3,519,986,224 bytes consed
  
10.46user 0.13system 0:10.70elapsed 99%CPU (0avgtext+0avgdata 347872maxresident)k
0inputs+0outputs (0major+10167minor)pagefaults 0swaps
➜  spoj  ./homo-gen-in 10000000 1000 | \time sbcl --noinform --noprint --disable-debugger --load "homo.lisp" > /dev/null
Evaluation took:
  12.103 seconds of real time
  11.902190 seconds of total run time (11.780209 user, 0.121981 system)
  [ Run times consist of 0.193 seconds GC time, and 11.710 seconds non-GC time. ]
  98.34% CPU
  24,151,750,796 processor cycles
  3,520,072,880 bytes consed
  
12.03user 0.14system 0:12.38elapsed 98%CPU (0avgtext+0avgdata 347984maxresident)k
0inputs+0outputs (0major+10670minor)pagefaults 0swaps
➜  spoj  ./homo-gen-in 10000000 1000000 | \time sbcl --noinform --noprint --disable-debugger --load "homo.lisp" > /dev/null
Evaluation took:
  16.913 seconds of real time
  16.648468 seconds of total run time (16.396507 user, 0.251961 system)
  [ Run times consist of 0.746 seconds GC time, and 15.903 seconds non-GC time. ]
  98.43% CPU
  33,749,201,068 processor cycles
  3,603,868,336 bytes consed
  
16.65user 0.27system 0:17.19elapsed 98%CPU (0avgtext+0avgdata 584656maxresident)k
0inputs+0outputs (0major+17579minor)pagefaults 0swaps
➜  spoj  ./homo-gen-in 10000000 1000000000 | \time sbcl --noinform --noprint --disable-debugger --load "homo.lisp" > /dev/null
Evaluation took:
  20.056 seconds of real time
  19.882977 seconds of total run time (18.828138 user, 1.054839 system)
  [ Run times consist of 2.491 seconds GC time, and 17.392 seconds non-GC time. ]
  99.14% CPU
  40,022,605,012 processor cycles
  4,191,032,800 bytes consed
  
19.09user 1.07system 0:20.34elapsed 99%CPU (0avgtext+0avgdata 2480352maxresident)k
0inputs+16outputs (0major+25761minor)pagefaults 0swaps

Так что запуск и измерение внешним time погоды не делает.

Не сильно хуже при большом разбросе (тогда оно вероятностно чаще hetero), но хуже при малом — я подозреваю, что у них там особый тест с малым разбросом (так что оно не всегда hetero). Ну и памяти больше.

Можешь попробовать продекларировать везде типы и declaim optimize/inline, ещё у тебя в -insert/-delete таблица вольно дёргается — у меня в случае MapShape ins за один проход доставляет итератор insert-ом и дальше всё константно, del — тоже за один проход доставляет find-ом итератор, _на котором_ (it) потом может быть выполнен erase — остальное константно.

Исходная версия quasimoto, 01.07.13 20:36: