Bejegyzés

QuickSort – ismét felfedeztük

Elméleti szinten oktatják a rendező algoritmusokat. Sok geek (megszállott) ennek jelentősséget is tulajdonít, pedig már nem számít. Gondoltuk a múlt hétig.

Elmúltak azok az idők, amikor 64kB RAM állt rendelkezésre és nagyon hatékony, gyakorlatilag kihegyezett algoritmust kellett írni mondjuk 200 dolgozó bérszámfejtési adatainak kezelésére. És nem mindenki tudta ezt megcsinálni.
Jelenleg az igazán sok adatot adatbázisokban kezeljük, nem számít a memória, a szerverben legyen sok.

A fejlesztők pedig 4-6 éve (Java-sok régebben) már túlléptek azon, hogy a numerikus analízisben megismert elveket kelljen ismerniük, hogy használható programot készítsenek. Mert beköszöntött a keretrendszerek kora. Ebben minden általánosan használt funkció már megírásra került, sőt eszközök is vannak arra, hogy a hiányzó részeket se tudjuk rosszul megírni (Generics, Interface, etc.)

Jó lenne ha emlékeznék, de nem fog menni. Valamikor a keretrendszer által támogatott rendező algoritmusok (Generic List Sort()) helyett sajátot készítettünk. (Ennek oka, hogy a BindingList-ben nincs sort, de ez mellékes). A saját pedig – minden bizonnyal – “pár napig jó lesz kipróbálni” szemlélet alapján egy gyors buborék rendezés lett. 4 sor, lehetetlen tévedni. Működött is. Majd a pár napból egy év lett.

Nem is lett volna baj, minden szépen működött, az SQL szerver rendesen kezelte a 80.000 terméket ügyfelünknél. Egészen addig, míg a 80.000 termék több, mint 5000 (!!!) gyártó alá került besorolásra. Ekkor a termékkiválasztó ablak megnyitása 30-50mp-et vett igénybe. A konzulens kollégák jelezték, hogy ez nem fatális hiba, emiatt nem kell azonnali verziót közzétenni, de minket mégis izgatott a dolog…

Quick Sort

És kb. egy órába telt, mire kiderült, hogy nem az adatbázis műveletek lassúak, nem is az 5000 gyártó combobox-ba feltöltése (valóságban más felületi elem, de példaképpen legyen combobox), hanem valahol belül egy adatátadás. És ekkor jött a homlokhoz csapás. A bubble-sort 5000 elem esetén statisztikailag 5000 x 2500 = 12.5M összehasonlítást végez és ennyi cserét is, ha kell. Ennek pedig ideje van. Egész számok helyett objektumok esetén még inkább.

A dolog sikerrel zárult, mert 3 órányi munka után a keretrendszerünk egy operáción esett át és a gyomor (körülbelül ez felel meg a rendező algoritmusoknak) újra egészségesen viselkedik. Persze újra felidézve tanulmányainkat rájöttünk, hogy a már rendezett adatokat a QSort nem is rendezi be újra, azaz még hatékonyabb lesz a működés.

Kis adatmennyiségek esetén nincs szerepe a fentieknek, de ott sem árt egy kis performancia-tuning.