Treasure Hunt a szybkość D

Michał ‘mina86’ Nazarewicz | 10 stycznia 2009

Zachęcony wpisem GiMa postanowiłem pobawić się w Google Treasure Hunt. Z początku moje wrażenia były negatywne, ale to dlatego, że zacząłem od zadania sieci, które jest co najmniej denne. Archiwum też nie napawało optymizmem, już zacząłem się zastanawiać, czy wszystkie będą tak prymitywne — na szczęście nie były.

Robot — kolejne zadanie, za które sie wziąłem — przypomniał mi stare dobre czasy, gdy to na lekcjach rachunku prawdopodobieństwa z umiłowaniem wyliczaliśmy na ile sposób można dojść z jednego rogu do drugiego albo ile jest n elementowych ciągów o wyrazach naturalnych, których suma wynosi m.

Na stworzenie tego wpisu zdecydowałem się jednak nie po to, aby się chwalić jaki to jestem mądry. Sprowokowało mnie do tego rozwiązanie czwartego zadania, w którym GiM wydawał się sugerować jakoby język D był niezmiernie szybki. Cóż… niechaj mój pomiar mówi sam za siebie (program napisany w C, procesor Sempron 2500+ 1,4GHz):

$ time ./sieve 20000000
max = 20000000
sequence = { 799, 415, 63, 31 }
count = 1270607
largest = 19999999
6814289

real    0m0.916s
user    0m0.817s
sys     0m0.077s

Jak widać na wolniejszym komputerze program znalazł przeszło 3 razy więcej liczb pierwszych w czasie krótszym od programu GiMa.

Teraz tylko zachodzę w głowę o co biega z tą koszulką, co to GiM ją niby dostał… ;)