Алгоритам спајања
Алгоритми спајања су групе алгоритама који раде секвенцијално са више сортираних низова и обично производе више сортираних низова као излаз. Употреба алгоритма је опала због великих РАМ меморија и многе апликације које користе овај алгоритам имају брже алтернативе када се користи РАМ.
Општи алгоритам спајања има низ показивача п0..н који показују на позиције у групи низова L0..н. Иницијално они показују на први елемент сваког низа. Алгоритам гласи:
Све док неки од показивача п0..н показује на податке у низовима L0..н:
- уради нешто са подацима
- пронађи који од показивача показује на најмањи елемент; преусмери показивач на следећи елемент
Анализа уреди
За рад ових алгоритама обично је потребно време пропорционално суми дужина низова. Они алгоритми који истовремено раде са великим бројем низова множе суму дужина низова са временом да би пронашли показивач на најмањи елемент, што се може постићи помоћу реда са приоритетом који је базиран на хипу за О(лог н) времена, за О(м лог н) времена, где је н број низова који се спајају а м је сума дужина низова. Када се спајају два низа дужине м, доња граница поређења у најгорем случају је 2м − 1.
Класично спајање (које се користи у сортирању спајањем) као излаз враћа најмањи елемент; ако на улазу има сортиране низове, као излаз враћа сортирани низ који садржи сортиране елементе било ког низа са улаза, и то чини у времену пропорционалном суми дужина низова са улаза.
Језичка подршка уреди
Стандардна C++ библиотека садржи функцију std::merge, која спаја два сортирана низа и std::inplace_merge, која спаја два узастопно сортирана низа у месту. Класа std::list има свој метод merge() који себи припаја другу листу. Типови спојених елемената морају да садрже оператор мање (<) или се мора обезбедити произвољан компаратор.
Стандардна Пyтхон библиотека (од верзије 2.6) такође има функцију merge() у heapq модулу, која узима више сортираних низова и спаја их у један.[1]
Паралелно спајање уреди
Код мултипрограмирања, низови сортираних вредности се могу ефикасно спојити помоћу проблема свих најближих најмањих вредности.[2]
Паралелно спајање се такође може имплементирати помоћу завади-па-владај алгоритма. Овај алгоритам добро ради када се искористи са брзим секвенцијалним спајањем као базни случај спајања малих низова. Имплементација помоћу Интелових Тхреадинг Буилдинг Блоцкс (ТББ) и Мајкрософтове Параллел Паттерн Либрарy (ППЛ) која ради са процесорима са више језгара се добро показала у пракси.[3]
Референце уреди
- ^ 8.4. хеапq — Хеап qуеуе алгоритхм — Пyтхон в2.7.5 доцументатион
- ^ Беркман, Омер; Сцхиебер, Баруцх; Висхкин, Узи (1993), „Оптимал доубле логаритхмиц параллел алгоритхмс басед он финдинг алл неарест смаллер валуес”, Јоурнал оф Алгоритхмс, 14 (3): 344—370, дои:10.1006/јагм.1993.1018
- ^ V. Ј. Дуваненко, "Параллел Мерге", Др. Добб'с Јоурнал, Фебруарy 2011
Литература уреди
- Кнутх, Доналд (1997). Тхе Арт оф Цомпутер Программинг. Волуме 3: Сортинг анд Сеарцхинг, Тхирд Едитион. Аддисон-Wеслеy. ИСБН 978-0-201-89685-5. Пагес 158-160 оф сецтион 5.2.4: Сортинг бy Мергинг. Сецтион 5.3.2: Минимум-Цомпарисон Мергинг. пп. 197-207.
- Цормен, Тхомас; Леисерсон, Цхарлес; Ривест, Роналд; Стеин, Цлиффорд (2009). „Сецтион 27.3: Мултитхреадед мерге сорт”. Интродуцтион то Алгоритхмс (Тхирд изд.). МИТ Пресс анд МцГраw-Хилл. стр. 797-804. ИСБН 978-0-262-03384-8.