Egész számok rendezése

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. január 22-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Az egész számok rendezése bizonyos értékkészletek rendezésének  feladata egész kulcsok segítségével. Az egész szám szerinti rendezési algoritmusok olyan problémák esetén is használhatók, ahol a kulcsok lebegőpontos számok vagy szöveges karakterláncok [1] . A kulcsokon való egész számok számtani műveleteinek végrehajtása lehetővé teszi, hogy az egész számok rendezési algoritmusai sok esetben gyorsabbak legyenek, mint az összehasonlítást alkalmazó hasonló rendezési algoritmusok, a számítási modellben megengedett műveletektől és a kulcsszámok méretétől függően.

A szokásos egész szám rendezési algoritmusok: kosár rendezés , radix rendezés , számláló rendezés széles körben használtak és hatékonyak [2] [3] . Az egészszámú rendezési algoritmusokkal kapcsolatos további kutatások a legrosszabb eset elméleti fejlesztéseire összpontosítottak, és a kapott algoritmusok nem tekinthetők hatékonynak a modern 64 bites számítógépeken, bár a kísérletek kimutatták, hogy ezen módszerek némelyike ​​jobb lehet, mint az adatok bitenkénti rendezése. 128 vagy több bittel a [4] kulcson . Ezenkívül nagy adathalmazok esetén az egész számok rendezési algoritmusainak csaknem véletlenszerű memória-hozzáférési jellege korlátot jelent, különösen, ha összehasonlítjuk más rendezési algoritmusokkal, amelyeket a hierarchikus memóriastruktúra figyelembevételével terveztek .

Az egész számok szerinti rendezést a DARPA High Productivity Computing Systems Discrete Mathematics programcsomag hat benchmarkjának egyikében, valamint a NAS Parallel Benchmarks programcsomag tizenegy kritériumának egyikében [5] használják .

Számítási modellek

Az egész szám rendezési algoritmusok időkorlátja általában három paramétertől függ:  - a rendezendő adatértékek számától,  - a lehető legnagyobb kulcs nagyságrendjétől és - a számítógép gépi szavának  bitjeinek számától. hogy az algoritmus végrehajtásra kerüljön. Általában azt feltételezik, hogy , vagyis a gépszavak elég nagyok ahhoz, hogy a beviteli sorozat indexét és a kulcsot is reprezentálják [6] .

Az egész számok rendezési algoritmusait általában úgy tervezték, hogy akár a mutatógépen is működjenek, vagy a memóriához véletlenszerű hozzáféréssel rendelkező géphez . A fő különbség e modellek között az, hogy a véletlen hozzáférésű gépek lehetővé teszik egy regiszterben tetszőleges érték használatát memóriacímként egységnyi időértékkel rendelkező olvasási és írási műveletekben, valamint összetett adatkezelések szervezését keresőtábla segítségével . A mutatógép-modell csak mutatókon keresztül teszi lehetővé a memóriához való hozzáférést, amelyek nem manipulálhatók aritmetikai műveletekkel. Mindkét modellben a bitenkénti műveletek általában egy időszeletben hajthatók végre . A különböző egészszám-rendezési algoritmusok eltérő feltételezéseket tesznek arról, hogy egy időszeletben elvégezhető-e az egész szám szorzása [6] [7] . Speciálisabb számítási modellek, például véletlen hozzáférésű párhuzamos gépek [8] [9] [10] [11] [12] is szóba jöhetnek .

1999-ben kimutatták, hogy bizonyos esetekben az egyes egész számok rendezési algoritmusaihoz szükséges szorzás vagy táblázatkeresés helyettesíthető speciális műveletekkel, amelyek könnyen megvalósíthatók hardverben, de általános célú számítógépeken általában nem érhetők el [7] .

Jegyzetek

  1. ↑ Han, Thorup, 2002 .
  2. ↑ McIlroy, Bostic, McIlroy, 1993 .
  3. ↑ Andersson, Nilsson, 1998 .
  4. ↑ Rahman, Raman, 1998 .
  5. ↑ A DARPA HPCS Discrete Mathematics Benchmarks archiválva : 2016. március 10., a Wayback Machine , Duncan A. Buell, University of South Carolina, letöltve: 2011.04.20.
  6. ↑ 1 2 Fredman, Willard, 1993 .
  7. ↑ 1 2 Andersson, Miltersen, Thorup, 1999 .
  8. ↑ Reif, 1985 .
  9. ↑ Cole, Vishkin, 1986 , Megjegyzés.
  10. ↑ Hagerup, 1987 .
  11. ↑ Bhatt et al., 1991 .
  12. ↑ Albers, Hagerup, 1997 .

Irodalom