Heltalssortering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. januar 2021; checks kræver 2 redigeringer .

Heltalssortering  er opgaven med at sortere et sæt værdier ved hjælp af heltalsnøgler . Heltalssorteringsalgoritmer kan også bruges til problemer, hvor nøglerne er flydende kommatal eller tekststrenge [1] . Evnen til at udføre heltals aritmetiske operationer på nøgler tillader heltalssorteringsalgoritmer at være hurtigere i mange tilfælde end lignende sorteringsalgoritmer ved hjælp af sammenligninger, afhængigt af de operationer, der er tilladt i beregningsmodellen og størrelsen af ​​nøgletallene.

De sædvanlige heltalssorteringsalgoritmer: kurvsortering , radixsortering , tællesortering er meget udbredte og effektive [2] [3] . Yderligere forskning i heltalssorteringsalgoritmer har fokuseret på worst-case teoretiske forbedringer, og de opnåede algoritmer anses ikke for at være effektive på moderne 64-bit computere, selvom eksperimenter har vist, at nogle af disse metoder kan være bedre end bitvis sortering af data med 128 eller flere bits på tasten [4] . Også for store datasæt er den næsten tilfældige hukommelsesadgang karakter af heltalssorteringsalgoritmer en begrænsning, især sammenlignet med andre sorteringsalgoritmer, der er designet med en hierarkisk hukommelsesstruktur i tankerne .

Heltalssortering bruges i et af de seks benchmarks i DARPA High Productivity Computing Systems Discrete Mathematics-pakken og i et af de elleve kriterier i NAS Parallel Benchmarks-pakken [5] .

Beregningsmodeller

Tidsbegrænsningerne for heltalssorteringsalgoritmer afhænger normalt af tre parametre:  - antallet af dataværdier, der skal sorteres,  - størrelsesordenen af ​​den størst mulige nøgle, og  - antallet af bits i computerens maskinord på hvilken algoritmen vil blive udført. Det antages generelt, at , dvs. maskinordene er store nok til at repræsentere både indekset i inputsekvensen og tasten [6] .

Heltalssorteringsalgoritmer er generelt designet til at fungere enten for markørmaskineneller for en maskine med tilfældig adgang til hukommelsen . Den største forskel mellem disse modeller er, at maskiner med tilfældig adgang giver dig mulighed for at bruge en vilkårlig værdi i et register som en hukommelsesadresse i læse- og skriveoperationer med en tidsenhedsværdi og organisere komplekse datamanipulationer ved hjælp af en opslagstabel . Pegemaskinemodellen giver kun adgang til hukommelsen gennem pegepinde, som ikke kan manipuleres ved aritmetiske operationer. I begge modeller kan bitvise operationer som regel udføres på én gang . Forskellige heltalssorteringsalgoritmer gør forskellige antagelser om, hvorvidt heltalsmultiplikation kan udføres i en tidsudsnit [6] [7] . Mere specialiserede beregningsmodeller, såsom parallelle maskiner med tilfældig adgang [8] [9] [10] [11] [12] , kan også overvejes .

Det blev vist i 1999, at i nogle tilfælde kan den multiplikation eller tabelopslag, der kræves for nogle heltalssorteringsalgoritmer, erstattes af specialiserede operationer, der let kan implementeres i hardware, men som normalt ikke er tilgængelige på computere til generelle formål [7] .

Noter

  1. ↑ Han, Thorup, 2002 .
  2. ↑ McIlroy, Bostic, McIlroy, 1993 .
  3. ↑ Andersson, Nilsson, 1998 .
  4. ↑ Rahman, Raman, 1998 .
  5. ↑ DARPA HPCS Discrete Mathematics Benchmarks Arkiveret 10. marts 2016 på Wayback Machine , Duncan A. Buell, University of South Carolina, hentet 2011-04-20.
  6. ↑ 1 2 Fredman, Willard, 1993 .
  7. ↑ 1 2 Andersson, Miltersen, Thorup, 1999 .
  8. ↑ Reif, 1985 .
  9. ↑ Cole, Vishkin, 1986 , Kommentar.
  10. ↑ Hagerup, 1987 .
  11. ↑ Bhatt et al., 1991 .
  12. ↑ Albers, Hagerup, 1997 .

Litteratur