假设我有一个数组k = [1 2 0 0 5 4 0]
我可以按如下方式计算掩码m = k > 0 = [1 1 0 0 1 1 0]
仅使用掩码 m 和以下操作
- 左移/右移
- And/Or
- 加/减/乘
我可以将 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),则我们将索引设置为具有左移数据。
Question
上述算法的复杂度为 O(N * (3 次移位 + 2 次比较 + AND + 加法 + 3 次乘法))。有没有办法提高其效率?
原始伪代码没有太多需要优化的地方。我在这里看到了一些小改进:
- 循环可以少执行一次迭代(即 size-1),
- 如果“use”为零,您可能会提前打破循环,
-
use = (m == 0) & (ml == 1)
可能可以简化为use = ~m & ml
,
- if
~
被算作单独的操作,最好使用倒置形式:use = m | ~ml
, d = ~use .* dl + use .* d
, use_r = [1 use(1:end-1)]
, d = d .*use_r
但发明更好的算法是可能的。算法的选择取决于所使用的CPU资源:
- 加载-存储单元,即将算法直接应用于内存字。在芯片制造商将高度并行的 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
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)