我知道有一个朴素的算法,时间复杂度是N,我相信这是唯一应该使用的。是否还有其他算法满足以下条件:
- 渐进性更好
- 可用于流水线处理,即RAW、WAR友好
- 可多线程处理。
void remove_every_kth(char *s, size_t len, int k)
{
// UNTESTED CODE, there might be an off-by-one or a wrong loop boundary
if (k < len)
return;
const char *endp = s + len;
size_t offset = 1;
// we skip the s[i] = s[i] memmove at offset=0.
for (s+=k-1 ; s + offset < endp-(k-1) ; s+=k-1) {
// every iteration copies k-1 characters, and advances s by k-1
memmove(s, s+offset, k-1);
offset++;
}
size_t lastchunk = endp - (s+offset); // some number (less than k) of bytes left in the input
memmove(s, s+offset, lastchunk);
s[lastchunk] = '\0';
}
// equivalently, we could have kept a pointer to the read position,
// like const char* read = s+offset;
// and incremented it by k, while incrementing s by k-1
// for (int i=0 ; i < k ; i++) // implicit length string
// if (!s[i]) return; // check for length < k
k
是常量,因此您可以计算出任何输出位置的输入字符的位置。out[i] = in[i + i/k]
。这里没有数据依赖性,因此如果您不需要就地执行,并且已经提前知道字符串的长度,则肯定可以进行多线程处理。只需将必要的memcpy
调用分配给多个线程即可。 (我使用了memmove
而不是char指针循环编写了简单版本,以使其更加明显,并且在中等到大的k
下具有更好的性能。对于小的k
可能不太好。)k
很大,则可以获得一些收益,以便即使在长字符串的末尾,大部分复制的源和目标仍在同一块内。每个工作单元都执行以下操作:
offset = chunk_number * chunk_size / k
字节,前一个工作单元需要读取它们。offset
字节保存到临时数组中。memmove(chunk + offset, chunk + offset*2, chunk_size - offset)
(即对所有前一个工作单元不需要的字节执行memmove)。对于小的k
,原地多线程是徒劳的,因为大多数块中的字节都需要用后面块中的字节进行覆盖。(非常大的块有所帮助。)
O(log k)
。但是,由于指针遍历和树的一般缓存不友好性,常数因子将会更加糟糕(远远糟糕)。 - The Paramagnetic Croissantk - 1
个字符外,所有其他字符都必须移动到新位置。这是o(N - (k - 1))
=o(N)
(小写字母 o),因此上限不能更好。由于您确实可以在O(N)
操作中完成该作业,因此这是您最佳的可能上限。 - John Bollinger