点击

机器学习算

法与Python学习

选择

加星标

精彩内容不迷路

01

排序算法 | 珠排序(bead sort)详解与Python实现

排序网络的优势在于该类算法是数据无关的,通过构造多个比较器可以很简单的实现并行计算。

什么是双调序列

一个序列 a1,a2, …,an 是双调序列,必须满足以下条件:

(1)存在一个 ak(1 ≤ k ≤ n),使得 a1 ≥ … ≥ ak ≤ … ≤ an 成立;

(2)序列能够循环移位满足条件(1)

什么是Batcher定理

将任意一个长为2n的双调序列A分为等长的两半X和Y,将X中的元素与Y中的元素一一按原序比较,即a[i]与a[i+n] (i < n)比较,将较大者放入MAX序列,较小者放入MIN序列。则得到的MAX和MIN序列仍然是双调序列,并且MAX序列中的任意一个元素不小于MIN序列中的任意一个元素。

其实,到现在还有两个问题:

怎么把普通序列变成双调序列?

怎么对双调序列进行排序?

02

如何进行双调排序(Bitonic sort)?

针对双调序列Z,根据Batcher定理,Z可以划分为2个双调序列X和Y,然后继续对X和Y进行递归划分,得到更短的双调序列,直到得到的子序列长度为1为止。这时的输出序列按单调递增顺序排列。

如图所示,针对序列Z=[10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]进行升序排序:

把序列Z对半分,假设n=2^k=4,然后1和n/2+1比较,小的放上,接下来2和n/2+2比较,小的放上,以此类推;

看成两个(n/2)长度的序列,因为都是双调序列,可以重复上面过程;

总共重复k=4轮,即最后一轮已经是长度是2的序列比较了,就可得到最终的排序结果。

该过程是up bottom的

怎么把普通序列变成双调序列?

采用分治(divide and conquer)思路

Bitonic merge

将两个相邻&单调性相反的单调序列看作一个双调序列, 每次将这两个单调序列merge生成一个新的双调序列, 然后进行双调排序,不断上述过程。流程如下:

对于无序数组 A,相邻的两个数肯定是双调序列,比如 (a0,a1), (a2,a3) 等

bitonic sort

bitonic sort

bitonic sort

步长依次为 2^n: 最后变为前 n/2 元素是升序,后 n/2 是降序的完整双调序列。

和前面sort的思路正相反, 是一个bottom up的过程。

03

复杂度:

串行方式,复杂度O(nlog(n))

n/2个并行,复杂度O(log(n))

36

15

27

57

4

32

69

46

76

99

21

31

92

31

90

13

# 自底向上的构建过程中也包含了自顶向下的排序过程

1

2

15

36

1

2

57

27

1

2

4

32

1

2

69

46

1

2

76

99

1

2

31

21

1

2

31

92

1

2

90

13

2

4

15

27

57

36

1

4

15

27

36

57

2

4

69

46

4

32

1

4

69

46

32

4

2

4

31

21

76

99

1

4

21

31

76

99

2

4

90

92

31

13

1

4

92

90

31

13

4

8

15

27

32

4

69

46

36

57

2

8

15

4

32

27

36

46

69

57

1

8

4

15

27

32

36

46

57

69

4

8

92

90

76

99

21

31

31

13

2

8

92

99

76

90

31

31

21

13

1

8

99

92

90

76

31

31

21

13

4

15

27

32

36

46

57

69

99

92

90

76

31

31

21

13

# 自顶向下完成双调序列的排序

8

16

4

15

27

32

31

31

21

13

99

92

90

76

36

46

57

69

4

16

4

15

21

13

31

31

27

32

36

46

57

69

99

92

90

76

2

16

4

13

21

15

27

31

31

32

36

46

57

69

90

76

99

92

1

16

4

13

15

21

27

31

31

32

36

46

57

69

76

90

92

99

4

13

15

21

27

31

31

32

36

46

57

69

76

90

92

99

from

import

def

comp_and_swap

(array: List[int], index1: int, index2: int, direction: int)

None

if

1

and

or

0

and

def

bitonic_merge

(array: List[int], low: int, length: int, direction: int)

None

if

1

2

for

in

def

bitonic_sort

(array: List[int], low: int, length: int, direction: int)

None

if

1

2

1

0

if

"__main__"

"Enter numbers separated by a comma:\n"

for

in

","

0

1

"\nSorted array in ascending order is: "

""

", "

0

0

"Sorted array in descending order is: "

""

", "


原文链接

编译:朱科锦 来源:onezero 在数据保护和人工智能技术监管方面,欧盟一直走在立法实践的最前端。当地时间 4 月 21 日,欧盟委员会公布了名为 “Laying Down Harmonised Rules on Artificial Intelligence (Artificial Intelligence Act) And Amending Certain Union Legislative Acts” 的草案,对人工智能技术应用进行了风险评定。 根据这份草案,欧盟将全面禁止大规模监控和利用人工智能技术的社会信用体系,同时对特定领域的 “高风险” 应用进行严格限制。 2020 年 2 月 19 日,欧盟委员会曾发布了名为 “White Paper