假设我有一个数组k = [1 2 0 0 5 4 0]
我可以计算一个掩码如下m = k > 0 = [1 1 0 0 1 1 0]
只使用掩码m和以下操作
- 左/右Shift
- 和
- 加/减/乘
我可以把k压缩成下面的形式[1 2 5 4]
这是我目前如何做的(MATLAB伪代码):
function out = compact( in )
d = in
for i = 1:size(in, 2) %do (# of items in in) passes
m = d > 0
%shift left, pad w/ 0 on right
ml = [m(2:end) 0] % shift
dl = [d(2:end) 0] % shift
%if the data originally has a gap, fill it in w/ the
%left shifted one
use = (m == 0) & (ml == 1) %2 comparison
d = use .* dl + ~use .* d
%zero out elements that have been moved to the left
use_r = [0 use(1:end-1)]
d = d .* ~use_r
end
out = d(1 : size(find(in > 0), 2)) %truncate the end
end
每次迭代，我们向左移动掩码并比较掩码。如果我们发现在左移之后，一个原本无效的索引(mask[i] = 0)现在是有效的(mask[i] = 1)，我们将索引设置为包含左移的数据。
上述算法有O(N *(3移位+ 2比较+ AND + add + 3乘法))。有没有办法提高它的效率?
原始伪代码中没有太多需要优化的内容。我在这里看到了一些小的改进:
- 循环可以少执行一次迭代(即size-1)，
- 如果'use'为零，你可以提前打破循环，
-
use = (m == 0) & (ml == 1)可能简化为use = ~m & ml， - 如果将
~计算为单独操作，则最好使用颠倒形式:use = m | ~ml,d = ~use .* dl + use .* d,use_r = [1 use(1:end-1)],d = d .*use_r
但是有可能发明更好的算法。算法的选择取决于所使用的CPU资源:
- Load-Store Unit，即直接将算法应用于记忆字。在芯片制造商将高度并行的散射指令添加到他们的指令集中之前，这里什么也做不了。
- SSE寄存器，即在寄存器的整个16字节上工作的算法。像提议的伪代码这样的算法在这里没有帮助，因为我们已经有了各种各样的洗牌/排列指令，这些指令可以使工作更好。在PMOVMSKB中使用各种比较指令，将结果按4位分组，并在switch/case(如LastCoder所述)下应用各种shuffle指令是我们能做的最好的。具有最新指令集的
- SSE/AVX寄存器允许更好的方法。我们可以直接使用PMOVMSKB的结果，将其转换为PSHUFB之类的控制寄存器。
- 整数寄存器，即GPR寄存器或同时在SSE/AVX寄存器的多个DWORD/QWORD部分上工作(允许执行多个独立压缩)。应用于整数寄存器的伪代码允许压缩任何长度(从2位到20位)的二进制子集。这是我的算法，它可能会表现得更好。
c++， 64位，子集宽度= 8:
typedef unsigned long long ull;
const ull h = 0x8080808080808080;
const ull l = 0x0101010101010101;
const ull end = 0xffffffffffffffff;
// uncompacted bytes
ull x = 0x0100802300887700;
// set hi bit for zero bytes (see D.Knuth, volume 4)
ull m = h & ~(x | ((x|h) - l));
// bitmask for nonzero bytes
m = ~(m | (m - (m>>7)));
// tail zero bytes need no special treatment
m |= (m - 1);
while (m != end)
{
ull tailm = m ^ (m + 1); // bytes to be processed
ull tailx = x & tailm; // get the bytes
tailm |= (tailm << 8); // shift 1 byte at a time
m |= tailm; // all processed bytes are masked
x = (x ^ tailx) | (tailx << 8); // actual byte shift
}
所以您需要弄清楚对于这样一个简单的任务来说，额外的并行性，移动/洗牌开销是否值得。
for(int inIdx = 0, outIdx = 0; inIdx < inLength; inIdx++) {
if(mask[inIdx] == 1) {
out[outIdx] = in[inIdx];
outIdx++;
}
}
如果你想走并行SIMD路线，你最好的选择是一个SWITCH CASE，包含掩码的下4位的所有可能的排列。为什么不是8?因为PSHUFD指令只能在XMMX m128上shuffle，而不能在XMMX m256上shuffle。
所以你有16个案例:
- [1 1 1 1 1]，[1 1 1 1 0]，[1 1 0 0]，[1 0 0 0]，[0 0 0 0]不需要任何特殊的移位/shuffle，你只需要将输入复制到输出MOVDQU，并分别将输出指针增加4,3,2,1,0。
- [0 1 1]，[0 0 1 1]，[0 1 1]，[0 0 1 1]，[0 0 0 1]，[0 0 0 0]，[0 0 1 0]，你只需要使用PSRLx(右移逻辑)并分别增加输出指针3,2,2,1,1,1
- [1 0 0 1]，[1 0 1 0]，[0 1 0 1]，[1 0 1 1]，[1 0 1 1]，[1 1 0 1]你使用PSHUFD来打包你的输入，然后分别增加你的输出指针2,2,2,3,3。
所以每种情况都是最小的处理量(1到2个SIMD指令和1个输出指针添加)。case语句的周围循环将处理常量输入指针的加法(乘以4)和MOVDQA来加载输入。
原代码一次只移动数组元素一步。这是可以改进的。可以对数组元素进行分组并一次移动2^k步。
该算法的第一部分计算每个元素应该移动多少步。第二部分移动元素——首先移动一步，然后移动2步，然后移动4步，以此类推。这可以正常工作，并且元素不会混合，因为每次移动之后都有足够的空间来执行2倍大的移动。
Matlab，未测试代码:
function out = compact( in )
m = in <= 0
for i = 1:size(in, 2)-1
m = [0 m(1:end-1)]
s = s + m
end
d = in
shift = 1
for j = 1:ceil(log2(size(in, 2)))
s1 = rem(s, 2)
s = (s - s1) / 2
d = (d .* ~s1) + ([d(1+shift:end) zeros(1,shift)] .* [s1(1+shift:end) zeros(1,shift)])
shift = shift*2
end
out = d
end
上述算法的复杂度为O(N * (1 shift + 1 add) + log(N) * (1 rem + 2 add + 3 mul + 2 shift))
阅读原始问题下面的评论，在实际问题中，数组包含32位浮点数，而掩码是(一个?)32位整数，所以我不明白为什么要使用移位等来压缩数组。简单的压缩算法(在C中)是这样的:
float array[8];
unsigned int mask = ...;
int a = 0, b = 0;
while (mask) {
if (mask & 1) { array[a++] = array[b]; }
b++;
mask >>= 1;
}
/* Size of compacted array is 'a' */
/* Optionally clear the rest: */
while (a < 8) array[a++] = 0.0;
较小的变化可能是由于掩码的位顺序，但唯一需要的ALU操作是索引变量更新和移位以及对掩码进行andding。因为原始数组至少有256位宽，所以没有普通的CPU可以按位移动整个数组。
假设您希望在c++中以最少的步骤存储数组中的正整数，下面是示例代码:
int j = 0;
int arraysize = (sizeof k)/4;
int store[arraysize];
for(int i = 0; i<arraysize; i++)
{
if(k[i] > 0)
{
store[j] = k[i];
j++;
}
}
如果不想使用for循环，也可以直接使用k[]的元素