Paralelní Sort – C / C++ – Fórum – Programujte.com

Ahoj, znáte nějakou knihovnu, funkci, která podporuje paralelní sort? Třídím 20 milionové pole a klasickej qsort trvá asi 4 vteřiny a je to trochu na obtíž na to pořád dokola čekat...

Na netu jsem našel a stáhnul nějaký soubory .h a .inl z knihovny Thrust, ale moc chytrej z toho nejsem...  

Díky

Mozes pouzit quick sort a merge sort. Na tych linkoch mas obrazky ako funguju, pole vecsinou delis na viacej casti a tie potom rekruzivne sortujes. Mozes sortovat kazdu cast v inom vlakne. Pouzivas c alebo c++? 

#2 vitamin

Používám c++ a pro paralelizaci OpenMP. Mě napadlo že to rozdělím v OpenMP, jen mi nebylo jasný, co udělám s těma seřazenýma blokama na konci, budu mít 12 polí (počet vláken) a každý bude mít 20 000 000 / 12 seřazených prvků a teď co s tím?  Kouknu na obrázky a třeba mi to dojde...

#3 hoacin
ja bych dejme tomu otestoval par desitek hodnot, vybral neco jako stred, a rozdelil pole a prohazel prvky co do polovin nepatri (alias jedna iterace quick sortu s trosku lepsim vybiranim stredu razeni),   pak mas poloviny, co se daji radit paralelne a to rozdeleni zase zarucuje, ze to na sebe bude navazovat...

jen to chce fakt trosku inteligentni hledani toho stredu ..  paralelne to uz pak bezet muze

S tou střední hodnotou to bude oříšek, není to číslo ale 160 bitová struktura která obsahuje tři proměnné s prvočíselnými součiny (každé prvočíslo je nějaká vlastnost a jejich součin je pak unikátní ID kombinace těch vlastností). Takže co za data a jak moc setříděná ve smyslu když bych udělal třeba statistiku z tisícovky příkladů té první proměnné třeba, si netroufám odhadovat. No popřemýšlím o tom, nějak to půjde  

#5 hoacin
tak nemusis nutne z tolika... zalezi na rozlozeni.. hlavni je netrefit krajni meze

Mimochodem jaky sou rozsahy tech prvocisel? Treba je 160b zbytecne moc... treba by se to dalo seradit uz pri generovani .. nebo nacitani.. kdo vi jak dlouho trva to

#6 KIIV

Ty prvočíselný součiny jsou rozsahem kolem 34 bitů, právě se to těsně nevlezlo na uint. Teď mě ale napadá, že podle toho třetího identifikátoru to půjde seřadit asi celkem dobře, tam ta čísla půjdou nějak předvídat, co je zhruba střední hodnota. Možná bych si nějakou střední hodnotu mohl vypočítat i při tom generování.

Jen ze zvědavosti, neexistuje nějakej rychlejší "sort" na to, když potřebuju jen dostat stejné hodnoty k sobě? Mně je v tom výpočtu jedno jestli mi to seřadí jako 1 4 4 4 5 7 7 9 nebo 7 7 1 9 4 4 4 5  

Ahoj, nechtěl jsem kvůli tomu zakládat nový vlákno. Je nějaký důvod, aby funkce qsort a memcpy nemohly běžet paralelně?    Když si do toho té pragmy dám message box s číslem threadu tak normálně vyskočí 12 message boxů s čísly 0...11 přesně jak bych očekával. Když tam ale použiju memcpy nebo qsort, padá to. Bohužel OpenMP nemůžu otestovat v debug verzi ale jen v release, tak se to blbě hledá. Je nějaký důvod, aby tyto funkce nemohly běhat paralelně?  

Díky

#9 hoacin
Sice ti neodpoviem na tvoju otazku (neovladam OpenMP) ale tvoj kod sa da urychlit aj inymi sposobmi. 

Najprv by si sa mal vykaslat na qsort. Radsej pouzi std::sort ktory umoznuje inlinovat porovnavaciu funkciu.

Aky pouzivas kompilator? (Nemozes pouzit thready z c++11 ?   http://en.cppreference.com/w/cpp/thread)

#10 vitamin
Díky.

OpenMP - samozřejmě to nebylo tak žhavý, jak jsem v OpenMP novej, tak jsem myslel, že počet dostupných vláken se volá funkcí omp_get_num_threads a ono se mělo použít omp_get_num_procs, já tu funkci už používal, jenže tam kde jsem ji volal zrovna vracela to co jsem čekal a tady vracela jedničku, na čemž to padalo  

std::sort - neznám, kouknu na to   Používám microsoft visual studio 2010, takže nějakej microsofťáckej kompilátor.