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:
- uradi nešto sa podacima
- 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 Majkrosoftove Parallel Pattern Library (PPL) koja radi sa procesorima sa više jezgara se dobro pokazala u praksi.[3]
Reference
[уреди | уреди извор]- ^ 8.4. heapq — Heap queue algorithm — Python v2.7.5 documentation
- ^ 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
- ^ V. J. Duvanenko, "Parallel Merge", Dr. Dobb's Journal, February 2011
Literatura
[уреди | уреди извор]- Knuth, Donald (1997). The Art of Computer Programming. Volume 3: Sorting and Searching, Third Edition. Addison-Wesley. ISBN 978-0-201-89685-5. Pages 158-160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging. pp. 197-207.
- Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). „Section 27.3: Multithreaded merge sort”. Introduction to Algorithms (Third изд.). MIT Press and McGraw-Hill. стр. 797-804. ISBN 978-0-262-03384-8.