Проксмап сортирање

Из Википедије, слободне енциклопедије
Проксмап сортирање
Insertion sorting into buckets during proxmap.

Пример сортирања уметањем листе случајних бројева.
Класа Алгоритам сортирања
Структура података Низ
Најгора перформанца O(n^2)
Најбоља перформанца O(n)
Најгора просторна комплексност O(n)
Елементи су распоређени међу кофама
Насупрот bucket sort-ирању које се врши након што су кофе напуњене, елементу су сортирани уметањем како су убацивани

Проксмапсорт или Проксмап сортирање је врста алгоритма сортирања, који ради тако што подели низ података, или кључева, на мањи број поднизова. Име је скраћеница од рачунања "proximity map"-е, која одређује, за сваки кључ К, почетак подниза у коме ће се К налазити у коначном поретку. Кључеви су постављени у сваки подниз коришћењем сортирања уметањем. Уколико су кључеви добро распоређени кроз поднизове, временска сложеност сортирања је линеарна, што је много брже од Comparison sort сортирања, које не може бити боље од О(nlogn). Процене теорије комплексности укључују број поднизова и proximity mapping функцију. То је облик Bucket sort-а и Radix sort-а. Алгоритам не постаје много комплекснији како количина података расте.

Када је проксмап сортирање завршено ProxmapSearch може бити коришћено за проналазак кључева у сортираном низу за временску сложеност О(1), уколико су кључеви добро распоређени током сортирања.

Историја[уреди]

Преглед[уреди]

Основна стратегија[уреди]

Основа: За низ А са n кључева:

  • мапира кључ у поднизу крањег низа А2 применом map key функција за сваки елемент низа
  • одређује колико кључева ће бити мапирано на исти подниз користећи низ "броја погодака," H
  • одређује где почиње сваки подниз у крајњем низу, тако да је свака "кофа" одговарајуће величине за све кључеве који ће бити мапирани, користећи низ "проксмапа" P
  • за сваки кључ, рачуна подниз на који ће бити мапиран, користећи низ "локација" L
  • за сваки кључ, проналази локацију и смешта га у ћелију А2; ако настаје колизија са кључем који је већ ту, сотрира се уметањем, померањем већих кључева за једно место у десно, како би се обезбедио простор за овај кључ. Пошто су поднизови довољно велики да складиште све кључеве који су мапирани на њих, неће доћи до прекорачења у наредни подниз.

Једноставније: За низ А са n кључева:

  1. Иницијализуј: Направи и иницијализуј два низа дужине n: hitCount, proxMap и 2 низа дужине A.length: локацију и A2.
  2. Дељење: користећи пажљиво одабрану mapKey функцију, подели A2 на поднизове, користећи кључеве из A.
  3. Распореди: прођи кроз A, убаци сваки кључ у одговарајућу кофу у A2; сортирање уметањем по потреби.
  4. Прикупљање: прођи кроз поднизове редом и постави све елементе у оригинални низ, или простије, користи A2.

Напомена: кључеви могу садржати и друге податке, на пример, инстанца низа објекта Студент садржи кључ, али и индекс студента и име. ProxMapSort је погодан за организацију група објеката, а не само кључева.

Пример[уреди]

Узмимо пун низ: A[0 до n-1] са n кључева. Нека је i индекс низа A. Сортирај кључеве A' у низ A2 исте величине. Маp key функција је дефинисана као mapKey(key) = floor(K).

Array table
A1 6.7 5.9 8.4 1.2 7.3 3.7 11.5 1.1 4.8 0.4 10.5 6.1 1.8
H 1 3 0 1 1 1 2 1 1 0 1 1
P 0 1 -9 4 5 6 7 9 10 -9 11 12
L 7 6 10 1 9 4 12 1 5 0 11 7 1
A2 0.4 1.1 1.2 1.8 3.7 4.8 5.9 6.1 6.7 7.3 8.4 10.5 11.5

A demonstration of ProxMapSort, a bucket sort variant that uses intermediate parallel arrays to efficiently index and size its sublists.

Псеудокод[уреди]

// compute hit counts
for i = 0 to 11 // where 11 is n
{
    H[i] = 0;
}
for i = 0 to 12 // where 12 is A.length
{
    pos = MapKey(A[i]);
    H[pos] = H[pos] + 1;
}
 
runningTotal = 0; // compute prox map – location of start of each subarray
for i = 0 to 11
    if H[i] = 0
        P[i] = -9;
    else
        P[i] = runningTotal;
        runningTotal = runningTotal + H[i];
 
for i = 0 to 12 // compute location – subarray – in A2 into which each item in A is to be placed
    L[i] = P[MapKey(A[i])];
 
for I = 0 to 12; // sort items
    A2[I] = <empty>;
for i = 0 to 12 // insert each item into subarray beginning at start, preserving order
{
    start = L[i]; // subarray for this item begins at this location
    insertion made = false;
    for j = start to (<the end of A2 is found, and insertion not made>)
    {
        if A2[j] == <empty> // if subarray empty, just put item in first position of subarray
            A2[j] = A[i];
            insertion made = true;
        else if A[i] < A2[j] // key belongs at A2[j]
            int end = j + 1; // find end of used part of subarray – where first <empty> is
            while (A2[end] != <empty>)
                end++;
            for k = end -1 to j // move larger keys to the right 1 cell
                A2[k+1] = A2[k];
                A2[j] = A[i];
            insertion made = true; // add in new key
    }
}

Овде, A је низ који се сортира, а mapKey функција одређује број поднизова који се користе. На пример, floor(K) ће просто доделити онолико поднизова колико има целих бројева у A. Дељење кључа константом смањује број поднизова; Различите функције се могу користити да преведу домен елемената A у поднизове, као што су замена слова A–Z са 0–25 или враћање првог елемента (0–255) за дати стринг. Поднизови се сортирају како подаци пристижу, а не када су сви подаци смештени у подниз, као што је случај у типичном Bucket sort-у.

Proxmap Претрага[уреди]

ProxmapSearch користи proxMap низ, генерисан претходно проксмап сортирањем, како би се пронашли кључеви у сортираном низу A2 у константном времену.

Основна стратегија[уреди]

  • Сортирај кључеве користећи ProxmapSort, чувајући MapKey функцију и P и A2 низове.
  • За претрагу кључа, иди до P[MapKey(k)], почетка подниза који садржи кључ, ако се тај кључ налази у подацима.
  • Секвенцијално претражи подниз; уколико је кључ пронађен, врати га; уколико се пронађе вредност већа од кључа, кључ није у подацима.
  • Рачунање P[MapKey(k)] је O(1) временске сложености. Уколико је током сортирања коришћена мапа која даје добар распоред кључева, сваки подниз је ограничен одозого константом c, тако да је највише c поређења потребно да се кључ пронађе, или да се сазна да ли је присутан; стога ProxmapSearch је O(1) временске сложености. Ако се користи најгора мапа, сви кључеви су у једном подстрингу и најгора временска сложеност је O(n) поређења.

Псеудокод[уреди]

function mapKey(key)

  return floor(key)
  proxMap ← previously generated proxmap array of size n
  A2 ← previously sorted array of size n
function proxmap-search(key)
  for i = proxMap[mapKey(key)] to length(array)-1
    if (sortedArray[i].key == key)
      return sortedArray[i]

Анализа[уреди]

Перформансе[уреди]

Временска сложеност рачунања H, P и L је O(n). Сваки се рачуна током једног проласка кроз низ, уз константно проведено време у свакој локацији низа.

  • Најгори случај: MapKey складишти све елементе у један подниз, што доводи до стандардног сортирања уметањем , временске сложености O(n^2).
  • Најбољи случај: MapKey складишти мали број елемената у сваки подниз у редоследу где долази до најбољег случаја сортирања уметањем. Свако сортирање уметањем је сложености O(c), c је величина подниза; постоји p поднизова, стога p * c = n, тако да фаза уметања сложености O(n); стога сложеност ProxmapSort-а је O(n).
  • Просечан случај: Највећа величина сваког подниза је c, константа; уметање за сваки подстринг је онда у најгорем случају O(c^2) сложености, такође константа. (Стварно време заправо може бити много боље, пошто c елемената није сортирано док се последњи елемент не дода у кофу). Укупно време представља број кофа, (n/c), сложености O(c^2)=O(n).

Коришћење добре MapKey функције је важно за избегавање најгорег случаја. Морамо знати нешто о распореду података да бисмо дошли до доброг кључа.

Оптимизације[уреди]

  1. Штедња времена: Сачувати MapKey(i) вредности, како се не би поново рачунале (као што су у коду изнад).
  2. Штедња простора: proxMaps могу бити чуване у hitCount низу, пошто он није више потребан када је проксмапа одређена; подаци могу бити сортирани у А, уместо коришћења А2, ако неко пожели да наведе које су вредности А до сада сортиране.

Поређење са другим алгоритмима[уреди]

Пошто проксмап сортирање није само алгоритам сортирања, доња граница Ω(n log n) није примењива. Брзина се може објаснити тиме што у основи није заснован на поређењу и што користи низове, уместо динамички алоцираних објеката и показивача који се морају пратити, као што је случај код бинарног стабла претраге.

ProxmapSort омогућава употребу ProxmapSearch-а. Упркос сложености O(n), ProxMapSearch то надокнађује O(1) просечним временом приступа, што га чини привлачним за велике базе података. Уколико подаци не морају бити често ажурирани, време приступа може учинити ову функцију привлачнијом од осталих сортирања која нису заснована на поређењу.

Генерички bucket sort у вези са ProxmapSort-ом[уреди]

Као ProxmapSort, bucket sort уобичајено рукује листом од n нумеричких улаза, у границама од 0 до неког максималног кључа или вредности M и дели домен вредности у n кофа величине M/n. Уколико је свака кофа сортирана користећи сортирање уметањем, може се показати да ProxmapSort и bucket sort раде паралелном линеарном временском сложеношћу.[1] Међутим, перформансе овог сортирања опадају са повећањем броја кључева у кофама; уколико су вредности збијене, биће сврстане у исту кофу и перформасе ће бити значајно умањене. Ова особина важи и за ProxmapSort: уколико су кофе превелике, перформансе ће значајно опасти.

Референце[уреди]

  1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174-177.

Литература[уреди]

  • Thomas A. Standish. Data Structures in Java. Addison Wesley Longman, 1998. ISBN 0-201-30564-X. Section 10.6, pp. 394-405.

Спољашње везе[уреди]