🚀 go-pugleaf

Oelewapperke wrote:

> Nicolas Barbier wrote:
> 
>> 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.
> 
> Nieuwe benchmark met writen naar een file (wat erger is dan schrijven naar
> het scherm, want bij het scherm kan hij beslissen van grote hoeveelheden
> toch naar /dev/null te schrijven) :

Dit zal in normale omstandigheden de orde enkel omlaag halen, wat niet het 
geval is (zie verder).

> aantal          Normaal                 Optimized
> 5               0.000                   0.000
> 50              0.020                   0.000
> 500             1.090                   0.020
> 1000            4.460                   0.010
> 2000            17.780                  0.040
> 
> Het gaat erom dat er een (grote, potentieel 1 jiffie) kost geassocieerd is
> met elke methode oproep, en als je er voor elk karakter 1 doet, verlies je
> veel meer tijd dan als je er maar 1 per lijn doet.

Aan de tekst van jou voorlaatste post te zien heb je het over orde van 
efficientie: "kunnen het probleem alleen maar uitstellen naar 
grotere aantallen". Die verandert volgens mij dus niet door jou 
optimalisatie.

Afgezien van het feit dat de orde pas bij benchmarks zichbaar wordt bij 
veel grotere getallen, kan je het wegschrijven naar een file van zulke 
kleine hoeveelheden gegevens (ze passen waarschijnlijk in je RAM) niet 
gebruiken als benchmark. Het programma beeindigt namelijk al voordat de 
gegevens echt op je schijf terecht gekomen gaan zijn.

Btw: ik vecht niet aan dat het efficienter is, enkel dat de orde van 
efficientie niet beter is (als je ervan uitgaat dat elk geoutput symbool 
minstens 1 keer gebruikt wordt om er ook daadwerkelijk iets mee te doen).

Mijn benchmark van jou code:

Alles wordt naar een willekeurige X terminal-emulator geschreven, waarvan 
ik denk dat het ongeveer lineaire tijd vraagt in het aantal karakters 
(vooral omdat er verhoudingsgewijs niet veel return-karakters bijzitten). 
De terminal bleef gedurende heel de benchmark op dezelfde positie zichbaar 
op mijn scherm. Niet erg wetenschappelijk, maar wetenschappelijker dan het 
naar een file schrijven argument IMO :-).

250     0m1.222s
500     0m5.513s
1000    0m27.067s
2000    1m52.107s

Dat lijkt mij toch wel relatief kwadratisch.

-- 
Nicolas Barbier