更快的strlen？

Question

strlen()从第一个字符到它找到的典型遍历\0.这要求您遍历每个角色.在算法意义上,它的O(N).

有没有更快的方法来做这个模糊定义的输入.例如:长度小于50,或长度大约200个字符.

我想到了查找块,但没有得到任何优化.

Answer 1

当然.在写入字符串时跟踪长度.

Answer 2

事实上,glibc的公司实施的strlen是量化方法的一个有趣的例子.它的特殊之处在于它不使用向量指令,而是找到一种方法,只使用来自缓冲区的32或64位字的普通指令.

Answer 3

显然,如果您的字符串具有已知的最小长度,则可以在该位置开始搜索.

除此之外,你无能为力; 如果你尝试做一些聪明的事情并找到一个\0字节,你仍然需要检查字符串的开头和那个点之间的每个字节,以确保没有更早的字节\0.

这并不是说strlen无法优化.它可以是流水线的,并且可以通过每次比较来处理字大小或矢量块.在大多数体系结构中,这些和其他方法的某种组合将在天真的字节比较循环中产生实质的恒定因子加速.当然,在大多数成熟的平台上,系统strlen已经使用这些技术实现.

Answer 4

简短的回答:没有.

更长的答案:您是否真的认为如果有更快的方法来检查准系统C字符串的字符串长度,那么常用的C字符串库就不会包含它？

如果没有关于字符串的某些额外知识,您必须检查每个字符.如果您愿意维护这些附加信息,您可以创建一个struct将长度存储为结构中的字段(除了字符串的实际字符数组/指针),在这种情况下,您可以进行长度查找恒定时间,但每次修改字符串时都必须更新该字段.

Answer 5

杰克，

strlen通过查找结尾的“\0”来工作，下面是来自 OpenBSD 的实现：

size_t
strlen(const char *str)
{
        const char *s;

        for (s = str; *s; ++s)
                ;
        return (s - str);
}

现在，正如您所说，您知道长度约为 200 个字符。假设您从 200 开始并上下循环“\0”。你找到了一个204，这是什么意思？该字符串有 204 个字符长？不！它可能会在此之前以另一个“\0”结束，而您所做的只是查看越界。