相关疑难解决方法(0)

好吧,所以我听起来不像白痴我会更明确地陈述问题/要求:

• 针(模式)和haystack(要搜索的文本)都是C样式的以空字符结尾的字符串.没有提供长度信息; 如果需要,必须计算.
• 函数应该返回指向第一个匹配的指针,或者NULL如果找不到匹配项.
• 不允许发生失败案件.这意味着任何具有非常量(或大常量)存储要求的算法都需要具有分配失败的后备情况(并且后备保养中的性能因此导致最坏情况的性能).
• 实现是在C中,虽然没有代码的算法(或链接到这样的)的良好描述也很好.

......以及"最快"的意思:

• 确定性O(n)where n= haystack长度.(但是O(nm)如果它们与更强大的算法组合以给出确定性O(n)结果,则可以使用通常(例如滚动哈希)算法的思想.
• 从不执行(可测量;一些时钟if (!needle[1])等等)比天真蛮力算法更糟糕,特别是在非常短的针上,这可能是最常见的情况.(无条件的重预处理开销是不好的,因为试图以可能的针头为代价来改善病理针的线性系数.)
• 给定任意针和干草堆,与任何其他广泛实现的算法相比,具有相当或更好的性能(不低于搜索时间长50%).
• 除了这些条件,我将保留"最快"开放式的定义.一个好的答案应该解释为什么你认为你建议"最快"的方法.

我目前的实现比glibc实现的双向大约慢10%和8倍(取决于输入).

更新:我目前的最佳算法如下:

• 对于长度为1的针,请使用strchr.
• 对于长度为2-4的针,使用机器字一次比较2-4个字节,如下所示:在每次迭代时从大海捞针以16位或32位整数预加载针,并从大海捞针中循环旧字节输出/新字节.大海捞针的每个字节都只读取一次,并对0(字符串结束)和一个16位或32位比较进行检查.
• 对于长度> 4的针,使用具有错误移位表的双向算法(如Boyer-Moore),该移位表仅应用于窗口的最后一个字节.为了避免初始化1kb表的开销,这对于许多中等长度的针来说是一个净损失,我保留一个位数组(32字节)标记移位表中的哪些条目被初始化.未设置的位对应于从不出现在针中的字节值,可以进行全针长度移位.

我脑海中留下的重大问题是:

• 有没有办法更好地利用坏班次表？Boyer-Moore通过向后扫描(从右到左)充分利用它,但是双向扫描需要从左到右扫描.
• 我在一般情况下找到的唯一两个可行的候选算法(没有内存或二次性能条件)是有序字母表上的双向和字符串匹配.但是,是否存在易于检测的情况,其中不同的算法将是最佳的？当然,空间算法中的许多O(m)(其中m是针长)可以用于m<100左右.如果针对针的简单测试可能仅需要线性时间,那么也可以使用最坏情况二次方的算法.

奖励积分:

• 假设针和干草堆都是结构良好的UTF-8,你能提高性能吗？(对于字节长度不同的字符,良好的形式在针和haystack之间强加了一些字符串对齐要求,并且当遇到不匹配的头字节时允许自动2-4字节移位.但这些约束是否会超出你的范围最大后缀计算,良好的后缀转换等已经为您提供了各种算法？)

注意:我很清楚那里的大多数算法,而不是它们在实践中的表现.这是一个很好的参考,所以人们不会继续给我作为评论/答案的算法参考:http://www-igm.univ-mlv.fr/~lecroq/string/index.html

背景: 我正在尝试创建一个纯D语言实现的功能,大致相当于C的memchr,但使用数组和索引而不是指针.原因是std.string将用于编译时功能评估.对于那些不熟悉w/D的人,如果满足某些限制,可以在编译时评估函数.一个限制是它们不能使用指针.另一个是他们不能调用C函数或使用内联汇编语言.使字符串库在编译时工作对于某些编译时代码生成很有用.

问题: memchr如何在引擎盖下工作以尽可能快地执行？在Win32上,我使用简单循环在纯D中创建的任何东西,即使有明显的优化技术,例如禁用边界检查,循环展开等,也至少要慢2倍.有哪些非显而易见的技巧可用于像在字符串中查找字符一样简单？