在时间 log(n) 中移动数组中的元素
Move element in array in time log(n)
我有两个数组 name[i] 和 signal[i] ，大小都是 n。
Tom Tim Kate Jim
0 1 1 0
其中名称以某种顺序存储在数组名称中，每个名称具有 0 或 1 个值。
我想将所有值为 0 的名称移到数组的左侧，而将值为 1 的名称移到右侧，并且顺序不变。因此结果看起来像
Tom Jim Tim Kate
0 0 1 1
关键是如何在时间log(n)中用nCPU实现？
那是不可能的，只是弄清楚哪些是零，哪些是一将花费 O(n) 时间，因为您必须逐一查看。
有了 n 个核心，你可以让每个核心看一个不同的元素，然后他们看他们的邻居，左边的接受所有有零的，奇数接受有一个的。偶数索引核心与其偶数索引邻居重复此操作，依此类推...
在这些操作的 O(log n) 之后，最左边的核心将拥有所有带零的项目，最右边的将拥有所有带一的项目。
也许你可以根据信号值把名字分成两个大小为n的数组。然后使用类似于 "Parallel Reduction" 的算法将您的名字收集到每个数组中，然后将两个数组合并为一个。
每个线程读取与其线程号关联的名称。如果名称的信号是 0，则在 name_0[thread_id] 中添加名称，信号等于 1 时类似。所以你有 2 个有序数组，第一个是所有信号 0，第二个是第二个所有信号 1。所以你 "just" 必须折叠这两个数组（激发你 "Parallel Reduction algorithm" ？）。
这是我见过最simple/parallel-processing的算法。
我有两个数组 name[i] 和 signal[i] ，大小都是 n。
Tom Tim Kate Jim
0 1 1 0
其中名称以某种顺序存储在数组名称中，每个名称具有 0 或 1 个值。
我想将所有值为 0 的名称移到数组的左侧，而将值为 1 的名称移到右侧，并且顺序不变。因此结果看起来像
Tom Jim Tim Kate
0 0 1 1
关键是如何在时间log(n)中用nCPU实现？
那是不可能的，只是弄清楚哪些是零，哪些是一将花费 O(n) 时间，因为您必须逐一查看。
有了 n 个核心，你可以让每个核心看一个不同的元素，然后他们看他们的邻居，左边的接受所有有零的，奇数接受有一个的。偶数索引核心与其偶数索引邻居重复此操作，依此类推...
在这些操作的 O(log n) 之后，最左边的核心将拥有所有带零的项目，最右边的将拥有所有带一的项目。
也许你可以根据信号值把名字分成两个大小为n的数组。然后使用类似于 "Parallel Reduction" 的算法将您的名字收集到每个数组中，然后将两个数组合并为一个。
每个线程读取与其线程号关联的名称。如果名称的信号是 0，则在 name_0[thread_id] 中添加名称，信号等于 1 时类似。所以你有 2 个有序数组，第一个是所有信号 0，第二个是第二个所有信号 1。所以你 "just" 必须折叠这两个数组（激发你 "Parallel Reduction algorithm" ？）。
这是我见过最simple/parallel-processing的算法。