Stabilní vs nestabilní třídění

V obchodě 2 jsme zaznamenali problém při spuštění našich testovacích souprav Rails v našich dvou hlavních vývojových prostředích, v systému Mac OS X jsme měli test, který by neustále selhal, zatímco v systému Linux by pokaždé vyhověl, což způsobem dokazuje starý software vývojové pořekadlo o důležitosti vývojových strojů co nejpodobnější těm, na kterých bude běžet váš výrobní kód.

Při vyšetřování jsme zjistili, že problém spočíval v tom, jak konkrétní test očekával, že prvky budou seřazeny.

Co se dělo

Základní rozdíl mezi algoritmy stabilního třídění a nestabilními algoritmy spočívá v tom, že stabilní algoritmy zajišťují zachování původního pořadí prvků při třídění podle nejedinečné hodnoty, která sdružuje více než jeden prvek dohromady. To je v podstatě to, co jsme testovali, že prvky byly roztříděny do skupin a že v každé skupině zůstaly v původním pořadí (pořadí, v jakém byly přidány).

Nejjednodušší způsob, jak vidět tento rozdíl, je seřadit podle nejedinečné hodnoty, která definuje skupinu prvků, například pole „naléhavosti“ na úkolu. Pokud funkce třídění bere v úvahu pouze toto pole naléhavosti, je konečné uspořádání dvou prvků se stejnou naléhavostí ponecháno na milosti použitého algoritmu a není zaručeno, že jejich původní pořadí bude zachováno. Dalším příkladem je třídění podle prvního písmene slova namísto celého slova. Jakýkoli třídicí algoritmus vám poskytne správně seřazené pole, ale pouze stabilní algoritmus zachová původní pořadí prvků v každé skupině.

Vytvářeli jsme řadu objektů (představujících dokumenty), které by pak byly seřazeny podle jejich „typu“ (alfanumerický řetězec), které nemusely být v rámci pole jedinečné (např. Dva dokumenty by mohly mít typ „smlouvy“). ). V naší specifikaci jsme však očekávali, že dokumenty stejného typu zůstanou ve stejném pořadí, v jakém jsme je přidali do pole. Na našich linuxových počítačích a na CI to fungovalo tak, jak bylo zamýšleno, na našich počítačích Mac tomu tak nebylo.

Proč bylo chování odlišné

K problému došlo v naší aplikaci Rails, takže jsme určili kořenovou příčinu spuštěním úžasného nástroje zvaného Pry, který zkontroluje zdrojový kód za metodou Ruby sort. Třídění probíhá díky volání funkce qsort C. V systému Mac OS X to ve skutečnosti používá algoritmus rychlého třídění, jak název napovídá, což není ze své podstaty stabilní. Ve specifickém případě implementace Mac OS X (který zase vychází z FreeBSD) je nestabilní.

Tuto nestabilitu vidíme v akci, pokud vezmeme v úvahu následující pole [21, 12, 47, 41, 33, 11, 13, 31, 43]. Při třídění podle první číslice v systému Mac OS X, buď v C (pomocí qsort) nebo v Ruby (sort nebo sort_by), dostaneme [12, 13, 11, 21, 33, 31, 47, 43, 41] zpět a i když je to ve skutečnosti seřazeno podle první číslice, vidíme, že 11 následuje 13 v konečném poli, i když v původním poli se ve skutečnosti objevuje před ním. 41 a 43 se také přepnou v konečném poli. Zde je ukázka implementace rychlého řazení systému Mac OS X v akci, která přesně ukazuje toto chování:

Vidíme, že když se 13 zamění se 47, vymění se za 11, což skončí po 13 ve finálním poli.

Aniž bychom šli do přísných důkazů stability / nestability, vidíme, že je to rychlé řazení několika nesousedních ukazatelů k výměně prvků, které jim umožňují vypadnout z původního pořadí a smíchat se.

Na rozdíl od názvu napovídá, qsort není nutně rychlé řazení na všech operačních systémech. Mats Linander má velmi pěkný článek o všech rozdílech v implementacích qsort v celé řadě různých knihoven.

Pokud jde o implementaci GLIBC (ta, kterou používá většina distribucí Linuxu), zmiňuje:

Tento qsort () je zajímavý v tom, že se vyhýbá quicksort ve prospěch sloučení.

Ano, je tu rub!

Je to opravdu zajímavé, protože sloučení je ve skutečnosti stabilní! Pokud spustíme qsort () (nebo sort_by v ruby) na našem vzorovém poli z předcházejícího na počítači se systémem Linux, opět třídění podle první číslice a ne celého čísla, vidíme, že pro náš příklad je algoritmus ve skutečnosti stabilní (vrací [12, 11, 13, 21, 33, 31, 47, 41, 43]). Naše testy prošly, protože naše pole bylo tříděno podle očekávání, seskupovalo naše dokumenty, ale udržovalo je v původním pořadí mezi podobnými dokumenty. Sloučit řazení porovnává prvky s prvky přímo sousedícími s nimi, proto nedochází k „skákání“, které by mohlo potenciálně změnit původní uspořádání. Zde je ilustrovaný příklad:

GLIBC je „qsort ()“, což je vlastně sloučení

Co jsme změnili

Chování kódu a testy by měly být co možná reprodukovatelné a deterministické, namísto umožnění neúspěšných testů na našich počítačích Mac jsme problém vyřešili. Samotná Ruby však neposkytuje žádné jednoduché alternativy, které by zaručovaly stabilitu řazení, takže jsme přišli s vlastním řešením (pravděpodobně) nejjednodušším.

Pokračovali jsme v používání Rubyho řazení, ale místo třídění výhradně podle našeho neobvyklého pole bychom také brali v úvahu index každého prvku v původním poli. Pokud bychom tedy měli při třídění dva prvky „svázané“, vždy by díky různým indexům vždy skončily v pořadí, v jakém byly původně.

Tento obrázek ukazuje použité řešení. Důvod, proč bylo pro třídění použito pole prvku a jeho indexu namísto jakéhokoli zřetězení prvku a indexu, je to, že se nemusíme obávat jakéhokoli čalounění v případě, že různé prvky mají různou velikost / délku .

Stabilní třídění nám dalo deterministické chování a absolvování testů ve všech našich prostředích, přesně tak, jak by mělo být.

Ahoj, my jsme store2be, berlínský startup, který buduje tržiště s možností SaaS pro krátkodobý maloobchodní prostor. Pokud se vám líbí to, co zveřejňujeme, možná budete chtít navštívit technickou stránku obchodu store2be nebo sledovat náš střední kanál.