Проксмап сортирање — разлика између измена

нема резимеа измене
|space=<math>O(n)</math>
}}
'''Проксмапсорт''' или '''Проксмап сортирање''' је врста [[Алгоритми_сортирања|алгоритма сортирања]], који ради тако што подели [[Низ_(структура_података)|низ]] података, или кључева, на мањи број поднизова. Име је скраћеница од рачунања "proximity map"-е, која одређује, за сваки кључ К, почетак подниза у коме ће се К налазити у коначном поретку. Кључеви су постављени у сваки подниз коришћењем [[Sortiranje_ubacivanjem|сортирања уметањем]]. Уколико су кључеви добро распоређени кроз поднизове, временска сложеност сортирања је линеарна, што је много брже од [http://en.wikipedia.org/wiki/Comparison_sort Comparison sort] сортирања, које не може бити боље од О(nlogn). Процене [[Теорија_комплексности|теорије комплексности]] укључују број поднизова и proximity mapping функцију. То је облик [[Алгоритми_сортирања#Bucket_sort|Bucket sort-а]] и [[Алгоритми_сортирања#Radix_sort|Radix sort-а]]. Алгоритам не постаје много комплекснији како количина података расте.
 
Када је проксмап сортирање завршено '''ProxmapSearch''' може бити коришћено за проналазак кључева у сортираном низу за временску сложеност О(1), уколико су кључеви добро распоређени током сортирања.
==Историја==
*Изумели су га [http://www.ics.uci.edu/faculty/profiles/view_faculty.php?ucinetid=standish Томас А. Стандиш], Prof. Emeritus, Department of Informatics, [http://en.wikipedia.org/wiki/Donald_Bren_School_of_Information_and_Computer_Sciences Donald Bren School of Information and Computer Sciences], University of California, Irvine крајем осамедесетих.
 
==Преглед==
===Основна стратегија===
Основа: За низ А са n кључева:
*мапира кључ у поднизу крањег низа А2 применом map key функција за сваки елемент низа
*одређује колико кључева ће бити мапирано на исти подниз користећи низ '''"броја погодака," H'''
*одређује где почиње сваки подниз у крајњем низу, тако да је свака "кофа" одговарајуће величине за све кључеве који ће бити мапирани, користећи низ '''"проксмапа" P'''
*за сваки кључ, рачуна подниз на који ће бити мапиран, користећи низ '''"локација" L'''
*за сваки кључ, проналази локацију и смешта га у ћелију А2; ако настаје колизија са кључем који је већ ту, сотрира се уметањем, померањем већих кључева за једно место у десно, како би се обезбедио простор за овај кључ. Пошто су поднизови довољно велики да складиште све кључеве који су мапирани на њих, неће доћи до прекорачења у наредни подниз.
Једноставније: За низ А са n кључева:
#'''Иницијализуј''': Направи и иницијализуј два низа дужине n: '''hitCount''', '''proxMap''' и 2 низа дужине '''A'''.length: '''локацију''' и '''A2'''.
# '''Дељење''': користећи пажљиво одабрану '''mapKey''' функцију, подели '''A2''' на поднизове, користећи кључеве из '''A'''.
# '''Распореди''': прођи кроз '''A''', убаци сваки кључ у одговарајућу кофу у '''A2'''; сортирање уметањем по потреби.
# '''Прикупљање''': прођи кроз поднизове редом и постави све елементе у оригинални низ, или простије, користи '''A2'''.
Напомена: кључеви могу садржати и друге податке, на пример, инстанца низа објекта Студент садржи кључ, али и индекс студента и име. ProxMapSort је погодан за организацију група објеката, а не само кључева.
===Пример===
Узмимо пун низ: '''A'''[''0'' до ''n-1''] са ''n'' кључева. Нека је ''i'' индекс низа A. Сортирај кључеве '''A'''' у низ '''A2''' исте величине.
Мap key функција је дефинисана као mapKey(key) = floor(K).
{| class="wikitable" style="text-align: center; width: 400px; border: 1px solid black;"
|+ Array table
|-
! scope="row" | 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
|-
! scope="row" | H
| 1 || 3 || 0 || 1 || 1 || 1 || 2 || 1 || 1 || 0 || 1 || 1
|-
! scope="row" | P
| 0 || 1 || -9 || 4 || 5 || 6 || 7 || 9 || 10 || -9 || 11 || 12
|-
! scope="row" | L
| 7 || 6 || 10 || 1 || 9 || 4 || 12 || 1 || 5 || 0 || 11 || 7 || 1
|-
! scope="row" | 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
|}
[[File:ProxMapSortDemo.gif|A demonstration of ProxMapSort, a bucket sort variant that uses intermediate parallel arrays to efficiently index and size its sublists.]]
<br clear=all>
===Псеудокод===
<source lang="java">
// 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
}
}
</source>
Овде, '''A''' је низ који се сортира, а mapKey функција одређује број поднизова који се користе. На пример, floor(K) ће просто доделити онолико поднизова колико има целих бројева у '''A'''. Дељење кључа константом смањује број поднизова; Различите функције се могу користити да преведу домен елемената '''A''' у поднизове, као што су замена слова A–Z са 0–25 или враћање првог елемента (0–255) за дати стринг. Поднизови се сортирају како подаци пристижу, а не када су сви подаци смештени у подниз, као што је случај у типичном [[Алгоритми_сортирања#Bucket_sort|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 функције је важно за избегавање најгорег случаја. Морамо знати нешто о распореду података да бисмо дошли до доброг кључа.
===Oптимизације===
# Штедња времена: Сачувати MapKey(i) вредности, како се не би поново рачунале (као што су у коду изнад).
# Штедња простора: 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''. Уколико је свака кофа сортирана користећи [[Алгоритми_сортирања#Insertion_sort|сортирање уметањем]], може се показати да ProxmapSort и bucket sort раде паралелном линеарном временском сложеношћу.<ref>[[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&ndash;177.</ref> Међутим, перформансе овог сортирања опадају са повећањем броја кључева у кофама; уколико су вредности збијене, биће сврстане у исту кофу и перформасе ће бити значајно умањене. Ова особина важи и за ProxmapSort: уколико су кофе превелике, перформансе ће значајно опасти.
==Референце==
<references />
* Thomas A. Standish. ''Data Structures in Java.'' Addison Wesley Longman, 1998. ISBN 0-201-30564-X. Section 10.6, pp.&nbsp;394&ndash;405.
 
* Thomas A. Standish and Norman Jacobson [http://portal.acm.org/ft_gateway.cfm?id=1138427&type=pdf "Using O(n) ProxmapSort and O(1) ProxmapSearch to Motivate CS2 Students (Part I)"] from [[Donald Bren School of Information and Computer Sciences]] at [[University of California, Irvine|UC Irvine]].
 
* Thomas A. Standish and Norman Jacobson [http://portal.acm.org/citation.cfm?id=1138403.1138427 "Using O(n) ProxmapSort and O(1) ProxmapSearch to Motivate CS2 Students (Part II)"] from [[Donald Bren School of Information and Computer Sciences]] at [[University of California, Irvine|UC Irvine]].
 
* Norman Jacobson [http://www.ics.uci.edu/~jacobson/ics23/ProxmapHandout.pdf "A Synopsis of ProxmapSort & ProxmapSearch"] from Department of Computer Science, [[Donald Bren School of Information and Computer Sciences]], [[University of California, Irvine|UC Irvine]].
==Спољашње везе==
* http://www.cs.uah.edu/~rcoleman/CS221/Sorting/ProxMapSort.html
* http://www.valdosta.edu/~sfares/cs330/cs3410.a.sorting.1998.fa.html
* http://www.cs.uml.edu/~giam/91.102/Demos/ProxMapSort/ProxMapSort.c
 
[[Категорија:Вики студент/Математички факултет]]
28

измена