🚀 go-pugleaf

Oelewapperke wrote:

> (meting met "for i in 5 50 500 5000; do echo $i:; time ./chessboard $i 5
> > /dev/null; done")
> 
> numVelden       numStars        chessboard      chessboardoptimized
> 5               5               0.000           0.000
> 50              5               0.010           0.000
> 500             5               1.100           0.010
> 5000            5               <te lang>       0.080
> 50000           5               <te lang>       0.630
> 
> (dit is dus met compileroptimalisaties af op een heel modern systeem, maar
> compileroptimalisaties kunnen het probleem alleen maar uitstellen naar
> grotere aantallen op lineaire basis, terwijl deze routine exponentieel
> sneller is dan de vorige oplossing) (daarmee bedoel ik dat als je
> numVelden verdubbeld het gegeven programma er 4x langer over doet, terwijl
> mijn versie er slechts dubbel zo lang over zal doen).

Van numVelden ^ 2 naar numVelden is geen exponentiele verbetering, maar 
slechts een lineaire. Je vergeet ook mee te rekenen dat het uitschrijven 
van een string die dubbel zo lang is ook ongeveer dubbel zo lang gaat duren 
(constante overhead niet meegerekend), _als_ je ook iets nuttig met die 
string gaat doen. Bij het wegschrijven van een string naar /dev/null maakt 
het normaal gezien niet uit hoe groot de string is, dus dat is een fout in 
je benchmark. Maw de orde blijft gelijk.

-- 
Nicolas Barbier