我知道有一个简单的算法是n阶的,我相信这是唯一可以使用的算法。还有其他的吗:
渐近较好
可管道化,即未加工、战争友好型
多线程。
我肯定有一个是给(1)的,但我对(2)和(3)不太确定。如果你还想提到为什么这是一个好的面试问题。我也想知道。

最佳答案

显而易见的方法很容易做到

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)。
旋转等待处理前一个块的线程将其标记为已完成。(PROB)使用单独的数据结构,因为仅仅观察最后一个重叠位置的数据是行不通的。它可能会被相同的值覆盖。)
从临时缓冲区复制到数据所属的块的开头
将工作块标记为已完成。
对于smallmemmove(chunk + offset, chunk + offset*2, chunk_size - offset),就地多线程是徒劳的,因为块中的大多数字节需要用后面块中的字节覆盖。(大块头对某些人有帮助。)

07-24 09:44
查看更多