Kokonaislukulajittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. tammikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Kokonaislukulajittelu  on tehtävä lajitella joitakin arvoja kokonaislukuavainten avulla. Kokonaislukulajittelualgoritmeja voidaan käyttää myös ongelmiin, joissa avaimet ovat liukulukuja tai tekstijonoja [ 1] . Kyky suorittaa kokonaislukuaritmeettisia operaatioita avaimille mahdollistaa sen, että kokonaislukulajittelualgoritmit ovat monissa tapauksissa nopeampia kuin vastaavat vertailuja käyttävät lajittelualgoritmit riippuen laskentamallissa sallituista operaatioista ja avainnumeroiden koosta.

Tavalliset kokonaislukulajittelualgoritmit: korilajittelu , kantalukulajittelu , laskentalajittelu ovat laajalti käytettyjä ja tehokkaita [2] [3] . Kokonaislukulajittelualgoritmien lisätutkimukset ovat keskittyneet pahimman tapauksen teoreettisiin parannuksiin, ja saatuja algoritmeja ei pidetä tehokkaina nykyaikaisissa 64-bittisissä tietokoneissa, vaikka kokeet ovat osoittaneet, että jotkin näistä menetelmistä voivat olla parempia kuin bittikohtainen tietojen lajittelu. 128 tai enemmän bittiä avaimessa [4] . Myös suurille tietojoukoille kokonaislukulajittelualgoritmien lähes satunnaismuistin käyttöluonne on rajoitus, etenkin verrattuna muihin lajittelualgoritmeihin, jotka on suunniteltu hierarkkista muistirakennetta ajatellen .

Kokonaislukulajittelua käytetään yhdessä kuudesta vertailuarvosta DARPA High Productivity Computing Systems Discrete Mathematics -sarjassa ja yhdessä yhdestätoista kriteeristä NAS Parallel Benchmarks -sarjassa [5] .

Laskentamallit

Kokonaislukulajittelualgoritmien aikarajoitukset riippuvat yleensä kolmesta parametrista:  - lajitettavien tietoarvojen määrästä,  - suurimman mahdollisen avaimen suuruusjärjestyksessä ja - tietokoneen konesanan  bittien määrästä joka algoritmi suoritetaan. Yleisesti oletetaan , että , eli konesanat ovat riittävän suuria edustamaan sekä syöttösekvenssin indeksiä että avainta [6] .

Kokonaislukulajittelualgoritmit on yleensä suunniteltu toimimaan joko osoitinkoneessatai koneelle, jossa on satunnainen pääsy muistiin . Suurin ero näiden mallien välillä on, että hajasaantikoneet mahdollistavat mielivaltaisen arvon käyttämisen rekisterissä muistiosoitteena luku- ja kirjoitusoperaatioissa, joissa on aikayksikköarvo, ja järjestää monimutkaisia ​​tiedonkäsittelyjä hakutaulukon avulla . Osoitinkonemalli mahdollistaa pääsyn muistiin vain osoittimien kautta, joita ei voi manipuloida aritmeettisilla operaatioilla. Molemmissa malleissa bittikohtaiset toiminnot voidaan suorittaa pääsääntöisesti yhdessä aikalohkossa . Erilaiset kokonaislukulajittelualgoritmit tekevät erilaisia ​​oletuksia siitä, voidaanko kokonaislukujen kertolasku suorittaa yhdessä aikaviipaleessa [6] [7] . Erikoisemmat laskentamallit, kuten satunnaispääsy-rinnakkaiskoneet [8] [9] [10] [11] [12] , voidaan myös harkita .

Vuonna 1999 osoitettiin, että joissakin tapauksissa joidenkin kokonaislukujen lajittelualgoritmien vaatima kertolasku tai taulukkohaku voidaan korvata erikoistoiminnoilla, jotka voidaan helposti toteuttaa laitteistossa, mutta joita ei yleensä ole saatavilla yleiskäyttöisissä tietokoneissa [7] .

Muistiinpanot

  1. ↑ Han, Thorup, 2002 .
  2. ↑ McIlroy, Bostic, McIlroy, 1993 .
  3. ↑ Andersson, Nilsson, 1998 .
  4. ↑ Rahman, Raman, 1998 .
  5. ↑ DARPA HPCS Discrete Mathematics Benchmarks Arkistoitu 10. maaliskuuta 2016 Wayback Machinessa , Duncan A. Buell, University of South Carolina, haettu 20.4.2011.
  6. ↑ 1 2 Fredman, Willard, 1993 .
  7. ↑ 1 2 Andersson, Miltersen, Thorup, 1999 .
  8. ↑ Reif, 1985 .
  9. ↑ Cole, Vishkin, 1986 , Kommentti.
  10. ↑ Hagerup, 1987 .
  11. ↑ Bhatt et ai., 1991 .
  12. ↑ Albers, Hagerup, 1997 .

Kirjallisuus