Egymillió 32 bites szám sorba rendezése, hogyan?

Offtopic

"2007. november 14-én Barack Obama szenátor, a világ leghatalmasabb országának elnökjelöltje látogatást tett a Google-nél, a világ leghatalmasabb keresőcégénél. A szenátor elmondta, hogyan kellene rendbe tenni az ország ügyeit, majd a cég zajosan ünneplő alkalmazottai előtt beszélgetett egy jót Eric Schmidttel, a cég vezérigazgatójával. A csúcspont az volt, amikor Schmidt megkérdezte tőle, hogyan rendezne sorba egymillió 32 bites számot. Obama szó szerint azt válaszolta, hogy "a buborékrendezés nem működne"..."
forrás: index.hu

Tényleg, hogyan?

  • 6448 megtekintés

amikor még mi tanultuk egyszerűen quicksortnak hívták, nem volt magyar fordítás. azt viszont akkor még rendesen megtanították, hogy van egy heapsort algoritmus is, amely bár picit lassabb a quicksortnál. de speciális esetekben, amikor a quicksort dög lassú, a heapsort nagyságrendekkel gyorsabb. ezért általánosságban jobb algoritmus a heapsort.

nem kellene pont ezen vitázni. első féléves progmat anyag része volt, most már talán gimiben is szó van róla.
valóban el kell ismerni, hogy mostanában sokan a hivatalok képzésen kívül, össze tudnak szedni komoly programozói tudást, főleg az internet segítségével. de azért a hagyományos oktatásnak is megvannak az erényei. a heapsort egy ilyen iskolapélda. szerintem olvass utána.

( mazursky | 2008. 09. 15., h – 11:05 )

1000 db 1000 hosszú sorozatot veszek, és azokon gyorsrendezés, majd az egészet összefésülöm.
Jobb ötlet?

/mazursky 

Love your job but never love your company!
Because you never know when your company stops loving you!

A Google is ma már egy a szupervállalatok közül és nem is különb azoknál. Ez az egész hülyeség csak önreklám volt, amit Obama nagy mellszélességgel támogatott is. Aztán kiderült, az egyetemen ő is tanult algoritmusokat, mégha abból csak a bubirendezésre emlékezik is (nem csoda, hiszen az elég könnyen felfogható).

( meditor | 2008. 09. 15., h – 12:51 )

Kupacrendezés. Helyben rendez, baromi gyors.
> Sol omnibus lucet.

( zamboriz v | 2008. 09. 15., h – 13:00 )

> hogyan rendezne sorba egymillió 32 bites számot

Ha egy szám egyszer szerepel, akkor elfér egy fél gigás bittérképben :-)

Miért ez lenne a leggyorsabb? Ez esetben is ötszáz megát kéne legalább kétszer végignyalni. Ennél egy quicksort vagy heapsort vagy bitenkénti radix is jóval kevesebb memóriaírást és -olvasást végez, arról nem is beszélve hogy jóval koncentráltabb helyen (vö. processzor cache), meg egyébként is mi van ha épp nincs kéznél fél giga hely épp erre a feladatra, és mondjuk nekiáll swapolni a rendszer?

A sebesség nem egy triviális kérdés. Pld nem vagyok biztos abban, hogy egy "tiszta" algoritmus a leggyorsabb (1m 32bites számra). Az is lehet, hogy a "nagyját" quicksort-tal, az "apraját" (mondjuk a 6 elemnél rövidebb blokkokat) meg valami mással érdemes rendezni.

Elegendően nagy elemszámnál egy négyzetes algoritmus gyorsabb lehet mint egy lineáris, de kis elemszámnál ez akár fordítva is lehet.

Úgy emlékszem, hogy a glibc quicksort implementációja a 7 vagy kevesebb elemre valami kézzel-lábbal rendezést használ, mert az a gyorsabb, és csak ennél többre játszik quicksort-féle rekurziót. Vagyis telibe találtál.

Rengeteg apró részleten tud még múlni az algoritmus hatékonysága. Például quicksort esetén a felhasználás módjától függően követelmény lehet, hogy véletlenszerű elemet válasszon ki, ne mondjuk a rendezetlen tömb középső elemét - ily módon rosszindulatú támadó nem tud olyan bemenetet konstruálni, amire n^2-es a futási ideje. Hasonló trükk lehet például nem is egy random számot választani, hanem hármat, és közülük az érték szerinti középsővel dolgozni tovább - ez is csökkenti a rossz választás esélyét.

Véletlen választásnál a rosszindulatú támadó nem, de a véletlen még összehozhatja a legrosszabb esetet.
Ezért írják oda az ilyen algoritmusoknál, hogy átlagos eset ennyi, legrosszabb eset annyi...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

> Ezért írják oda az ilyen algoritmusoknál, hogy átlagos eset ennyi, legrosszabb eset annyi...

Persze, teljesen tiszta sor, csak be akartam hozni egy újabb szempontot. Én úgy látom (lehet hogy rosszul), hogy eleinte volt az "átlagos" és a "legrosszabb" eset, aztán később, a gyakorlati alkalmazások, internet terjedése, támadások, DoS stb. során jött be a képbe az a szempont, hogy nemcsak random inputra, hanem tudatosan rosszindulatú inputra is vizsgálják az átlagos hatékonyságot.

How fast can we sort 5 elements

"... he decided to get more aggressive, writing code to do the sort in seven comparisons.

bubble sort, insertion sort, merge sort and Quicksort all will require ten comparisons in the worst case.
a carefully coded merge sort requires eight comparisons in the worst case.
heapsort requires at least nine comparisons in the worst case.

The generated procedure is 485 lines long"

Hát igen, a gyors kód általában nem rövid.

mert nincs valodi sorbarendezes. van egy 2 ad 32 elemu tombod (T), elemei legyenek bitek hogy keves helyet foglaljon el :) 1x vegigfutsz az 1m szamon (N), mig 1be allitod a tomb megfelelo indexet T[N]=1 - ez 1m bit iras. kesz a sorbarendezes. ha ki akarod olvasni 1x vegigfutsz a tombon - ez 512M bit olvasas optimalizalhato -, ahol 1et talalsz azt kiirod.
c64-en rendezed a tombot? mert ha nem ne okozzon gondot az 512M a tarolasara, nem ez volt a feladat. ha igen, a 4M is sok lesz.

most hogy mondod c64en anno megcsinaltuk ennek a 10e szamos 16 bites valtozatat es a "bitmapsort" sebessege tobbszorose volt az akkor ismert tobbi algoritmusenak, tehat nem a levegobol vettem a sebessegkulonbseget, en mar csinaltam egy tesztet. ha at akarod ultetni egy mai gepre tedd meg. en ma is a "bitmapsort"-ra fogadnek :)

Hmmm... míg a többiek az arról vitatkoznak, hogy lineáris -- n log n -- négyzetes, addig te előhúzod az aduász algoritmust, ami a bitek számában exponenciális, magyarul a 16 bites számok rendezéséről a 32-bites számokra átállva az igényelt memóriaterület (bitekben) és ezáltal a futási idő (utasítások száma) is a négyzetére emelkedett. Minden bizonnyal 5-10 éve, amikor már régesrég mindenki 32-bites egészekkel dolgozott, akkor is azt javasoltad, hogy hoppá, fél gigát bele a gépbe egy ilyen egyszerű feladatért, állod a cekket. Mondd csak, 64-bites architektúrákról hallottál már? :-)

Egy baj van ezzel. C64 prociában szerintem nem volt cache... Méghozzá azért nem, mert nem kellett. Azért nem, mert a memória és a proci sebessége között nem volt 2 nagyságrend...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

> en ma is a "bitmapsort"-ra fogadnek :)

Rosszul tennéd: 


# time ./quicksort
real	0m10.331s
user	0m9.937s
sys	0m0.348s


# time ./bitmapsort
real	0m26.122s
user	0m21.937s
sys	0m2.964s

Kétszer olyan gyors a quicksort. És mi volt a bitmapsort.c? Íme: 


char p[ 512 * 1024 *1024 ]; 
 
int main(void){ 
 
  for( int i=0; i<50; i++ ){ 
    for( int j=0; j<512 * 1024 *1024; j++ ){ 
      p[j] = i; 
    } 
  } 
 
  return 0; 
}

Hoppá, ez nem rendez semmit, mégis laaaasssssúúúúú. :-)

(Persze a quicksort.c -ben is ott volt az 50-es ciklus.)

Tényleg érdekes lenne...

A probléma annak a bizonyos 512Mb-nek a feltöltése.
Fogsz egy számot. Kíszámolod a hozzá tartozó bit címét.
Beolvasod a bitet tartalmazó byte-ot. Mivel a számok nem sorban jönnek, ezért tuti a cache miss. Vársz míg a proci beolvassa a cache-be a neked kellő byte-ot, és a környékét, átbillented a megfelelő bitet (ez is vagy 2-3 művelet), kiírod a byte-ot.
Sajnos még az Out-of-Order végrehajtás sem segít sokat, állandóan cache miss-jeid lesznek, emiatt újabb adatokat kell beolvasni a cache-be, és még azt is meg kell várnod, hogy az előző adatokat kiírja a memóriába...

Ezzel szemben egy jó kis quick-sort szinte a cache-ben rendez...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

> ez 1m bit iras. kesz a sorbarendezes.

És ki fogja a tömböt csupa nullával inicializálni? :)

> c64-en rendezed a tombot? mert ha nem ne okozzon gondot az 512M a tarolasara, nem ez volt a feladat. ha igen, a 4M is sok lesz.

Azt akarod mondani, hogy ha 4M van, akkor 512 is biztos van?

Ennek a feladatnak (mivel az adatmennyiség nagyon picike) tökéletes megoldása a sort használata.

De ilyent nem is kérdeztek a google-nél (legalábbis management pozícióra pályázóktól), inkább olyat, hogy hogyan rendeznéd a föld teljes emberi lakosát életkor szerinti sorba? Alapvetően nem(csak) matematikai a feladat - onnan kezdjünk, hogy ott ülsz a géped előtt és ezt meg akarod oldani, hogyan állsz neki, milyen lépésekre lesz szükséged, milyen problémákra számítasz és hogy akarod megoldani őket?

( uid_4656 v | 2008. 09. 15., h – 14:37 )

Ha nincs más feltétel megadva, akkor pl. ez alapján a táblázat alapján:

http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorith…

lehet választani olyan rendezést, ami O(n*log(n))-ben rendez átlagosan és legrosszabb esetben is, valamint O(1) a memóriaigénye.

Persze lehet bonyolítani a dolgokat, ha finomítjuk a feltételeket. Pl. ha azt mondjuk, hogy van a feladat számára felsőegészrész(log(1.000.000)) * 2^32 bit memóriánk, akkor meg lehet csinálni azt, hogy egy ilyen memóriaterületen tároljuk azt, hogy melyik számból hány darabot találtunk, és akkor elég O(n)-ben egyszer végigmenni a tömbön és a memóriaterület értékeit ennek megfelelően növelgetni.

A dolog akkoris érdekesebb, ha van több processzorod, vagy több számítógéped több processzorral. Ekkor el lehet kezdeni azon gondolkodni, hogy elvileg hogyan darabolható szét jól a feladat. Pl. két feldolgozó egység esetén megteheted, hogy a rendezendő számok egyik felét az egyik egységgel rendezteted, a másik felét a másik egységgel, majd a két rendezett darabot összefűzöd. A fentebb említett algoritmusok között vannak olyanok, amelyek ki tudják használni az ilyen párhuzamosításokból adódó előnyöket, és vannak, amelyek nem. Esetleg érdekes lehet arra is figyelni, hogy az ilyen jellegű párhuzamosítós/terheléselosztós dolgoknak van némi overhead-je is - maga az elosztás is időbe kerül, ami akár rosszabb teljes futásidőt okozhat, mintha egy egységen futna a teljes rendezés.

Aztán igazán izgalmassá azzal tehető a feladat, ha az egymilliót megemeljük mondjuk sokszázezermilliárdra. Ha 32 bites számoknál vagyunk, akkor nem is rendezési feladatról van szó, hanem számlálási feladatról, ahogy fentebb írtam. Ha nagyobb számokról van szó (mondjuk akkorákról, hogy akár lehet közöttük sokszázezermilliárd különböző is), amelyek egyszerre nem férnek bele a a rendezni akaró egységek memóriájába - nos, akkor neki kell állni számolgatni komolyabban, ami már nagyon nem az én asztalom.

( nc | 2008. 09. 15., h – 15:12 )

Kedvet kaptam a rendezési algoritmusokhoz :)

Legenerálom az 1 milka 32 bites számot és írok rá különböző rendezéseket. Dolgozzon más :)

( asch v | 2008. 09. 15., h – 19:08 )

Ha már elmélet... Előre adott véges méretű inputra nincs értelme ordókról beszélni. Létezik olyan gép aminek a feladat pontosan egy művelet.

( Tyra3l | 2008. 09. 15., h – 19:11 )

ORDER BY, csak legyen index a mezon. :)

Tyrael

Így van és ez lefutot 0.00 s -alatt
Kár volt programozni ;-)

Hiába az űskáoszt programozók csinálták...

A htáttérrendszert szerencsére egy jó rendszergazda rendesen beállította és így az elég stabil volt ennek rendezésére.

:-D

----
Nyicc-egy-csört?
Esetleg nézd meg itt: http://kayapo.extra.hu/

( psc | 2008. 09. 15., h – 22:44 )

Tegyük fel a kérdést a prog.hu -n... :)

( tomsolo | 2008. 09. 16., k – 00:18 )

sztem párosak balra páratlanok jobbra a maradékot meg egymás mellé

/me abakuszt tologat

"A very intelligent turtle, found programming UNIX a hurdle
The system, you see ran as slow as did he,And that’s not saying much for the turtle."

( hokuszpk | 2008. 09. 16., k – 01:13 )

termeszetesen a PageRank (c) algoritmussal.

( radix | 2008. 09. 16., k – 02:42 )

Ez nem ér, indexelésnél már eleve sorba volt rendezve, ez a lényege az indexelésnek.
Amikor ráadod az indexet, akkor rendezi sorba.

( bri | 2008. 09. 16., k – 09:32 )

quicksort... a formátum lényegtelen. lehetne string is.

szerk.: és egy gyors gép sok processzorral. ez nem PC-s feladat.

:: by BRI.
:: config :: Acer TravelMate // Intel Celeron 530 1.73GHz. 533MHz FSB, 1MB L2 // 1GB DDR2 // Mobile Intel GMA X3100 // Ubuntu Hardy

Az eredeti feladatban mind a számok maximális mérete (32-bites), mind darabszámuk (egymillió) meg volt adva, nincsen egyetlen szabad paraméter sem, tehát nincs értelme ordóról beszélni. Teljesen konkrét implementációkat lehet összehasonlítani, ismerve az azt futtató processzor időzítési adatait. Ebben az esetben a radix esetén is felmerül az a kérdés, hogy mekkora egységekre robbantod a 32-bites számot (bitekre? byte-okra? egyéb?) és azon belül is egész pontosan hogyan rendezel.

Ha a két paraméterből az egymilliót szabadon engeded és n lesz belőle, akkor a radix remek ötlet. Ha viszont épp a másik paramétert engeded szabadon (rendezz sorba egymillió darab akármekkora számot), akkor épphogy nagyon nem nyerő a radix.

A RADIX-et tényleg akkor érdemes használni, ha a helyiértékek száma lényegesen kisebb a rendezendő elemek számánál (k kisebbkisebb n). Viszont szerintem logikus egy ilyen feladatnál azt feltételezni, hogy a helyiértékek száma legfeljebb egy paraméter, ami megszokott határok közt mozog (8-128), míg a darabszám az, ami tipikusan változó, és tipikusan a végtelenhez tart.

--
The Net is indeed vast and infinite...
http://gablog.eu

Megjegyezheted ahányszor akarod, attól még nem lesz igazad. :)

Összehasonlító algoritmusok műveletigénye minimum O(n logn). Ennél jobbat ne is keressen senki, bizonyítottan nincs.

Nézzünk nem összehasonlító algoritmust:
RADIX műveletigénye nem O(n), hanem O(n*k), ahol n a darabszám, a k pedig a helyiértékek száma.
Bináris esetben minimum hány helyiérték kell n darab szám ábrázolásához?
Természetesen logn.
Azaz ebben az esetben a RADIX műveletigénye O(n logn). Hoppááá....

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Kezdjük azzal, hogy a RADIX nem összehasonlításon alapuló rendezés. (Az említett bizonyítást én is nagyon jól ismerem.)
Pont ezért lehet vele O(n logn) alá menni, és pont ezért hoztam fel újra.

Az érvelésedben pedig van egy nagy hiba: a helyiértékek száma 32-bites számoknál nem logn, hanem 32.
A legjobb ismereteim szerint pedig O(32*n) == O(n) .

A RADIX továbbra is O(n)! Hoppááá.... xD

--
The Net is indeed vast and infinite...
http://gablog.eu

az ervelesben nem volt hiba, legfeljebb te nem erted - annyi volt, hogy az n-nel a szamok darabjat jelolte tr3w, nem a meretet (=32 bites).

a radix akkor lehet gyorsabb mint a kupacrendezes (vagy akarmelyik hasonlo), ha nagyon sok szam van, de kicsik, tehat sok az azonos (ezt is irtak mar itt feljebb). ekkor tenyleg kisebb lesz a muveletigenye (nem az ordo-rol beszelek) mint n*logn. viszont az 1 millio 32 bites szam pont nem ilyen (log n = log 1000000 < 32).

- Use the Source Luke ! -

Hoppááá.... ^_^

Az én érvelésemmel meg az a baj, hogy bár egymillió számról volt szó, azt folyamatosan csak egy példának veszem, úgy, hogy egyébként tart a végtelenbe.

Trükkös dolog ez az aszimptotikus konvergencia. Csak azt akartam kihangsúlyozni, hogy vannak nem összehasonlításon alapuló rendezések, és azokra nem igaz az O(nlogn) korlát.

--
The Net is indeed vast and infinite...
http://gablog.eu

Nem is mondtam, hogy a az alsó korlát a radixra vonatkozik.
Csak megjegyeztem, hogy ismert ilyen alsó korlát...

Illetve azt jegyeztem meg, hogy ha feltesszük, hogy a rendezni kívánt n db szám közül elenyésző az ami többször szerepel, akkor logn helyiérték kell.

Mivel most tudjuk, hogy 32 helyiérték van, ezért mindaddig gyorsabb lesz egy jó összehasonlító algoritmus mint a radix, amíg logn < 32.
Ami 1000000 számnál bőven teljesül.

És akkor még nem is beszéltünk arról, hogy pl pc-n a processzor-cache-memória felépítés miatt mennyivel jobb egy quickshort, mint egy radix...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

"Az érvelésedben pedig van egy nagy hiba: a helyiértékek száma 32-bites számoknál nem logn, hanem 32.
A legjobb ismereteim szerint pedig O(32*n) == O(n) ."

Tipikus példája az Ordo jelölés értelmetlen használatának.

Mert akkor én azt mondom, hogy n az elemszám, ami feltehető, hogy a mai informatikai háttér mellett kisebb, mint N=2^(2^99999999999999), ami egy konstans.

A buborékrendezés N számra <=N^2 összahasonlítást/cserét jelent.
Ha csak n számom van, akkor is <=n^2 < N^2 kell.
Azaz tehát a buborékrendezés O(N^2)==O(1).

Ez nyilvánvaló baromság...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Ez nem értelmetlen, az ordo per definition ilyen. Csak akkor van értelmet használni, mert már a definició is értelmetlen ha diszkrét paraméterhalmazon dolgozunk, ha az n paraméter a végtelenhez tart, és kis n-ekre nem nézzük. Pedig gyakran van, hogy a legnagyobb elérhető n-ünk is olyan kicsi, hogy egy nagyobb nagyságrendben lévő fv is kisebb eredményt ad.

--
The Net is indeed vast and infinite...
http://gablog.eu

Szerintem már érted, csak nem akarod beismerni. :)

A radix futásideje O(k*n). Te gondoltál egyet, és rögzítetted a k, merthogy "azt tudjuk", kijött neked az O(n), és lobogtatod, hogy az jobb, mint az O(n*logn).

Akkor én azt mondom, hogy az n=1000000, ezt tudjuk, tehát a radix O(k), míg a buborék O(1), tehát a buborék jobb.

Ebből is látszik, hogy ha önkényesen lerögzítesz paramétereket, akkor értelmetlenné válik az egész.

Én nem ezt tettem, hanem vettem a k-ra egy elég jó n alapú becslést, és így már összehasonlítható a kettő.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

O(n logn - 0.9n) == O(n logn)

http://en.wikipedia.org/wiki/Comparison_sort#Lower_bound_for_the_averag…

Máig nem találtak algoritmust ami bármilyen n-re log(n!) időn belül végez, de ez is O(n logn), és ez alá menni nem lehetséges összehasonlításon alapuló rendezéssel.

--
The Net is indeed vast and infinite...
http://gablog.eu

akkor tegyük fel, hogy egy tetszőleges összehasonlító-cserélgető rendező algoritmusba bevezetünk egy új változót, ami a pass-onkénti cseréket számlálja. amennyiben ez valamelyik pass végére 0 marad, azaz nem volt már csere, onnantól rendezett az adathalmaz és nem kell már folytatni az algoritmust sem.
extrém esetben, ha pl. egy rendezett adathalmazra küldjük rá a fentivel kiegészített algoritmust, akkor az első pass után ki is lép, azaz O=n
az O(nlogn) inkább a helyesen megírt algoritmus esetén a maximálisan szükséges műveletek száma szerintem.
de én rohadtul nem vagyok matematikus :)

Most azt bizonyítottad be, hogy létezik olyan rendezési algoritmus, amihez létezik olyan bemenet, hogy n-1 összehasonlítást követően terminál. (n szám végignézéséhez nem n, hanem n-1 összehasonlítás kell)

Az említett O(n logn) korlát pedig azt jelenti, hogy nem létezik olyan összehasonlításon alapuló rendezési algoritmus, amelyik _bármilyen_ bemenetet nagyságrendben n*logn összehasonlításnál kevesebbel rendezne. A tényleges alsó korlát pedig felsőegészrész(log(n!)), ami ugyanez a nagyságrend.

Rendezési algoritmusoknál - sőt, általában algoritmusoknál - nem az szokta érdekelni az embereket, hogy egy partikuláris vagy legjobb esetben mit produkál, hanem hogy _minden_ esetben jól működjön, és átlagos ill. legrosszabb esetben milyen igényei vannak.

--
The Net is indeed vast and infinite...
http://gablog.eu

ez igaz, csak a fogalmazásod, miszerint:
Máig nem találtak algoritmust ami bármilyen n-re log(n!) időn belül végez, de ez is O(n logn), és ez alá menni nem lehetséges összehasonlításon alapuló rendezéssel.
ahol értelmezésem szerint n az elemszámot jelenti és _nem_ az adathalmaz minőségét/rendezettségét, és ebben az esetben (tehát ha n a darabszám) a mondatod második fele nem igaz.
persze ez csak fogalmazási kérdés nyilván, elméletben nyilván igazad van.

Félrebeszélsz. Algoritmusokat az elemszám függvényében szoktunk elemezni, átlagos és legrosszabb esetre nézve. A használt O() jelölés pontosan az utóbbit fejezi ki.

Amit te csinálsz, az az, hogy a legjobb, ill. egy kiemelt esetre nézve elemezed, aminek nem sok értelme van. Lehet persze így is vizsgálni egy programot, de az algoritmus megértésén/tanításán kívül nem nagyon látják hasznát.

Ha nagyságrendekről és algoritmusok elemzéséről van szó, akkor légyszíves vagy a meglévő elméleti kereteken belül maradjunk, vagy nyugodtan vezesd be a saját metrikáidat, de anélkül hiányzik a keret, a kontextus, amiben beszélni lehet bármiről is.

Továbbra sem látom értelmét azon vitázni, hogy milyen rendezési algoritmusokat ismerünk rendezett sorozatok rendezésére...
Vagy azzal nem értesz egyet (?), hogy az O(nlogn) - per definition - mit jelent?

--
The Net is indeed vast and infinite...
http://gablog.eu

( mrev | 2008. 10. 03., p – 10:15 )

Példa qsort alkalmazásra. A feladat leindexelni egy 30 millió soros táblát, azaz felépíteni egy ekkora btree-t. Azért nehéz, mert a kulcsok véletlen sorrendű hozzáadása miatt az épülő btree-t állandóan rendezgetni kell (page split). Ennek az eredménye kivárhatatlan, a harver előbb szétesne, mint ahogy a művelet befejeződik. Megoldás: A kulcsokat előzőleg rendezni kell. Kiírjuk a kulcsokat egy fájlba, azt fájlmappinggel bemapoljuk, arra meghívjuk az egyszerű könyvtári qsortot, pár perc alatt kész.
--
CCC3

( luisex v | 2008. 10. 03., p – 10:39 )

Lehet, csak bennem merült fel a kérdés, de mit takar a 32 bites szám? Lebegőpontosan, vagy fix pontosan ábrázolt számot?
Ha jól tudom, az FPU a mai napig nagyságrendekkel lassabban számol, és hasonlít össze, mint az ALU.
Így, ha lebegőpontos, célszerű kissé felbontani a számot, és először a mantissza szerint rendezni, majd azon belül karakterisztika szerint. Természetesen mindezt olyan formában, hogy az ALU dolgozzon, ne az FPU...
Persze lehet, tévedek, akkor kérlek javítsatok ki...

( enpassant v | 2008. 10. 06., h – 09:01 )

Általában egy nagyon jó általános rendezés, ha előzetesen QuickSort-tal "kvázi" rendezzük pl. 10 elem mélységig, tehát a QuickSort rekurzióját nem engedjük le 1-ig, hanem pl. 10-nél megállunk. Majd az így előállt "kvázi" rendezett halmazt egy egyszerű beszúró rendezéssel lerendezzük.

( horvatha | 2008. 10. 06., h – 09:13 )

Biztos vannak erre tesztek. Nem tud valaki URL-t különféle rendezések benchmark-járól azonos környezetben? Biztos csinált ilyet valaki.

(Mivel a qsort glibc-ben benne van, gyorsan tudnék erre progit írni, de nincs időm bubblesort-ot programozni, dolgozni kell.)