一位同学最近在备战一场算法竞赛，语言误选了 Python ，无奈只能着手对常见场景进行语言迁移。而字符串查找的场景在算法竞赛中时有出现。本文即对此场景在 Python 和竞赛常用语言 C++ 下的速度进行对比，并提供相关参数和运行结果供他人参考。
本次实测设置两个场景：场景 1 的源串字符分布使用伪随机数生成器生成，表示字符串查找的平均情况；场景 2 的源串可连续分割成 20,000 个长度为 50 的字符片段，其中第 15,001 个即为模式串，形如“ab…b”（1 个“a”，49 个 “b”），其余的字符片段形如“ab…c”（1 个“a”，48 个“b”，1 个“c”）。
本次实测中，Python 语言使用内置类型 str的.find()成员函数，C++ 语言分别使用string类的.find()成员函数、strstr标准库函数和用户实现的 KMP 算法。
IPython 的 %timeit魔法命令可以输出代码多次执行的平均时间和标准差，在此取平均时间。C++ 的代码对每个模式串固定运行 1,000 次后取平均时间。
以下时间若无特别说明，均以微秒为单位，保留到整数位。
* 原输出为“2.63 ms”。IPython 的 %timeit输出的均值保留 3 位有效数字，由于此时间已超过 1 毫秒，微秒位被舍弃。此处仍以微秒作单位，数值记为“2630”。
本次实测时使用的设备硬件上劣于算法竞赛中的标准配置机器，实测结果中的“绝对数值”参考性较低。
根据上表中的结果，在给定环境和相关参数条件下，场景 1 中 Python 的运行时间大约为 C++ 中 string::find的五分之一，与std:strstr接近；而在场景 2 中 Python 的运行时间明显增长，但 C++ 的前两种测试方法的运行时间与先前接近甚至更短。四次测试中，C++ 的用户实现的 KMP 算法运行时间均较长，长于同条件下 Python 的情况。
Python 中的内置类型 str的快速查找（.find()）和计数（.count()）算法基于 Boyer-Moore 算法 和 Horspool 算法 的混合，其中后者是前者的简化，而前者与 Knuth-Morris-Pratt 算法 有关。
有关 C++ 的 string::find比std::strstr运行时间长的相关情况，参见 Bug 66414 - string::find ten times slower than strstr 。
Why do you think strstrshould be slower than all the others? Do you know what algorithmstrstruses? I think it's quite likely thatstrstruses a fine-tuned, processor-specific, assembly-coded algorithm of theKMPtype or better. In which case you don't stand a chance of out-performing it inCfor such small benchmarks.
KMP 算法并非是所有线性复杂度算法中最快的。在不同的环境（软硬件、测试数据等）下，KMP 与其变种乃至其他线性复杂度算法，孰优孰劣都无法判断。编译器在设计时考虑到诸多可能的因素，尽可能使不同环境下都能有相对较优的策略来得到结果。因而，在保证结果正确的情况下，与其根据算法原理自行编写，不如直接使用标准库中提供的函数。
同时本次实测也在运行时间角度再次印证 Python 并不适合在算法竞赛中取得高成绩的说法，你们觉得呢？平仑区留下你的看法。
我们在一个数组中想查找某个对象item我们改如何操作呢？很简单一层遍历就可以搞定了，如下：
但是我们有没有更优的算法来查找呢？
在数据结构的书中我们可以找到“哨兵查找法”，但是什么又是“哨兵查找法”呢？什么又是“哨兵”呢？
所谓“哨兵”就是用一个特殊的值来作为数组的边界key，可以少用一条判断语句，目的在于免去查找过程中每一步都要检测整个表是否查找完毕，以达到提高程序的效率。
相对于一层遍历，没有使用”哨兵“的，是有两个判断条件的i<array.count和if(array[i] == item)；但是使用了”哨兵“只有一个判断条件if(array[i] == item)！
如果你的数据量非常小的话，相对于一层遍历来说，差别微乎其微，但是当数据达到十万或者更多的时候，函数的执行时间就会有明显差距了！
我们可以将数组的第一个值作为”哨兵“，数据存储下标index从1开始，则list的0号位表示暂无元素，位”哨兵“Key。
比如数组中有一千个元素，我查找中间那个元素，运行结果如下：
欢迎各位大神提出宝贵的意见和建议，也欢迎大家进群交流365152048！
