删除长度为N的字符串中每个第k个字符的最佳算法是什么？

Question

我知道有一个天真的算法是N阶,我确信这是唯一使用的算法.还有其他的:

1. 渐渐变好了
2. 可管道即RAW,WAR友好
3. Multithreadable.

我确定(1)有一个,但我对(2)和(3)不太确定.如果你还想提一下为什么这是一个很好的面试问题.我也很想知道这一点.

Answer 1

显而易见的方法很容易就地完成

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不是字符指针循环，以使这一点更加明显，并且对于中型到大型的性能更好k。对于小型 来说，它可能很糟糕k。）

对于就地多线程来说，如果k很大，就会有所收获，因此即使在长字符串的末尾，大部分复制的源和目标也位于同一块内。各工作单位做到：

• 不要触及第一个offset = chunk_number * chunk_size / k字节，前一个工作单元需要读取它们。
• 将第二个offset字节保存到临时数组中。
• memmove(chunk + offset, chunk + offset*2, chunk_size - offset)（即对前一个工作单元不需要的所有字节进行memmove）。
• 自旋等待前一个块被处理它的线程标记为已完成。（问题是使用单独的数据结构，因为仅查看最后一个重叠位置的数据是行不通的。它可能会被相同的值覆盖。）
• 从临时缓冲区复制到数据所属的块的开头
• 将工作块标记为已完成。

对于小型k，就地多线程是徒劳的，因为块中的大多数字节需要被后面块中的字节覆盖。（非常大的块会有所帮助。）