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