Paralelní Sort – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

hoacin0
Newbie
17. 4. 2013   #1
-
0
-

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

Nahlásit jako SPAM
IP: 88.100.48.–
vitamin+8
Grafoman
17. 4. 2013   #2
-
0
-

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++? 

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
hoacin0
Newbie
17. 4. 2013   #3
-
0
-

#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...

Nahlásit jako SPAM
IP: 88.100.48.–
KIIV
~ Moderátor
+43
God of flame
17. 4. 2013   #4
-
0
-

#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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
hoacin0
Newbie
17. 4. 2013   #5
-
0
-

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  

Nahlásit jako SPAM
IP: 88.100.48.–
KIIV
~ Moderátor
+43
God of flame
17. 4. 2013   #6
-
0
-

#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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
hoacin0
Newbie
17. 4. 2013   #7
-
0
-

#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í.

Nahlásit jako SPAM
IP: 88.100.48.–
hoacin0
Newbie
18. 4. 2013   #8
-
0
-

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  

Nahlásit jako SPAM
IP: 88.100.48.–
hoacin0
Newbie
18. 4. 2013   #9
-
0
-

   

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

Nahlásit jako SPAM
IP: 88.100.48.–
vitamin+8
Grafoman
18. 4. 2013   #10
-
+1
-
Zajímavé

#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)

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
hoacin0
Newbie
18. 4. 2013   #11
-
0
-

#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.

Nahlásit jako SPAM
IP: 88.100.48.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 17 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý