<div dir="ltr">Kiitos avustasi. Kokeilin tuossa 10k limittiä ja 1.2M merkkiä meni sillä noin 27s. 1k limitillä noin 6s. Kyllähän näillä viritelmillä jo pärjää. Kokeilen uutta versiotasi kun olet tehnyt korjailuja. Pitää ilmeisesti kääntää itse kun homebrew näytti edelleen tarjoavan 3.8 versiota. Mutta jospa se onnistuu.<div><br></div><div>Katsoin itsekin, että tuo näytti hieman exponentiaaliselta ajan kasvulta. Mutta eipä sitä koskaan tiedä. Jos alkaa selviämään niin hyvä juttu.</div><div><br></div><div>Miten parsit tuota UTF8:aa? Onko siinä jokin kirjaston rajapinta mihin ei voi antaa omia rajoja? Esim. pitää indeksi dokumentin byte taulukkoon ja parsia UTF8 merkkejä indeksistä alkaen kunnes kunnes tulee se whitespace ja siinä on token? Sitten tästä uusi indeksi tauluun? Ihan hatusta nämä heitot kyllä</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2016-01-06 12:40 GMT+02:00 Harri Pitkänen <span dir="ltr"><<a href="mailto:hatapitk@iki.fi" target="_blank">hatapitk@iki.fi</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Wednesday 06 January 2016 12:13:32 Harri Pitkänen wrote:<br>
> > 1.5k noin 0.01s<br>
> > 25k noin 1s<br>
> > 30k noin 2s<br>
> > 40k noin 3s<br>
> > 60k noin 5s<br>
> > 65k noin 7s<br>
> > 115k noin 20s<br>
> > 270k noin 2min 8s eli 128s<br>
> > 415k noin 5min 20s eli 320s<br>
><br>
> Tämä näyttää viittaavan melko selvästi siihen, että aikaa kuluu<br>
> neliöllisesti syötteen pituuteen nähden (pituuden kaksinkertaistaminen<br>
> nelinkertaistaa ajankäytön). Teoriassa tämän algoritmin aikavaativuuden<br>
> pitäisi olla lineaarinen, joten bugihan siellä jossain on.<br>
><br>
> Yritän korjailla loppuviikon aikana.<br>
<br>
</span>Taisin löytää ongelman syyn: libvoikon funktiossa voikkoNextTokenCstr tehdään<br>
UTF-8-stringin dekoodausta vähän liikaa eli jokaisen tokenin alusta koko<br>
annetun tekstin loppuun. Tämä on teoriassa tarpeellistakin, koska rajapinta on<br>
sellainen, ettei tuota dekoodattua stringiä voida säilyttää missään kutsujen<br>
välillä, ja toisaalta ei voida olla varmoja etteikö se koko tuhansien merkkien<br>
kokonaisuus voisikin olla yhtä sanaa.<br>
<br>
Ihan triviaalia korjausta tuohon ei siis ole tehtävissä, mutta pienellä<br>
väännöllä tuon pitäisi taipua pahimmassakin tapauksessa vaativuuteen n log(n)<br>
ja tyypillisessä tapauksessa lineaariseksi. Palaan asiaan...<br>
<div class="HOEnZb"><div class="h5"><br>
Harri<br>
_______________________________________________<br>
voikko mailing list<br>
<a href="mailto:voikko@lists.puimula.org">voikko@lists.puimula.org</a><br>
<a href="http://lists.puimula.org/listinfo/voikko" rel="noreferrer" target="_blank">http://lists.puimula.org/listinfo/voikko</a><br>
</div></div></blockquote></div><br></div>