Тимсорт

Из Википедије, слободне енциклопедије
Тимсорт
Намена сортирање
Структура података низ
Временска компл. O(n\log n)[1]
Средња ВК O(n\log n)
Меморијска компл. O(n)

Тимсорт је хибридни алгоритам за сортирање, дериват сортирања спајањем и селекцијом, дизајниран да се понаша добро на много врста реалних светских података. Направио га је Тим Петерс 2002. године за потребе Пајтон програмског језика. Алгоритам проналази подскупове података који су већ поређани, и користи то знање да сортира остатак ефикасније. Ово се ради спајањем идентификованог скупа, који се назива пролаз, са постојећим пролазима док одређени критеријум није испуњен. Тимсорт је Пајтонов стандардни алгоритам за сортирање од верзије 2.3. Користи се за сортирање низова у Java SE 7,[2] на Андроид платформи,[3]и у ГНУ Октави.[4]

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

Тимсорт је дизајниран да користи предности парцијалног редоследа који већ постоји у већини података из реалног света. Тимсорт ради тако што налази пролазе, подскупове од најмање два елемента, међу подацима. Пролази су или неопадајући(сваки елемент је једнак или већи од претходног) или стриктно опадајући(сваки елемент је мањи од претходног). Ако је опадајући, онда мора бити строго опадајући, пошто се опадајући пролази касније обрћу једноставним заменама елемената са оба краја конвергирајући у средини. Овај метод је стабилан ако се елементи презентују у стриктно опадајућем редоследу. После обављања оваквог пролаза у датом низу, Тимсорт га прихвата и процесуира, и онда тражи следећи пролаз.

Минипролаз[уреди]

Тимсорт алгоритам тражи овакве сортиране секвенце, минипролазе, да убрза поступак

Природни пролаз је подниз који је већ сортиран. Природни поднизи у реалном свету могу бити подаци различитих дужина. Тимсорт бира технике сортирања у зависности од дужине пролаза. На пример, ако је пролаз мањи од одређене дужине, користи се сортирање уметањем. Према томе, тимсорт је прилагодљив алгоритам.[5] Величина пролаза се пореди са минимумом величине пролаза. Минимална величина пролаза(минипролаз) зависи од дужине низа. За низ који има мање од 64 елемента, минипролаз је величине низа, редукујући тимсорт на сортирање уметањем. За веће низове, минипролаз се бира у рангу између 32 и 64 елемента, тако да је величина низа, подељена минипролазом, једнака или мало мања од степена двојке. Финални алгоритам узима шест најзначајнијих битова величине низа, додаје један ако су сви недостајући битови постављени, и користи тај резултат као минипролаз. Овај алгоритам ради за све низове, укључујући и оне мање од 64.[5]

Сортирање уметањем[уреди]

Када су низови случајни, природни пролази ће вероватно имати мање елемената од минипролаза. У овом случају, одређен број успешних елемената се бира, и сортирање уметањем повећава величину пролаза до минипролаза. Према томе, већина пролаза у случајном низу су, или постану, минипролази у величини. Резултат су ефикасна, балансирана спајања. Такође, резултује разумним бројем позива функција при имплементацији алгоритма.[6]

Спајање меморије[уреди]

Минипролази се умеђу у стек. Ако X < Y + Z тада се X и Y се спајају и умећу у стек. Овако, спајање је континуирано све док сви низови не задовољавају а)X > Y + Z и б)Y > Z

Када су дужине пролаза оптимизоване, пролази се спајају. Када је пролаз пронађен, алгоритам гура његову базну адресу и дужину на стек. Функција одређује да ли ће пролаз бити спојен са претходним пролазима. Тимсорт не спаја неузастопне пролазе, јер ако би се то радило изазвало би да елемент, који је заједнички за сва три пролаза постане несортиран. Према томе, спајање се увек ради над узастопним пролазима. Због овога, три највиша пролаза на стеку који су несортирани се гледају. Ако, на пример, X, Y, Z, представљају дужине три највиша пролаза на стеку, алгоритам спаја пролазе тако да следећа два правила задовољена:

  1. X > Y + Z
  2. Y > Z[5]

На пример, ако прво правило није задовољено тренутним статусом пролазом, то јест, ако X < Y + Z, тада се Y спаја са мањим измезу X и Y. Спајање се наставља док оба правила нису испуњена. Тада алгоритам одређује следећи пролаз.[6] Правила горе су направљена са циљем одржавања величине пролаза што је могуће ближе једна другој да би се балансирала спајања. Само мали број пролаза се памти, пошто је стек специфичне величине. Алгоритам користи свеже појаве пролаза да их споје, у кеш меморији. Према томе, компромис се постиже тако што се одлаже спајање, а користи свеже појављивање у кеш меморији.

Процедура спајања[уреди]

Алгоритам ствара привремену меморију једнаку величини мањег низа. Тада, он премешта из(рецимо да је Х мање)Х у привремену меморију и онда сортира и пуни елементе у финалном реду у комбинован простор од Х и У

Спајање суседних пролаза се ради уз помоћ привремене меморије. Привремена меморија је величине мањих од два пролаза. Алгоритам копира мањи од два пролаза у привремену меморију и користи оригиналну меморију и меморију другог пролаза да смести сортирани резултат. Једноставни алгоритам сортирања ради са лева на десно, или са десна на лево, у зависности који је пролаз мањи, на привременој и оригиналној меморији већег пролаза. Крајњи сортирани пролаз се смешта у оригиналну меморију два иницијална пролаза. Тимсорт тражи одговарајуће позиције за почетни елемент једног низа у другом користећи адаптацију бинарне претраге. На пример, два пролаза А и Б требају бити спојени, а А је мањи пролаз. У овом случају бинарна претрага гледа А да нађе прву позицију већу од првог елемента у Б(а`). Приметимо да су А и Б већ сортирани индивидуално. Када је а` је пронађен, алгоритам може игнорисати елементе пре те позиције док убацује Б. Слично, алгоритам такође тражи најмањи елемент у Б(б`) већи од највећег елемента у А(а). Елементи после б` могу такође бити игнорисани при спајању. Ова прелиминарна претрага није ефикасна за висок степен насумичности података, али је ефикасна за друге ситуација, па је према томе, укључена.

Галопирајући мод[уреди]

Елементи(означени плавом стрелицом) се пореде и мањи елемент се смешта на финалну позицију(коју означава црвена стрелица).

Спајање се углавном дешава кад је позван „један по један пар“, када су елементи оба пролаза прошли поређење. Када алгоритам спаја лево на десно, мањи од два се доводи у део за спајање. Бројач броја пута у којим се крајњи елемент појави у датом пролазу се памти. Када ова вредност достигне одређени праг, МИН_ГАЛОП, спајање се пребацује у „галопирајући мод“. У овом методу се користи претходно поменута адаптација бинарне претраге, да се утврди где први елемент мањег низа треба бити смештен у већем низу(и супротно). Функције mege-lo и merge-hi инкрементирају вредност мин_галопа, ако галопирање није ефикасно, и декрементира ако јесте. Ако више узастопних елемената долази из различитих пролаза, излази се из галопирајућег мода.[5]

Сви црвени елементи су мањи од плавих(овде, 21). Према томе, могу бити померени у део до крајњег низа.

У галопирајућем моду, алгоритам тражи први елемент једног низа у другом. Ово се ради поређењем првог елемента(иницијалног елемента) са нултим елементом у другом низу, онда са првим, трећим и тако даље, то је (2к-1)ти елемент, тако да се добије ранг елемената између којих ће иницијални елемент бити. Ово сужава ранг бинарне претраге, према томе повећава ефикасност. Галопирање се показало ефикасније осим у случајевима специфично дугих пролаза, али насумични подаци обично имају краће пролазе. Такође, у случајевима када се галопирање показује мање ефикасно од бинарне претраге, излази се из галопирајућег мода.

Галопирање није увек ефикасно. Један од разлога је велики број позива функција. Позиви функција су скупи и према томе када се јављају често, утичу на ефикасност програма. У неким случајевима галопирање захтева више поређења од обичне линеарне претраге. Док за прве случајеве оба мода могу захтевати исти број поређења, током времена галопирање захтева 33% више поређења од линеарне претраге да би добио исти резултат. Додатно, сва поређења се врше позивом функција.

Галопирање је корисно једино када је почетни елемент пролаза није међу првих седам елемената другог пролаза. Ово имплицира МИН_ГАЛОП од седам. Да би се избегла задржавања галопирајућег мода, спајајуће функције подешавају вредност мин_галопа. Ако је елемент из низа који тренутно враћа елементе, мин_галоп се смањује за један. Иначе, вредност се повећава за један, па смањује вероватноћу преласка у галопирајући мод. Када се ово уради, у случају насумичних података, вредност мин_галопа се поваћава толико да се никад не улази у галопирајући мод.

У случају коришћења merge-hi функције(тј. спаја се са десна на лево), галопирање почиње са десног краја података, односно од последњег елемента. Галопирање од почетка такође даје потребне резултате, али прави више поређења. Према томе, алгоритам галопирања користи променљиву која чува индекс од којег галопирање треба почети. Тимсорт може ући у галопирање у било којем индексу и наставити да проверава следећи индекс који је противтежа 1, 3, 7,...., (2к-1)... и тако даље од тренутног индекса. У случају merge-hi, противтежа индексу ће бити -1, -3, -7...[5]

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

Према информационој теорији, ни један алгоритам поређења не може боље од \Theta(n \log n)поређења у просечном случају. На реалним подацима, тимсорт често захтева много мање од \Theta(n \log n) поређења, јер користи чињеницу да су подскупови скупа већ сортирани.[7] У случају да су подаци потпуно обрнути у односу на смер сортирања, тимсорт се приближава теоретском лимиту \log(n!) који је у \Theta(n \log n) Следећа таблица пореди сложеност тимсорта и осталих алгоритама за сортирање.[5]

Тимсорт Сортирање спајањем Квиксорт Сортирање уметањем Сортирање селекцијом Смутсорт
Најбољи случај \Theta(n) \Theta(n \log n) \Theta(n \log n) \Theta(n) \Theta(n^2) \Theta(n)
Просечан случај \Theta(n \log n) \Theta(n \log n) \Theta(n \log n) \Theta(n^2) \Theta(n^2) \Theta(n \log n)
Најгори случај \Theta(n \log n) \Theta(n \log n) \Theta(n^2) \Theta(n^2) \Theta(n^2) \Theta(n \log n)


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

Timsort Сортирање спајањем Квиксорт Сортирање уметањем Сортирање селекцијом Смутсорт
Просторна сложеност O(n) O(n) O(\log n) O(1) O(1) O(1)

Приметимо, међутим, да просторна сложеност и тимсорта и сортирања спајањем може бити смањена на \log n по цени брзине(погледајте сортирање у месту).

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

  1. ^ Peters, Tim. „[Python-Dev] Sorting“. Python Developers Mailinglist Приступљено 24 Feb 2011. „[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N-1 compares is best).“ 
  2. ^ jjb. „Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort“. Java Development Kit 7 Hg repo Приступљено 24 Feb 2011. 
  3. ^ „Class: java.util.TimSort<T>“. Android JDK 1.5 Documentation Приступљено 24 Feb 2011. 
  4. ^ „liboctave/util/oct-sort.cc“. Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Приступљено 18 Feb 2013. „Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.“ 
  5. ^ а б в г д ђ timsort, python. „python_timsort“. 
  6. ^ а б timsort, understanding. „understanding timsort“. 
  7. ^ Martelli, Alex (2006). Python in a Nutshell (In a Nutshell (O'Reilly)). O'Reilly Media, Inc.. стр. 57. ISBN 0-596-10046-9. 

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