Algoritam spajanja

Из Википедије, слободне енциклопедије

Algoritmi spajanja su grupe algoritama koji rade sekvencijalno sa više sortiranih nizova i obično proizvode više sortiranih nizova kao izlaz. Upotreba algoritma je opala zbog velikih RAM memorija i mnoge aplikacije koje koriste ovaj algoritam imaju brže alternative kada se koristi RAM.

Opšti algoritam spajanja ima niz pokazivača p0..n koji pokazuju na pozicije u grupi nizova L0..n. Inicijalno oni pokazuju na prvi element svakog niza. Algoritam glasi:

Sve dok neki od pokazivača p0..n pokazuje na podatke u nizovima L0..n:

  1. uradi nešto sa podacima
  2. pronađi koji od pokazivača pokazuje na najmanji element; preusmeri pokazivač na sledeći element

Analiza[уреди]

Za rad ovih algoritama obično je potrebno vreme proporcionalno sumi dužina nizova. Oni algoritmi koji istovremeno rade sa velikim brojem nizova množe sumu dužina nizova sa vremenom da bi pronašli pokazivač na najmanji element, što se može postići pomoću reda sa prioritetom koji je baziran na hipu za O(log n) vremena, za O(m log n) vremena, gde je n broj nizova koji se spajaju a m je suma dužina nizova. Kada se spajaju dva niza dužine m, donja granica poređenja u najgorem slučaju je 2m − 1.

Klasično spajanje (koje se koristi u sortiranju spajanjem) kao izlaz vraća najmanji element; ako na ulazu ima sortirane nizove, kao izlaz vraća sortirani niz koji sadrži sortirane elemente bilo kog niza sa ulaza, i to čini u vremenu proporcionalnom sumi dužina nizova sa ulaza.

Jezička podrška[уреди]

Standardna C++ biblioteka sadrži funkciju std::merge, koja spaja dva sortirana niza i std::inplace_merge, koja spaja dva uzastopno sortirana niza u mestu. Klasa std::list ima svoj metod merge() koji sebi pripaja drugu listu. Tipovi spojenih elemenata moraju da sadrže operator manje (<) ili se mora obezbediti proizvoljan komparator.

Standardna Python biblioteka (od verzije 2.6) takođe ima funkciju merge() u heapq modulu, koja uzima više sortiranih nizova i spaja ih u jedan.[1]

Paralelno spajanje[уреди]

Kod multiprogramiranja, nizovi sortiranih vrednosti se mogu efikasno spojiti pomoću problema svih najbližih najmanjih vrednosti.[2]

Paralelno spajanje se takođe može implementirati pomoću zavadi-pa-vladaj algoritma. Ovaj algoritam dobro radi kada se iskoristi sa brzim sekvencijalnim spajanjem kao bazni slučaj spajanja malih nizova. Implementacija pomoću Intelovih Threading Building Blocks (TBB) i Microsoftove Parallel Pattern Library (PPL) koja radi sa procesorima sa više jezgara se dobro pokazala u praksi.[3]

Reference[уреди]

  1. ^ 8.4. heapq — Heap queue algorithm — Python v2.7.5 documentation
  2. ^ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), „Optimal double logarithmic parallel algorithms based on finding all nearest smaller values“, Journal of Algorithms 14 (3): 344–370, DOI:10.1006/jagm.1993.1018 
  3. ^ V. J. Duvanenko, "Parallel Merge", Dr. Dobb's Journal, February 2011