什么是最快的子字符串搜索算法？

Question

好的，为了不让自己听起来像个白痴，我会更明确地陈述问题/要求：

• 需要在C风格的空终止字符串中查找针（模式）和干草堆（文本）。未提供长度信息；如果需要，必须计算。
• 函数应返回第一个匹配项的指针，如果未找到匹配项，则返回NULL。
• 不允许失败情况。这意味着任何具有非常量（或大常量）存储要求的算法都需要具有分配失败的回退情况（并且回退情况的性能有助于最坏情况的性能）。
• 实现应使用C语言，但仅有算法的良好描述（或链接）而无代码也可以。

...以及我所说的“最快”是什么意思：

• 确定性的 O(n)，其中 n 是指 haystack 的长度。（但是如果将其与更健壮的算法结合起来，可以使用通常为 O(nm) 的算法（例如滚动哈希）中的思想，以获得确定性的 O(n) 结果。）
• 从未表现出比朴素的暴力算法更差的性能（可测量的；if (!needle[1]) 等需要一些计时器是可以接受的），特别是在非常短的 needle 上，这可能是最常见的情况。（无条件的重度预处理开销不好，试图通过牺牲常规 needle 的代价来改善病态 needle 的线性系数也不好。）
• 对于任意给定的 needle 和 haystack，在搜索时间上与任何其他广泛实现的算法相比具有可比或更好的性能（搜索时间不超过其他算法的50%）。
• 除了这些条件外，我将“最快”的定义留给开放式的。一个好的答案应该解释为什么你认为你提出的方法是“最快”的。

我的当前实现大约比 glibc 的 Two-Way 实现慢10％到8倍（取决于输入）。

更新：我的当前最佳算法如下：

• 对于长度为1的针，使用strchr。
• 对于长度为2-4的针，使用机器字来一次比较2-4个字节，方法如下：用位移将针预加载到16或32位整数中，并在每次迭代中从干草堆中循环旧字节/新字节。每个干草堆的字节都被读取一次，并产生与0（字符串结尾）和一个16或32位比较的检查。
• 对于长度大于4的针，使用具有坏移位表的双向算法（例如Boyer-Moore），该算法仅应用于窗口的最后一个字节。为避免初始化1kb表的开销，这将是许多中等长度针的净损失，我保留了一个位数组（32字节），标记哪些条目在移位表中已初始化。未设置的位对应于永远不出现在针中的字节值，可以进行完整的针长移位。

我心中的重要问题是：

• 有没有办法更好地利用坏的移位表？Boyer-Moore通过向后扫描（从右到左）最好地利用它，但Two-Way需要从左到右扫描。
• 我找到的唯一两个适用于一般情况（没有内存不足或二次性能条件）的可行算法是Two-Way和String Matching on Ordered Alphabets。但是否存在易于检测的情况，其中不同的算法将是最优的？当然，对于m<100左右，许多O(m)（其中m是针长度）的空间算法都可以使用。如果有一个仅需要线性时间的简单测试针的算法，则还可以使用最坏情况二次的算法。

额外加分项：

• 如果假定针和草堆都是格式良好的UTF-8，您是否可以通过这种方式提高性能？（由于具有不同字节长度的字符，格式良好性在针和草堆之间强加了一些字符串对齐要求，并在遇到不匹配的头字节时允许自动的2-4字节移位。但是，除了各种算法已经给出的最大后缀计算、好后缀移位等之外，这些约束是否会给您带来更多/任何好处？）

注意：我对大多数算法都很熟悉，只是不知道它们在实践中表现如何。这里有一个很好的参考资料，以便别人不再给我关于算法的评论/答案: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

- R.. GitHub STOP HELPING ICE

---

在字符串算法页面上列出了相当多的字符串搜索算法。您可能希望描述一下您从这个列表中考虑过哪些算法。 - Greg Hewgill

结尾处的链接非常有价值！ - Carlos

我无法相信你仍然没有接受一个答案。 - user541686

@Mehrdad：我本来想说没有答案真正回答了问题，但你的似乎可以。在你回答的时候，我已经转而离开了进一步改进strstr的事情，所以我实际上还没有好好阅读你链接的论文，但它听起来非常有前途。谢谢你，很抱歉没有及时回复你。 - R.. GitHub STOP HELPING ICE

Answer 1

建立一个测试库，包含可能的关键词和待搜索的文本。使用多种搜索算法（包括暴力搜索）对这些测试进行分析，选择在您的数据上表现最佳的算法。Boyer-Moore使用坏字符表和好后缀表。Boyer-Moore-Horspool使用坏字符表。Knuth-Morris-Pratt使用部分匹配表。Rabin-Karp使用运行哈希。它们都以不同程度的开销换取减少比较操作，因此实际性能取决于关键字和待搜索文本的平均长度。初始开销越大，适合处理更长的输入。对于非常短的关键字，暴力搜索可能会更快。编辑：寻找碱基对、英语短语或单词可能需要不同的算法。如果有一种适用于所有输入的最佳算法，那么就会公开发表。考虑下面的小表格。每个问号可能都需要使用不同的最佳搜索算法。

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

这应该是一个图表，每条轴上应有不同长度的输入范围。如果在这样的图表上绘制每个算法，它们会有不同的特征。某些算法在模式中有大量重复时可能会受到影响，这可能会影响搜索基因等用途。其他影响整体性能的因素包括多次搜索相同模式以及同时搜索不同模式。

如果我需要一个样本集，我想我会爬取像Google或维基百科这样的网站，然后从所有结果页面中剥离HTML。对于搜索网站，输入一个单词，然后使用建议的搜索短语之一。选择几种不同的语言（如果适用）。使用网页，所有文本都将较短至中等长度，因此合并足够的页面以获得更长的文本。您还可以找到公共领域的书籍、法律记录和其他大量文本。或者只需从字典中挑选单词来生成随机内容。但是，分析的目的是根据您将要搜索的内容进行测试，因此尽可能使用真实世界的样本。

关于“短”和“长”的定义比较含糊。对于“针”，我认为小于8个字符为短，小于64个字符为中等，小于1k为长。对于“干草堆”，我认为小于2 ^ 10个字符为短，小于2 ^ 20个字符为中等，长达2 ^ 30个字符。

- drawnonward

---

你有好的测试库建议吗？我之前在SO上问过这个问题，但从未得到真正的答案。（除了我的...）它应该是全面的。即使我的strstr应用程序的想法是搜索英文文本，其他人的想法可能是在碱基序列中搜索基因... - R.. GitHub STOP HELPING ICE

这比短/长要复杂一些。对于针（即模式字符串），大多数算法的性能与以下问题相关：长度？是否有周期性？针内是否包含所有唯一字符（不重复）？或者全部是相同字符？干草堆中有大量字符从未出现在针中吗？是否有可能需要处理由攻击者提供的针，以利用最坏情况性能来瘫痪您的系统？等等。 - R.. GitHub STOP HELPING ICE

这个库和测试代码是与smart一起存在的，你列出的旧算法都表现不佳。Leroy的论文也太老了。BM、KMP、BMH、KP有大约80个改进。目前（截至2020年）在所有情况下最好的是EPSM。 - rurban

Answer 2

2011年发布的一篇论文，我认为这很可能是Dany Breslauer、Roberto Grossi和Filippo Mignosi提出的"Simple Real-Time Constant-Space String Matching"算法。

更新：

2014年，作者发表了这篇改进论文：Towards optimal packed string matching。

- user541686

---

哇，谢谢。我正在阅读这篇论文。如果它比我现在拥有的更好，我一定会接受你的答案。 - R.. GitHub STOP HELPING ICE

@R..：当然！ :) 顺便说一下，如果您成功实现了该算法，请考虑在 StackOverflow 上发布它，这样每个人都可以受益！我在任何地方都没有找到它的实现，而且我不擅长实现研究论文中的算法哈哈。 - user541686

这是我已经在使用的“双向”算法的一个变体，因此调整我的代码以使用这个可能实际上很容易。不过，我需要更详细地阅读论文才能确定，并且我需要评估所做的更改是否与我使用的“坏字符表”兼容，该表极大地加快了常见情况的速度。 - R.. GitHub STOP HELPING ICE

你还没有接受@Mehrdad的答案！:-) - lifebalance

公平地说，这确实是一个仅有链接的回答，在这里是不允许的。 - Dawood ibn Kareem

@DavidWallace: 什么？它有论文标题和作者。即使链接失效，你也可以找到这些论文。你希望我做什么？为这个算法写伪代码吗？你为什么认为我懂这个算法呢？ - user541686

Answer 3

看到我们的技术报告被引用在这个讨论中，我感到惊讶；我是被称为Sustik-Moore算法的作者之一。（我们在论文中没有使用这个术语。）

我在这里想强调的是，对我来说，该算法最有趣的特点是可以很容易地证明每个字母最多只检查一次。对于早期的Boyer-Moore版本，他们证明每个字母最多只检查3次或者2次，并且这些证明更加复杂（参见论文中的引用）。因此，我认为这个变体的呈现和研究也具有教学价值。

在论文中，我们还描述了更多的变化，旨在提高效率，同时放宽理论保证。在我看来，这篇论文应该对一个普通的高中毕业生来说是可理解的。

我们的主要目标是将这个版本带到其他人的注意下，以便他们进一步改进它。字符串搜索有很多变化，我们无法想象所有这个想法可能带来好处的地方。（固定文本和不同的模式，固定模式不同的文本，预处理可能/不可能，并行执行，在大型文本中查找匹配的子集，允许错误，近似匹配等等。）

- Matyas

---

你是否知道是否有可用的C或C++实现？我正在考虑将其用于一些DNA模体搜索（精确模体匹配）。如果没有，也许我会尝试开发一个实现并提交给boost算法。 - JDiMatteo

由于没有已知的可用实现，Sustik-Moore/2BLOCK算法似乎不太可能在实践中得到应用，并且会继续被省略在总结性论文如《Exact String Matching Problem: a Comprehensive Experimental Evaluation》(http://arxiv.org/pdf/1012.2547v1.pdf)的结果中。 - JDiMatteo

Answer 4

你指向的http://www-igm.univ-mlv.fr/~lecroq/string/index.html链接是一些最好的已知和研究过的字符串匹配算法的优秀来源和摘要。

解决大多数搜索问题涉及到与预处理开销、时间和空间需求方面的权衡。没有单一算法在所有情况下都是最优或实用的。

如果你的目标是设计一个特定的字符串搜索算法，那么请忽略我接下来要说的内容，如果你想开发一个通用的字符串搜索服务程序，则可以尝试以下方法：

花些时间回顾你已经引用的算法的具体优点和缺点。以找到一组覆盖你感兴趣的字符串搜索范围和范围的算法为目标进行审查。然后，基于分类器函数构建一个前端搜索选择器，以针对特定输入目标最佳算法。这样你就可以使用最有效的算法完成工作。当算法非常适用于某些搜索但效果较差时，这种方法特别有效。例如，暴力搜索可能是长度为1的针的最佳选择，但随着针的长度增加，它很快就会退化，此时sustik-moore算法可能更有效（对于小字母表），然后对于更长的针和更大的字母表，KMP或Boyer-Moore算法可能更好。这只是举例说明一种可能的策略。

多算法方法并不是一个新的想法。我相信一些商业排序/搜索软件（例如，在大型机上广泛使用的SYNCSORT实现了几种排序算法，并使用启发式方法选择给定输入的“最佳”算法）已经采用了这种方法。

每种搜索算法都有几个变体，可以对其性能产生重大影响，正如这篇论文所说明的那样。

基准测试您的服务，以确定需要额外的搜索策略或更有效地调整选择器函数的区域。这种方法不快也不容易，但如果做得好，可以产生非常好的结果。

- NealB

---

谢谢您的回复，特别是提供了我之前没有见过的Sustik-Moore链接。多算法方法肯定被广泛使用。Glibc基本上是使用strchr，Two-Way（不带坏字符移位表）或Two-Way（带有坏字符移位表），具体取决于needle_len是否为1，<32或>32。我的当前方法与此相同，只是我始终使用移位表；我用一个位集的32字节memset替换了必须进行的1kb memset，以标记已初始化哪些表元素，并获得了好处（但没有开销），即使是小针头也是如此。 - R.. GitHub STOP HELPING ICE

经过思考，我真的很好奇Sustik-Moore的预期应用是什么。使用小字母，您永远无法进行任何重大的移位（字母表的所有字符几乎肯定出现在针尖附近），有限自动机方法非常有效（小状态转换表）。因此，我无法想象任何情况下Sustik-Moore可能是最佳选择... - R.. GitHub STOP HELPING ICE

非常好的回答 -- 如果我能给这个特别的答案打星，我一定会。 - Jason S

@R.. Sustik-Moore算法背后的理论是，当字母表相对较小（例如搜索DNA序列）且针相对较大时，它应该给您更大的平均移位量。在这种情况下，“更大”仅意味着比基本的Boyer-Moore算法在相同输入情况下产生的移位量更大。相对于有限自动机方法或其他Boyer-Moore变体（其中有许多），这种效率提高了多少很难说。这就是为什么我强调要花些时间研究候选算法的具体优势/劣势的原因。 - NealB

嗯，我想我一直在考虑Boyer-Moore中的坏字符移位。然而，在BM好后缀移位的改进下，Sustik-Moore可能会超越DFA方法在DNA搜索中的表现。真是个不错的东西。 - R.. GitHub STOP HELPING ICE

Answer 5

最快的子字符串搜索算法将取决于以下方面：

1. 字母表大小（例如DNA与英语）
2. 针长度

2010年发表的论文“精确字符串匹配问题：综合实验评估”提供了51种算法（具有不同的字母表大小和针长度）的运行时间表，因此您可以选择最适合您环境的最佳算法。

所有这些算法都有C语言实现以及测试套件，在此处可找到：

http://www.dmi.unict.it/~faro/smart/algorithms.php

- JDiMatteo

---

不，2010年的论文没有提到最新和最好的算法，即“Exact Packed String Matching”（epsm）。在所有情况下，epsm都是最佳选择。 faro的新网站目前出现了故障，在互联网档案馆中可以查看它。 - rurban

@rurban：2010年的论文错过了2013年的论文？ - user541686

@user541686：没错。最新和最好的还未被发现。OP提到了那篇旧论文，它没有涵盖最新和最好的内容。 - rurban

Answer 6

更快的“查找单个匹配字符”算法（类似于strchr）。

重要说明：

- 这些函数使用“前导/尾随零的数量/计数”gcc编译器内置函数__builtin_ctz。这些函数只有在具有执行此操作的指令（即x86、ppc、arm等）的机器上才可能快速。 - 这些函数假定目标架构可以执行32位和64位未对齐的加载。如果目标架构不支持此操作，则需要添加一些启动逻辑以正确对齐读取。 - 这些函数与处理器无关。如果目标CPU具有矢量指令，您可能会获得更好的性能。例如，下面的strlen函数使用SSE3，并且可以轻松修改为异或扫描的字节以查找除0之外的字节。在运行Mac OS X 10.6（x86_64）的2.66GHz Core 2笔记本电脑上进行基准测试：

• strchr：843.433 MB/s
• findFirstByte64：2656.742 MB/s
• strlen：13094.479 MB/s

... 32位版本：

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

...以及一个64位版本：

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

编辑于2011/06/04，评论中的OP指出此解决方案存在一个“无法克服的错误”：

它可以读取所寻找的字节或空终止符之后的内容，这可能会访问未映射页面或没有读取权限的页面。除非对齐，否则在字符串函数中不能使用大型读取。

从技术上讲，这是正确的，但适用于几乎任何操作大于单个字节的块的算法，包括评论中OP建议的方法：

典型的strchr实现并不是天真的，而是比你提供的要高效得多。请参见本文最后部分，了解最广泛使用的算法：http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

这与对齐实际上没有什么关系。确实，在使用的大多数常见架构上，这可能会导致讨论的行为，但这更多地涉及微体系结构实现细节-如果不对齐的读取跨越4K边界（同样是典型的），那么如果下一个4K页面边界未映射，则该读取将导致程序终止错误。

但这不是答案中给出的算法中的“错误”-因为像strchr和strlen这样的函数不接受length参数来限制搜索的大小。使用strchr(bytes, 0xAA)（其中strchr是逐字节实现）搜索char bytes[1] = {0x55};，它恰好位于4K VM页面边界的末尾，并且下一页未映射，将以完全相同的方式崩溃。对于strchr相关的表亲strlen也是如此。

没有length参数，就无法告诉您何时应该从高速算法切换回逐字节算法。更可能的“错误”是读取“超过分配的大小”，从技术上讲，这会导致根据各种C语言标准的未定义行为，并且类似于valgrind的东西会将其标记为错误。

总之，任何操作大于字节块以加快速度的东西（如本答案代码和OP指出的代码），但必须具有字节精确读取语义，如果没有length参数来控制“最后一次读取”的角落情况，则很可能会出现“错误”。

这个答案中的代码是一个内核，可以快速地找到自然CPU字大小块中的第一个字节，如果目标CPU有快速的ctz指令。很容易添加一些东西，比如确保它只在正确对齐的自然边界上操作，或者某种形式的length限制，这将允许您从高速内核切换到较慢的逐字节检查。

OP在评论中也提到：

针对你的ctz优化，它只对O(1)尾部操作有影响。它可能会提高小字符串（例如strchr("abc", 'a');）的性能，但肯定不会对任何大型字符串产生影响。

这个说法是否正确取决于微架构。使用经典的4级RISC流水线模型，几乎可以肯定是正确的。但是很难确定它是否适用于当代的乱序超标量CPU，其中核心速度可以完全超过内存流速。在这种情况下，"可以退役的指令数"相对于"可以流式传输的字节数"之间可能存在很大差距，以至于您每个可以流式传输的字节都有"可以退役的指令数"。如果足够大，则可以免费完成ctz + shift指令。

- johne

---

OP说字符串已经正确地以null结尾，所以你关于char bytes[1] = {0x55};的讨论是无关紧要的。非常相关的是你提到了对于任何不知道长度的单词读取算法都是如此。 - Seth Robertson

这个问题不适用于我引用的版本，因为你只在对齐的指针上使用它——至少正确的实现是这样做的。 - R.. GitHub STOP HELPING ICE

@R，这与“对齐指针”无关。假设你有一种支持字节级粒度的VM保护的架构，并且每个malloc分配在两侧都“足够填充”，并且VM系统强制执行该分配的字节粒度保护...无论指针是否对齐（假设是微不足道的32位int自然对齐），仍然可能出现对该对齐读取超出分配大小的情况。任何超出分配大小的读取都是未定义行为。 - johne

@johne: 对评论点赞。从概念上讲，你是正确的，但现实情况是，字节级保护在存储和执行方面都非常昂贵，因此它们不存在，也永远不会存在。如果你知道底层存储是从类似于“mmap”的页面粒度映射获得的，那么对齐就足够了。 - R.. GitHub STOP HELPING ICE

我在苹果的i386 strlen中没有看到任何SSE3指令，只有SSE2。pcmpeqb、pmovmskb、pxor和movdqa都是SSE2。可能他们只是在注释中提到了SSE3，因为SSE3是苹果x86 CPU的基准。 (最初的苹果x86是Core Duo，而SSSE3是Core 2 Duo (Merom/Conroe)中的新功能。很遗憾苹果不得不支持一个不能运行64位代码的CPU，因为他们比一代CPU早了一步。) - Peter Cordes

Answer 7

我知道这是一个老问题，但大多数坏的移位表都是单个字符。如果对于您的数据集有意义（例如特别是如果它是书面单词），并且如果您有可用的空间，使用由n-gram而不是单个字符组成的坏移位表可以获得显着的加速。

- Timothy Jones

Answer 8

一个非常好的问题。只需要添加一些小细节...

1. 有人正在谈论DNA序列匹配。但对于DNA序列，我们通常会为干草堆建立一个数据结构（例如后缀数组、后缀树或FM索引），并将许多针匹配到它上面。这是一个不同的问题。

2. 如果有人愿意对各种算法进行基准测试，那就太好了。在压缩和后缀数组构造方面有非常好的基准测试，但我还没有看到关于字符串匹配的基准测试。可能的干草堆候选者可以来自SACA基准测试。

3. 几天前，我正在测试你推荐的页面中的Boyer-Moore实现（编辑：我需要一个类似memmem()的函数调用，但它不是标准函数，所以我决定实现它）。我的基准测试程序使用随机干草堆。似乎该页面中的Boyer-Moore实现比glibc的memmem()和Mac的strnstr()快几倍。如果你有兴趣，实现在这里，基准测试代码在这里。这绝对不是一个真实的基准测试，但这是一个开始。

- user172818

---

如果您有一些好的测试用例，可以与SACA基准测试中的哈希表候选项一起进行测试，请将其作为答案发布在我的其他问题中，除非有更好的答案，否则我会标记它为已接受。 - R.. GitHub STOP HELPING ICE

关于您的memmem和Boyer-Moore算法，很可能Boyer-Moore（或者说Boyer-Moore的一种增强算法）在随机数据上表现最佳。随机数据具有极低的周期性和长偏差匹配的概率，这会导致二次最坏情况。我正在寻找一种将Boyer-Moore和Two-Way结合起来，或者高效地检测何时可以“安全使用”Boyer-Moore的方法，但迄今为止我没有取得任何成功。顺便说一句，我不会将glibc的memmem作为比较对象。我的实现基本上与glibc相同的算法速度快几倍。 - R.. GitHub STOP HELPING ICE

正如我所说，这不是我的实现。感谢Christian Charras和Thierry Lecroq。我可以想象为什么随机输入对基准测试不利，我相信glibc选择算法是有原因的。我也猜测memmem()没有被高效地实现。我会尝试的。谢谢。 - user172818

Answer 9

这是Python搜索实现，在核心中被广泛使用。注释表明它使用了一个压缩的Boyer-Moore Delta 1表。

我自己进行了一些相当广泛的字符串搜索实验，但这是针对多个搜索字符串的。Horspool和Bitap的汇编实现通常可以与像Aho-Corasick这样的算法相媲美，适用于低模式计数。

- Matt Joiner

Answer 10

你在提问中提到的“双向算法”（顺便说一下，这个算法真是太棒了！）最近已经得到改进，可以同时高效地处理多字节单词：最佳压缩字符串匹配。

我没有读完整篇论文，但看起来他们依赖于一些新的、特殊的 CPU 指令（例如 SSE 4.2 中包含的指令）的时间复杂度为 O(1)，尽管如果这些指令不可用，他们可以在 O(log log w) 的时间内模拟这些指令，其中 w 表示位数，听起来也不错。

- j_random_hacker