並行算法庫清單: 附各算法代碼實例!

　　【IT168 資訊】並行算法採用並行程式語言NESL實現，該語言是卡內基梅隆大學Scandal項目中開發的一種程式語言。對於每個算法，團隊給出了一個簡短的描述以及複雜性評估(就工作和深度而言)。

　　在很多情況下，NESL代碼已經設置完畢，可以使用FORMs基本接口來運行算法。隨意更改數據或算法，並提交修改後的版本。請注意，一些算法已經規定了對輸入的限制(例如必須是均勻的)。

　　注意：本文涉及的一些功能描述和文檔非常簡潔，但都是可以正常工作的。(原文地址：https://www.cs.cmu.edu/~scandal/nesl/algorithms.html#scan，所有代碼示例均可點擊進入原文查看)

　　並行算法序列和字符串：

　　·Scan (prefix sums)

　　·List ranking

　　·Sorting

　　·Merging

　　·Medians

　　·Searching

　　·String matching

　　·Other string operations

　　並行算法的樹和圖：

　　·Trees

　　·Connected components

　　·Spanning trees

　　·Shortest paths

　　·Maximal independent set

　　·Graph separators

　　計算幾何的並行算法：

　　·Convex hull

　　·Closest pairs

　　·Delaunay triangulation

　　數值/科學計算的並行算法

　　·Fourier transform

　　·Dense matrix operations

　　·Sparse matrix operations

　　·N-body code

　　·Other

　　Scan

　　Scan操作(也稱為all-prefix-sum)採用二元聯合運算符作為標識函數和arry，並返回一個新數組，其中每個元素具有所有先前元素的總和(sum是相對於關聯運算符定義的)。例如

　　scan(+, 0, [2, 8, 9, -4, 1, 3, -2, 7]);

　　是

　　[0, 2, 10, 19, 15, 16, 19, 17]

　　算法

　　·Tree Scan

　　List Ranking

　　List ranking需要一個連結列表，並返回列表中每個元素的位置。位置給出了距列表尾部的距離。使用整數數組表示列表，其中每個整數表示列表中下一個元素的索引。我們用自指針終止列表。 例如，數組

　　[2, 5, 1, 3, 7, 6, 6, 3]

　　代表以下兩列：

　　0 -> 2 -> 1 -> 5 -> 6

　　4 -> 7 -> 3

　　算法：

　　·Wyllie

　　·Random Mate

　　·Sorting

　　有許多並行排序算法。這裡給出了一些示例。

　　算法

　　·Quicksort

　　·Selection sort

　　·Insertion sort

　　·Counting sort

　　·Batcher's Bitonic Sort

　　·Radix Sort

　　·String Radix Sort

　　Merging算法：

　　·Batcher's Odd-Even Merge

　　·Halving Merge

　　Medians

　　這裡考慮找到一個集合中第k個最小元素的問題。眾所周知，這個問題可以在O(n)時間序列內解決。在這裡考慮的兩個算法都需要O(n)的工作，雖然第一個是預期的情況，第二個是高概率。

　　算法

　　·Quick Select

　　·Sample Select

　　Searching算法：

　　·Hash Tables

　　String Matching

　　字符串匹配問題需要一個TEXT字符串和一個PATTERN字符串，並查找模式在文本中出現的所有位置。

　　算法：

　　·Naive algorithm

　　·Vishkin algorithm

　　其他字符串

　　這裡考慮字符串的各種操作，比如按字母順序比較兩個字符串，將一串字符分解成幾行，然後再匹配括號。

　　算法

　　·String comparison

　　·breaking a string into lines

　　·Matching Parentheses

　　樹算法：

　　·Generate Euler tour from edgelist

　　·Rootfix (e.g. for level numbering)

　　·Leaffix (e.g. for subtree sizes)

　　連接組件

　　連接組件問題採用無向圖，並返回所有通過邊連接的組件。對於一個有n個頂點和m條邊的圖，這個問題可以用O(n + m)時間順序地使用深度優先搜索或寬度優先搜索來解決，並行算法是基於收縮圖的思想。

　　算法

　　·Awerbuch Shiloach

　　·Random mate

　　·Hybrid

　　生成樹

　　生成樹算法與連接組件類似，但生成樹算法需要跟蹤哪些邊用於收縮，而不需要將圖擴展回去。

　　算法

　　·Hybrid based Spanning Tree

　　短路徑算法：

　　·Breadth First Search

　　最大獨立集算法:

　　·Luby's Algorithm

　　圖劃分算法：

　　·Spectral

　　·Recursive bisection

　　·Teng/Vavasis/Miller

　　Convex Hull算法：

　　·Jarvis March

　　·Quickhull

　　·Kirkpatrick-Seidel

　　·Overmar's Mergehull

　　·Atallah's variant of Overmar's Mergehull (O(lg n) time)

　　Closest Pairs算法：

　　·All closest pairs

　　Delaunay Triangulation算法：

　　·Projection based

　　·Closest pair based

　　Fourier Transform算法：

　　·Fast Fourier transform

　　Dense Matrix Operations算法：

　　·Matrix multiply

　　·Matrix inverse

　　·Linear system solve

　　·Null space of matrix

　　Sparse Matrix Operations算法：

　　·Matrix-vector multiply

　　·Jacobi

　　·Conjugate gradient

　　N-body Code算法：

　　·All pairs

　　·Barnes-Hut

　　·Greengard's FMM

　　·PMTA (a hybrid)

　　其他數值編碼算法：

　　·prime numbers

　　·adaptive integration

　　·line fitting

　　·order-m recurrences

　　·Tree based preconditioner