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

Question

我知道有一个朴素的算法，时间复杂度是N，我相信这是唯一应该使用的。是否还有其他算法满足以下条件：

1. 渐进性更好
2. 可用于流水线处理，即RAW、WAR友好
3. 可多线程处理。

对于（1）我相信有这样的算法，但对于（2）和（3），我不太确定是否存在。如果您想解释为什么这是一个好的面试问题，也可以提出来。

- West

---

如果您使用二叉搜索树来存储单个字符，其中节点的排序/顺序基于字符的索引，则可以渐进地降至O(log k)。但是，由于指针遍历和树的一般缓存不友好性，常数因子将会更加糟糕（远远糟糕）。 - The Paramagnetic Croissant

因为最好的面试问题没有明确的答案，而是像你所提出的那样，引导你探索不同的选择。 - Weather Vane

应该返回什么？这个问题是在询问返回第k个字符，还是返回删除了第k个字符的字符串？ - Jonathan M

这个字符串是否要表示为字符数组？我认为面试官可能希望被问到这种问题，以便开始讨论其他表示字符串/字符串集合的方式。 - user1952500

相对简单的看待渐进复杂度问题的方法是，无论你如何进行删除操作的细节，除了 k - 1 个字符外，所有其他字符都必须移动到新位置。这是 o(N - (k - 1)) = o(N)（小写字母 o），因此上限不能更好。由于您确实可以在 O(N) 操作中完成该作业，因此这是您最佳的可能上限。 - John Bollinger

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指针循环编写了简单版本，以使其更加明显，并且在中等到大的k下具有更好的性能。对于小的k可能不太好。）

对于多线程就地处理，如果k很大，则可以获得一些收益，以便即使在长字符串的末尾，大部分复制的源和目标仍在同一块内。每个工作单元都执行以下操作：

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

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

- Peter Cordes