• mina86.com

  • Categories
  • Code
  • Contact
  • Treasure Hunt a szybkość D

    Posted by Michał ‘mina86’ Nazarewicz on 10th of January 2009 | (cite)

    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ł… ;)