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

Question

我知道有一种简单的 N 阶算法，我几乎确信这是唯一可以使用的算法。还有没有其他的是:

1. 渐近更好
2. 可管道化，即 RAW，WAR 友好
3. 多线程。

我确定 (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 而不是 char-pointer 循环编写了简单版本，以使其更加明显，并且在中型到大型 k 中获得更好的性能。它可能对于小的 k 很糟糕。)

对于就地多线程，如果 k 很大，那么即使在长字符串的末尾，大部分复制的源和目标都在同一个 block 中.每个工作单元做:

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

对于小的k，就地多线程是徒劳的，因为 block 中的大部分字节需要被后面 block 中的字节覆盖。 (非常大的 block 可以帮助一些。)