algorithm - 优化数组压缩

Question

假设我有一个数组 k = [1 2 0 0 5 4 0]

我可以按如下方式计算掩码 m = k > 0 = [1 1 0 0 1 1 0]

只使用mask m和下面的操作

1. 左移/右移
2. 和/或
3. 加/减/乘

我可以将 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

直觉

每次迭代，我们将掩码左移并比较掩码。如果我们发现在这个移位之后，一个原本为 void(mask[i] = 0) 的索引现在有效(mask[i] = 1)，那么我们设置一个索引让数据左移。

问题

上述算法复杂度为 O(N * (3 shift + 2 comparison + AND + add + 3 multiplys))。有没有办法提高它的效率？

Answer 1

原始伪代码中没有太多需要优化的地方。我在这里看到了几个小改进:

• loop 可以少执行一次迭代(即 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，即将算法直接应用于内存字。在芯片制造商将高度并行的 SCATTER 指令添加到他们的指令集中之前，这里什么也做不了。
• SSE 寄存器，即在整个 16 个字节的寄存器上工作的算法。像提议的伪代码这样的算法在这里无济于事，因为我们已经有了各种可以使工作更好的随机/排列指令。将各种比较指令与 PMOVMSKB 结合使用，将结果按 4 位分组并在 switch/case 下应用各种混洗指令(如 LastCoder 所述)是我们能做的最好的事情。
• 带有最新指令集的 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
}