点击
机器学习算
法与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