45 - Distribuované a paralelní algoritmy - algoritmy vyhledávání Flashcards
Optimální algo
Optimální sekvenční algoritmus pro vyhledávání
a. X není seřazená - sekvenční vyhledávání
○ t(n)=O(n), je potřeba prozkoumat n prvků.
b. X je seřazená - binární vyhledávání
○ t(n)=O(logn )
Tak mě ještě napadá co Hash tables? Ty jsou konstantní ne?
N-ary search - seřazená posloupnost
Vyhledává v seřazené posloupnosti. - rozdělíme na části podle počtu procesorů, zjistíme v jaké části se nachází
Princip algoritmu
• Při binárním vyhledávání zjistíme v každém kroku ve které polovině se prvek nachází za pomocí jednoho procesoru.
• S použitím N procesorů lze provést N+1 ární vyhledávání - v jednom kroku zjistíme, ve které z N+1 části se může prvek nacházet.
Vlastnosti
- Je potřeba CREW PRAM
• Časový složitost - t(n)=O(log(n+1)/log(N+1) )
• Cena - c(n)=O(N∗log_(N+1)〖(n+1)〗) - není optimální
N-ary search - NEseřazená posloupnost - OPTIMÁLNÍ S CRCW
Vyhledává prvek v neseřazené posloupnosti.
Princip algoritmu
1. Hledaný prvek x pošlu paralelně všem N procesorům.
2. Každý z procesorů sekvenčně prohledá svůj prostor o velikosti n/N.
3. Paralelně si projdu si výsledky od procesorů a pokud nějaký z nich prvek našel, tak ho vrátím.
Vlastnosti
Model je PRAM s N procesory.
• EREW
1. krok = O(logN ), data dokážeme mezi procesy destribuovat a log. čase
2. krok = O(n/N)
3. krok = O(logN ), data dokážeme z procesorů dostat také v log. čase
○ t(n)=O(logN+n/N) — c(n)=O(N∗logN+n)
• CREW
1. krok = O(1), máme concurent read, takže distribuci dat máme hned
2. krok = O(n/N)
3. krok = O(log N), data dokážeme z procesorů dostat v log. čase
○ t(n)=O(logN+n/N) — c(n)=O(N∗logN+n)
• CRCW
1. krok = O(1), data dokážeme mezi procesy destribuovat a log. čase
2. krok = O(n/N)
3. krok = O(1), data dokážeme z procesorů dostat hned jelikož máme concurent write
○ t(n)=O(n/N) — c(n)=O(n), což je optimální
Tree Search - NEseřazená posloupnost
pošleme hodnotu do listů, pokud je přítomna, list pošle zpátky 1, jinak 0
Princip algoritmu
1. Kořen načte hledanou hodnotu x a předá ji synům … až se dostane ke všem listům.
2. Listy obsahují seznam prvků, ve kterých se vyhledává (každý list jeden). Všechny listy paralelně porovnávají x a x_i, výsledek je 0 nebo 1.
3. Hodnoty všech listů se předají kořenu.
○ Každý ne-list spočte logické OR svých synů a výsledek zašle otci. Kořen dostane 0 - nenalezeno, 1 - nalezeno
Vlastnosti Stromová architektura s 2n−1 procesory. 1. krok - O(logn) 2. krok - O(1), procesor porovná příchozí hodnotu s tou, kterou obsahuje 3. krok - O(logn), distribuce výsledku ke kořenu • t(n)=O(logn ) • p(n)=O(2n−1) • c(n)=O(n∗logn), což není optimální