Vybrat si mezi naší a KACTL implementací

trinerdi / icpc-notebook

The ACM-ICPC notebook of our team "Tři nerdi"

MIT License

2 stars 1 forks source link

Vybrat si mezi naší a KACTL implementací #43

Closed vvolhejn closed 6 years ago

vvolhejn commented 6 years ago

Většinu toho, co máme my, má i KACTL, takže bychom jednu z variant měli vyhodit.

FFT: oboje je rekurzivní, ale oni používají valarray, což bude asi rychlejší
NTT: jejich skoro určitě rychlejší, je sice rekurzivní, ale nekopíruje pole
Flow: my Dinic, oni Push-relabel, nevím, co je rychlejší
numth: rychlost bude asi podobná, jde spíš o stručnost/návaznost kódu. Můžeme nějak skloubit oboje dohromady.
HLD: momentálně jsme vyřadili jejich.

RichardHladik commented 6 years ago

Co se týče FFT, jejich je asi 3–4× rychlejší a zdá se, že dává stejné výsledky. Jejich NTT je rychlejší asi 4×, ale radši bych ho ještě otestoval. Na vzorových příkladech odpovídalo stejně, ale naivní násobení na konci benchmarkového testu dávalo odlišné výsledky. Přiznávám, že jsem to dál moc nezkoumal.

vvolhejn commented 6 years ago

Na SPOJ - FASTFLOW běží Push-Relabel rychleji, tak tam dám ten. Nevím, jestli to je reprezentativní (můžou tam být hluboké grafy, přitom v úlohách bývají mělké), ale zatím nic lepšího nemám a není to tak důležité.

Čas je 0.17 vs 0.13, takže rozdíl není dramatický.

vvolhejn commented 6 years ago

Zbývá ještě NTT a teorie čísel. Na ty zakládám zvláštní issues, #53 a #54.