sort -u

Szkriptek: Python, Perl, Bash, ...

Gyakran használtam eddig a sort|uniq parancspárt, míg egy hatalmas fájlnál el nem jutottam teljesítőképességnek határára (vagyis használatakor betelt a (nem kicsi) merevlemezem). Ekkor találtam ezt az oldalt, ami rámutat, hogy mennyivel jobb a fenti helyett inkább a sort -u parancsot használni: http://aplawrence.com/Unixart/sort-vs-uniq.html - A sort -u valóban létre tudta hozni a kívánt 110MB-os szövegfájlt.

Ha tudtok olyasféle trükk-gyűjteményről a weben, amivel (a fenti tényhez hasonlóan) érdemes szembesülni, írjátok meg!

  • 3015 megtekintés

( szemet | 2011. 03. 24., cs – 14:49 )

Ismertem, ami miatt nekem gyakran nem jó, hogy: a "-u"-val nem lehet számolni az előfordulásokat mint "uniq -c"-vel

A vinyód két okból nem elég talán:

- a sort alapesetben /tmp-t használ és neked talán /home partíción van valójában sok szabad helyed "-T"-vel állíthatod át (-T ./ide_keruljon_a_temp_file )

- lehet tömöríteni is az ideiglenes fájlokat, egy gyors tömörítővel és redundáns fájlokkal még időt is nyerhetsz annyira lecsökken az IO: "--compress-program=lzop"

( lx | 2011. 03. 24., cs – 17:22 )

Ha a kimenetben nem számít a rendezettség, csak az egyediség fontos, az awk gyorsabb lehet, mint a sort -u -- valószínűleg nem mindenki számít erre.


# hogy ne torzítson a file cache
> for i in 1 2 3; do cat text > /dev/null; done

> time sort -u text | wc -l
671

real 0m0.069s
user 0m0.025s
sys 0m0.005s

> time awk '{a[$0]}; END {for (i in a) { print i}}' text | wc -l
671

real 0m0.018s
user 0m0.011s
sys 0m0.005s

Nem is a program(ozókat) gondoltam versenyeztetni - csak ötletet adni arra az esetre ha számít az idő.

Nem terveztem külön leírni, de ha már itt vagyunk... Megismételtem a tesztet egy 120 megás fájllal is (kb. 1m sor, kb. 100e az egyedi): sort -u kb. 2p 20mp, awk kb. 6mp. Ha nem kellene a sorrend, csak a duplák kiszűrése, kibírnám fair play díj nélkül a dolgok ilyetén állása mellett. ;)

"awk megoldás ciki lehet ha nincs elég memória."

Bizony, és 10, de akár csak 5 éve sem álltam volna elő ilyen ötlettel, de lassan hozzászokom ahhoz a gondolathoz, hogy 1-2G alatti RAM-mal számítógép csak a bontóban fordul elő.

"+a cache-t root-ként így ürítjük a teszt előtt:

echo 3 > /proc/sys/vm/drop_caches"

Éppen az volt a cél, hogy a sort is, az awk is már fc-ben találja a fájlt, hogy ne álljon elő az, hogy a sort még lemezről olvas, az awk pedig a sort hagyatékából.

Közben rájöttem, hogy szándékosan előre felolvasod így összehasonlításra jó de valós futás modellezésére nem az igazi, mert abban benne van a file beolvasása is és ott lehet különbség sort és awk között.

Változnak az idők, ma már az esetek igen nagy részében tényleg belefér minden a memóriába...

Azt elmeséled mellékesen, hogy az interpretálásos - tehát - az awk példában hol van a rendezés? Mert én nem látom, ráadásul az eredeti írója oda is írta, hogy ha a rendezettség *nem* követelmény, csak az egyediség, akkor lehet az ő verziója jó. Konkrétan az awk egy "véletlenszerű" sorrendben fogja kidobálni a sorokat.

szerinted hogy működhet egy ilyen (nem feltétlen a konkrét awk)?
jön egy újabb sor, valahova el kell tárolnia, vagy ekkor vagy a kiíráskor figyelnie kell hogy volt-e már, tehát meg kell keresnie az addigiak közt (vagy valamilyen értelemben az összes sor között) az aktuálisat
ezt minek nevezed ha nem sorbarendezésnek?

nem az volt a kérdés hogy az awk hogy működik
ha hash akkor az NEM a jelen feladat, lehet ütközés, ennyi erővel a hagyományos sorbarendezés is mehetne hash-el és megint csak nincs különbség

(nem azt mondom hogy nem gyorsabb, egy kicsit tényleg lehet gyorsabb kisebb memóriaigény (nem méret*) miatt, de lényegében sorbarendezés, egyszerűen annyi a különbség hogy nem sorok hanem rövidebb hash-ek közt kell keresnie, a meg olyan hash-re gondolsz ami eleve az összes lehetőséget lefoglalja.. az itt szerintem nem lehetőség:) )

ps:
*:öö fáradt vagyok.. HA az awk tudná előre hogy majd mit kell majd kezdenie azzal a hashtömbbel (vagy mivel) akkor megtehetné hogy a bemeneti sorokat nem tárolja és ha olyan jön ami még nem volt kiírja, ekkor tényleg kevesebb memória kellene elvileg neki, de ettől még a keresés miatt marad lényegében sorbarendezés, HACSAK nem mondjuk egy 32bites hash mint bitmap ami még befér a memóriába, de az meg csúnya, tényleg lehetnek ütközések :)

Nem voltam pontos. Az awk asszociatív tömböt használ (azt már nem nézem meg, hogy hash van e mögötte), de abban biztos vagyok, hogy nem lehet ütközés. A feladatot nem jól értelemezed. Nem kell sorba rendezni, csak legyűjteni az egyedi sorokat. Ebből következik, hogy az asszociatív tömbnek semmi köze a sorba rendezéshez, viszont hatékony eszköz lehet a duplikált elemek (sorok) kiszűréséhez. (Igaz a sorrendiség elveszik)

hmm, megmondtad hogy az awk-os példa jó eredményt ír ki, de amiről elkezdtünk vitatkozni arra annyit írtál hogy nézzek utána.. én kezdtelek el érvekkel győzködni.. ez így kicsit vicces ;)

(félreértések lekerülése miatt: az előző hszm szerkesztése előtt csak az első kérdőmondat szerepelt ott :) )

Annyit kell tenned, hogy megnézed az asszociatív tömb definícióját. Nem akartam pontatlan definíciót írni mikor rengeteg jó definíciót lehet rá találni. Itt írnak példákat: http://www.thegeekstuff.com/2010/03/awk-arrays-explained-with-5-practic… itt a wikipedia definíció: http://en.wikipedia.org/wiki/Associative_array .

Én nem vitatkoztam :-) Az awk asszociatív tömb jó erre a feladatra, persze a korlátait figyelembe kell venni (a sorrend felborul, memória elfogyhat, lehet olyan hosszú sor amit már nem tud az awk kulcsként kezelni)

Szerinted miért nem jó az awk megoldás?

nem jóságról hanem sebességről volt szó

a szál elején páran azt mondják hogy kétszer gyorsabb hisz nem két program kell hozzá hanem egy, sort és uniq helyett awk

azért túloztam hogy érthető legyen min akadtam fenn, azt mondják azért gyorsabb mert nem kell sorrendben kiírni az adatot és ez _nyilvánvaló_, pedig te is csak annyit mondasz hogy azért gyorsabb mert a költséges sorbarendezés és uniq helyett egyetlent rövid lépést hajtasz végre: {a[$0]} és ezért gyorsabb, pedig az az egyetlen lépés költséges, _épp_ annyira mint egy sorbarendezés

tehát uniq nem lehetséges sort nélkül, nem lehet rajta gyorsítani, legalábbis ordóban

Azt azért vedd figyelembe, hogy awk-nál minden memóriában megy míg a sort a háttérben egy temp file-ba dolgozik.

Nem hiszem, hogy a sorba rendezés és a hash tábla felépítése ugyanannyira lenne költséges, mert a hashnál természetéből fakadóan lehet hatékonyabb tárolást (visszakeresésre és elem beszúrásra optimalizált) csinálni, míg a sorba rendezést egy strukturálatlan adathalmazon kell végrehajtani. Innen fakadnak a hash limitációi is. Ajánlom figyelmedbe a hasító függvények működését.

Nálam egy ~20k soros file-on kb 10szeres az awk előnye.

nns@nnspc:/usr/share/doc/chromium-browser$ wc -l copyright
19231 copyright

nns@nnspc:/usr/share/doc/chromium-browser$ time sort -u copyright >/dev/null

real 0m0.412s
user 0m0.380s
sys 0m0.008s
nns@nnspc:/usr/share/doc/chromium-browser$ time awk '{a[$0]}; END {for (i in a) {print i}}' copyright >/dev/null

real 0m0.034s
user 0m0.020s
sys 0m0.008s

most akkor miért gyorsabb? az eltérő implementáció miatt vagy mert elvileg gyorsabb? én az utóbbiról írtam (hisz az előbbiről már volt sz a szál elején) tehát hogy nem igaz hogy azért gyorsabb mert nem kell sorrendben kiírnia

a teszted nem mutatja hogy melyik ok miatt gyorsabb, csak hogy gyorsabb, de nem erről volt szó, hanem ha azonosak lennének a feltételek (awk és sort implementációja) nem számítana hogy sorrendben kell-e kiírnia

a hash lehet gyors mert nem beszúrnia kell hanem keresnie? biztos nem keversz valamit?
ahogy írtam is, igen, tudom hogy vannak a hashnek olyan felhasználásai amikor nem kell beszúrina/keresnie, de ez itt nem járható út, ide olyan adatszerkezet nem jöhet szóba, csak olyan ahol a keresés után már nem számít hogy beszúrunk-e

implementációtól függ:

tc@box:~$ head -c1234567 /dev/urandom | od -An -tx1 -w3 >a
tc@box:~$ time sort a | uniq >/dev/null
real 0m 3.94s
user 0m 2.57s
sys 0m 0.37s
tc@box:~$ time awk '{a[$0]}; END {for(i in a){print i}}' a >/dev/null
real 0m 7.31s
user 0m 6.37s
sys 0m 0.90s

nem pedig azért mert nem kell kiírnia sorrendben

"...sorba rendezés és a hash tábla felépítése ugyanannyira lenne költséges, mert a hashnál természetéből fakadóan lehet hatékonyabb tárolást (visszakeresésre és elem beszúrásra optimalizált) csináln..."

talán ott van félreértés hogy ha már visszakerested, azzal egyúttal meg is találtad, nincs plusz költsége a beszúrásnak, legfeljebb külön listába szúrod be, az meg lényegtelen hogy most amíg visszakeresed azt a hash-t az egy hash vagy sztring-e

a hash ereje abban van hogy szétszórja az adatokat, így eloszlásra lehet hatékonyabb algoritmus mert számíthatunk rá hogy az lesz

ezen kívül még lehetnek olyan hash-szerű képződmények aminél nem kell keresni mert maga a hash legenerálása megadja a helyét, de ez korlátozásokkal lehet csak adott memóriakorlátozásnál, mert a lehetséges adatoknak mind kell egy kis memóriát lefoglalni, vagy a vödrök leszek túl nagyok és azon belül megintcsak keresni kell, vagy a bitmapet kell tömöríteni ami szintén csak spéci esetben lehet hatékony

Ez a baj a varázslatokkal (asszociatív tömb, oop, stb.) hogy eltakarja az eredetileg egyszerűen megérthető funkciókat. Amikor azt hiszed, hogy az asszociatív tömb egy elemét megcímzed a hash-el, amit egy rekordból képeztél, akkor amögött nincs keresés, akkor te éppen az új idők áldozata vagy. Attól, hogy a pl. három elemű tömbödet rendre a 'elsőelem' 'bikkmakk' 'hashvarázslat' indexértékekkel címzed, attól még van emögött keresgélés, míg a hagyományos címzés csak egy egyszerű összeadást kíván meg, ha ismerjük a tömb első elemének a címét, ugyanis |első elem címe|[1] = első elem,|első elem címe|[2] = |első elem címe|[1]+1, stb. Végiggondolva itt az awk csak az egyfelghasználós gépeken nyer és csak azért, mert memória a tömegtárolója. Egy olyan gépen, ahol 70 ember van beloginolva, máris bajban lesz, mert alig kap memóriát vagy időszeletet a nagy memóriaigény miatt, míg a sort továbbra is egyenletes teljesítményt nyújtana. Ha ezt az elméleti tesztet megfejeljük azzal, hogy manapság nem ritkák a milliós rekordszámú állományok, akkor pedig marad a sort.

Végül, szerintem nem is volt értelme az összehasonlításnak, ha végiggondoljuk, mert a két tool célja teljesen más.

nem teljesen értelmetlen, hisz adott esetben, beleértve a billentyűzetleütéseket az awk gyorsabb :)

és legalábbis én nem a toolokat kezdtem összehasonlítani hanem azon lepődtem meg hogy egyeseknek miért olyan egyértelmű hogy ha nem kell sorrendben kiírni akkor nem kell sorbarendezni

"Végiggondolva itt az awk csak az egyfelghasználós gépeken nyer és csak azért, mert memória a tömegtárolója. Egy olyan gépen, ahol 70 ember van beloginolva mert alig kap memóriát vagy időszeletet a nagy memóriaigény miatt, míg a sort továbbra is egyenletes teljesítményt nyújtana. "

A gép, amelyen a kis- és később a nagyfájlos tesztet futtattam, fő feladatként DB2-t (öszvér DB-k) és WebSphere MQ-t/MB-t hajt meg.
A 70 felhasználó párhuzamos kiszolgálása (igaz, nem shellel) az alsó-közepes terhelése. De persze lehetne jobban is szívatni,
mint ahogy diszket is lehet rángatni pl. médiakonvertálással, hogy a sort se érezze sajátjának az olvasófejeket...

"Végül, szerintem nem is volt értelme az összehasonlításnak, ha végiggondoljuk, mert a két tool célja teljesen más"

De, mert aki elolvasta, tanult belőle. Ki azt, hogy spórolhat a saját idejével, ha a dolga éppen megengedi, ki azt, hogy mielőtt összecsap egy egysorost, az a minimum, hogy elolvassa az egysoros potenciális komponenseinek forrását, hogy az esélyegyenlőségügyi ombucmanó ne illethesse kritikával a kiválasztott alternatívát.

"A gép, amelyen a kis- és később a nagyfájlos tesztet futtattam, fő feladatként DB2-t (öszvér DB-k) és WebSphere MQ-t/MB-t hajt meg.
A 70 felhasználó párhuzamos kiszolgálása (igaz, nem shellel) az alsó-közepes terhelése. De persze lehetne jobban is szívatni,
mint ahogy diszket is lehet rángatni pl. médiakonvertálással, hogy a sort se érezze sajátjának az olvasófejeket..."

Ez már kötözködés. :)

Ha a db2 kiszolgál 70 embert, az nem ugyanaz, mintha 70 interaktív session van nyitva. Sőt, egészen más.

"De, mert aki elolvasta, tanult belőle. Ki azt, hogy spórolhat a saját idejével, ha a dolga éppen megengedi, ki azt, hogy mielőtt összecsap egy egysorost, az a minimum, hogy elolvassa az egysoros potenciális komponenseinek forrását, hogy az esélyegyenlőségügyi ombucmanó ne illethesse kritikával a kiválasztott alternatívát."

Ez igaz.

Nincs keresgélés, hanem hasító függvény van és ennek a funkciója egyszerűen megérthető. Ez nem egy új találmány ahogy maga az awk sem. :)

A példádban levő hagyományos tömb címzés az részhalmaza az asszociatív tömböknek, ha a a kulcsok csak int-ek lehetnek a hasító függvény pedig ennyit csinál: érték helye a memóriában = tömb címe + kulcs * kulcs által elfoglalt memória.

Ha a hasító függvény nem lenne jobb mint egy hagyományos keresés akkor nem lenne értelme :)

Eddig elméletről beszéltünk, nézzük akkor a gyakorlatot. Ha megnézed az awk-ot akkor azt találod, hogy nincs benne hagyományos tömb csak asszociatív, de ez nem zavar abban senkit, hogy számokat használjon kulcsnak, mivel ez az eset részhalmaza az általánosított esetnek. Más adat típusokra is lehet hatékony hasító függvényeket írni, bár azok nem lesznek ennyire triviálisak.

Nézzük még 1 kicsit azt az elméletet: http://en.wikipedia.org/wiki/Hash_function Finding Duplicate records fejezet. Hasonló a helyzet de ott épp a duplikátumokat keresi. Nézzük akkor ezt az esetet sort-al és awk-al.

Gyakorlat: 


# wc -l /usr/share/doc/Deployment_Guide-en-US-5.2/index.html                                               71662 /usr/share/doc/Deployment_Guide-en-US-5.2/index.html

# time awk '{a[$0]++} END {for(i in a) {if(a[i] > 1) print i}}' /usr/share/doc/Deployment_Guide-en-US-5.2/index.html > /dev/null

real    0m0.103s
user    0m0.090s
sys     0m0.013s

# time sort /usr/share/doc/Deployment_Guide-en-US-5.2/index.html | uniq -d > /dev/null                     
real    0m2.073s
user    0m2.064s
sys     0m0.019s

bocsi, de most már tényleg szerintem neked kellene utánanézni mi az a hash fv.

szerintem egyszerűen a hahyományos tömbként képzeled el a hash-t, ami néha igaz is, de akkor egy-egy tömbcímen vödör van, amiben tovább kell keresni, ha meg nem, olyan nagy memória kellene hogy az összes lehetőség beleférjen, ez adott esetben nem nagy hanem végtelen

A hash nem hagyományos tömb, de a hagyományos tömb működése leképezhető egy egyszerű hash függvénnyel. Az int értéktartománya nem végtelen és a kulcsot int-ként specifikálatam a példában, így nem kell végtelen memória sem. Azt is állítottam, hogy ugyanazok vonatkoznak erre mint a hagyományos tömbre. Ebben az esetben a bucket csak 1 értéket tartalmaz. (mivel a teljes kulcs tartomány leképezhető)

- az nem hasító fv hanem bitmap (nagyon csúnyán fogalmazva:) )
- a hash fv-nek a szétszórás a lényege, hogy ha a bemenetben volt is csomósodás, az egyenletes halmazokon, véletlenszerű adatokon jól működő algoritmusok ne a legrosszabb formájukat hozzák, épp ezért hasít, nem pedig ahogy írod leképez

az egyenleted szerint egy normális esetben terabájtok sem lennének elegek (az a bitmap, azaz eleve tudjuk az összes lehetséges bemenetet, meg tudjuk mondani ami épp jön az ebben a listában hányadik, és annyiadik bitet átállítjuk egybe; nálad a kulcs helyett gondolom adatméretet akartál írni, ez most gondolom 1 bit)

Ajánlom figyelmedbe a http://en.wikipedia.org/wiki/Hash_function Trivial hash function leírását. Még mindig tartom, hogy az egy hasító függvény a leírt feltételek mellett és egyszerűsége folytán könnyen megérthető. Ennek nem sok köze van a bitmap-hez, az egyenlet utánozza a hagyományos tömbök működését, és ugyanazok a korlátai mint egy hagyományos tömb-nek.

Az egyenletben a kulcs által elfoglalt memória alatt valójában az érték által elfoglalt memóriát gondoltam :) (Ez persze lehet akármi csak fix szélességűnek kell lennie, amit fel lehet oldani ha a tömbben pointerek vannak)

Nézzünk 1 példát:
Asszociatív tömbünk elemei:

0 -> 4
1 -> 5
2 -> 6
3 -> 7

Egy elem mérete 4 byte
A tömb címe #0100

Memória:

#0100 0004
#0104 0005
#0108 0006
#010C 0007

A triviális függvény szerint pl a 2es kulcshoz tartozó elem megtalálható a #0100(tömb címe)+2(kulcs)*4(elem méret) = 0108 helyen vagyis az érték az 6.

1. mi van az ütközéssel?
2a. a szükséges memória mérete akkor ha jól nézem 2^(4*8) * 4 byte = 16GB?
2b. vagy ha nem kell az összes memóriát lefoglalni honnan tudom _előre_ hogy 7-es pointer által hivatkozott sztringnek épp a 4. hash értéket kell adnom és nem az utolsó helyre?

1. Nincs ütközés, mert a kulcsok teljes értéktartománya le van képezve. A válóságban a normál tömbök mérete előre deklarált.

2a. A példában igen, de ez csak 1 triviális példa. Ma már nem elképzelhetetlen ekkora méretű memória, de a valóságban a normál tömböknél a kulcsok (indexek) értéktartománya (a tömb mérete) ennél jóval kisebb.

2b. Ehhez le kell foglalni a memóriát -> lásd állításomat: 1 asszociatív tömb a felvázolt hasító függvénnyel ugyanazt a funkcionalitást látja el mint egy hagyományos tömb. (A hagyományos tömb spec esete az asszociatív tömböknek)

Azt szerettem volna felvázolni, hogy a hagyományos tömb indexelésre lehet úgy tekinteni mint spec hasító függvény. http://en.wikipedia.org/wiki/Hash_function Trivial hash function fejezet (alatta ott a perfect hash rész is).

0; nem tömbről hanem hash-ről volt szó, azt mondod hogy a hash-nek speciális esete a tömb, és a feladatot ezért tömbbel akarod kezelni... kevered a bogárt a rovarral, azt mondod mivel a kocsi része a kerék, úgy megyek munkába hogy magamhoz veszem a kereket.. jó-jó, demihajcsa? hol a motor?

1; a kulcs nyilván nem ütközik (most attól függetlenül hogy tömbről írsz nem hashről), két sztringnek lesz ugyanaz a kulcsa

2a1; kicsi feladathoz vegyek szuperszámítógépet?
2a2; amit írtál az a 4byte elég kicsi kulcstér, ha tovább csökkented a lottószámaim is ütközni fognak, nemhogy egy szövegfájl sorai

2b; lsd 0, egyszerűen nem tudom felfogni mit írsz, még csak nem is a hagyományos tömböt akarjuk kiváltani hash-el, hanem hash fv-el akarunk valamit gyorsítani, erre te leírsz egy tömbös megoldást

2: azért írtam direkt konkrét adatot hogy lásd hol hibádzik, sok memória is kevés (konkrét példa számokkal), erre te azt írod hogy a sokat is meg lehet fizetni de nem kell mert elég kevés is (így a levegőbe), itt meg azt nem értem hogy az elvi síkról a gyakorlatira terelésnél mér t térsz le még az elvi síkról _is_

Szerintem nem ugyanarról beszélünk. Feljebb offtopic módon tomi66 arról írt http://hup.hu/node/100959#comment-1249839, hogy a hash mögött mindig van keresgélés míg a tömb indexálás mögött nincs. Arra próbáltam utalni, hogy a tömb indexálást is fel lehet fogni mint egy egyszerű hasító függvényt.

Ez persze nem magyarázza miért gyorsabb az awk az eredeti problémában. Én úgy gondolom, hogy a valódi hasító függvények a direkt leképezés (a példám) és a leképezés nélküli adatelérés (sort) között helyezkedenek el sebességben.

1. Igen, de nem minden sztring fog ütközni és ha jó a hasító függvény akkor kis elemszámú bucketek lesznek így minimalizálhatja a rendezést/keresést.

2a. Ez nyilvánvaló, hogy súlyos korlátokkal rendelkezik.
2b. Mert elmentem offtopicba tomi66 miatt. Elnézést érte. Jónak láttam a tömb indexelést mint szélsőséges példát a hasító függvényre. Azt lásd be, hogy amit írtam az példa a triviális és perfekt hasító függvényre. A cél egy gyors hasító függvény bemutatása volt.

2. Több konkrét mérési eredményt is írtunk (ahol én publikus text fileokat használtam) és mindenhol az awk lett a gyorsabb nem is kevéssel.

épp onnan indult az egész szál hogy senki nem vitatta hogy gyorsabb az awk, a kérdés az hogy miért?

architekturális oka van vagy mert lehet sorbarendezés műveletigényétől az asszociatív tömbbel gyorsabban kiírni az egyszeres sorokat?

kicsi vödrök? igen, pont ez a lényege a hashnek, de ettől még teljes keresés lesz, először a vödröt kell keresni aztán a vödörben, a hash mondjuk a sztring első karaktere, a további keresés így már 1/256-od halmazon kell, de ez épp ugynolyn keresés; azaz a hash csak azt garantálja hogy nem csupa a-val kezdődő sorok lesznek hanem egyenletesen, (bár ez plusz műveletet ad, a hash leképezést, ami épp annyira nem számít minthogy ezen a módon a végén sorrendben írjuk-e ki vagy nem )

mindegy, ha nem tudsz mutatni konkrét algoritmust hogy kell hash-el megvalósítani, tárgytalan, ha igen akkor nagyon kíváncsi vagyok, és megmutatom hogy minimális plusz művelettel sorrendben is ki lehet írni :)

Aha csak szerintem a vödör kikeresése az sokkal gyorsabb mint egy normál keresés és ez okozza a sebesség különbséget. Sztringeknél valószínű, hogy nem csak az első karaktert használja így nem csak 256 vödörre hasít hanem sokkal többre. Így a teljes sorberendezés kiváltható a hash függvénnyel ahol a hasítás gyors a vödörben elhelyezés meg kb ugyanolyan lassú mint a sorbarendezésnél, kivéve ha a vöddrökben csak 1-1 elem van. Minden nem ütköző hash óriási nyereség időben. (Egy hash számítás sokkal kevésbé költséges (CPU) mint adatokat mozgatni memóriában diszkekről nem is beszélve)

Példa: http://awk.info/?doc/news/mawkHashing.html itt ezt használja: http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function

El szerettem volna kerülni de megnéztem a gawk kódját. (http://ftp.gnu.org/gnu/gawk/) Az array.c-ben ott a awk_hash függvény ami elég szörnyű, de működik :)