登录 / 注册
IT168技术开发频道
IT168首页 > 技术开发 > 技术开发资讯 > 正文

并行算法库清单: 附各算法代码实例!

2017-11-30 09:26    it168网站原创  作者: 编译 | 钰莹 编辑: 赵钰莹

  【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

标签: 程序员 , 并行计算
  • IT168企业级IT168企业级
  • IT168文库IT168文库

扫码送文库金币

编辑推荐
系统架构师大会
系统架构师大会
点击或扫描关注
IT168企业级微信关注送礼
IT168企业级微信关注送礼
扫描关注
首页 评论 返回顶部