我认为，在哈布雷（Habré）上有硅谷系列的粉丝。 本周，这是六个季节以来的第一次，他们展示了一个大代码-当然，我立即想在这里进行讨论。
为了羞辱主角理查德·亨德里克斯（Richard Hendrix），他的前任老板在一次会议上展示了他的旧守则的片段。 在那里，对已经排序的数据进行线性搜索-这样就可以完成任务，但是效率很低。
理查德本人并不认为该代码不好。 但是，在该系列的观看者中，他的决定突然发现了防守者，现在我想知道哈伯对他们的立场有何看法。
理查德的已知代码段如下所示：
int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1;
在这里，线性搜索依次转到排序列表的每个元素，直到找到正确的列表。 通常，他们更喜欢对排序的数据进行二进制搜索，每次将集合分成两半，将不适当的一半作为一个整体丢弃（由于数据量的增加，线性迭代的次数比二进制迭代快得多）。 但是在subreddit / r / SiliconValleyHBO中出现了以下注释 ：
“我想稍微研究一下，并指出，在许多情况下，理查德（Richard）在对分类数据进行线性搜索而不是二进制搜索时的“错误”实际上更具生产力。 使用庞大的数据集（我认为阈值在数百万个元素上），二进制搜索会更快。 但是通常，如果您的数据集不是巨大的，则线性搜索将更好地被处理器缓存，更适合于分支预测器，并且您的算法也可以被向量化。 线性搜索需要更多的迭代，但是每个搜索都比二进制搜索迭代快得多。 这是违反直觉的，与您在大学所教的所有内容相矛盾，但事实并非如此。
该报告非常有趣，并且显示了实际性能测量的一些惊人结果。”
线程的其他成员也支持该注释器：是的，从理论上讲，所有迭代都是等效的，但是在具有真正优化功能的真实硬件上，一切都完全不同。 就像该系列的创建者Mike Judge一样，他们在80年代就曾在Valley工作，当时所有这些L1缓存和分支预测还没有特别明显，因此CPU的性能更接近理想模型-这是该系列的一个例子。
对我来说，正如评论所言，这听起来似乎违反直觉，但是弄清楚理查德是否正确是一件很有趣的事情。 当然，这会干扰以下事实：该系列中没有给出整个上下文：例如，我们不知道迭代了多少数据。 一方面，理查德（Richard）随后在互联网巨头胡里（Hooli）工作，在那里他可能不得不处理数百万条记录，但另一方面，这是他的第一个工作日，无法立即将他丢掉成百万。 我们以这种方式提出这个问题：即使二进制搜索在胡里节中的大多数任务上显然更好，但理查德是否有可能根据自己的条件做出了正确的选择，而其他角色却白白嘲笑了他，却不知道上下文如何？
为了理解，我打开了Reddit引用的报告 。 如所承诺的，结果很有趣（鉴于这是Andrei Alexandrescu的报告，因此不足为奇），但是在查看了一部分并单击其余部分之后，我没有看到二进制和线性搜索的比较度量。
但是我记得在我们的DotNext会议上，同一位Alexandrescu也谈到了性能。 我打开了他为Habr制作的报告的文本版本 ，并搜索了“线性”一词。 事实证明，它只是给出了一个奇怪的场景示例，其中这种搜索比二进制搜索要有效得多（在两个集合相同的情况下搜索两个集合的匹配元素）–但这是一个非常特殊的情况，没有一般性结论“线性搜索被低估了。”
谷歌搜索了现代互联网对此的看法-但基本上找到了Stack Overflow的答案，他们只需编写“使用二进制文件，减少迭代次数”。 在某些情况下，他们尝试进行基准测试，但对我来说也不太令人信服。
当然，这里的选项乞求“您必须对自己进行基准测试，才能在真实的硬件上看到自己的所有内容。”
但是，如果我在DotNext的所有访问中都从两位注重性能的Andreevs（Alexandrescu和Akinshina ）那里学到了一些东西，那就是人们认识到基准测试错误的频率以及他们没有考虑多少。 因此，我对带有基准的随机互联网帖子信心不足，但对我自己而言甚至更低。
幸运的是，Habr上的人比我了解得多（例如，同一位Andrey DreamWalker Akinshin，他撰写了一本有关基准测试的完整书）。 因此，如果您理解该主题，请在评论中告诉我们一切的真实情况。 线性方法仍然可以适合多大尺寸的数据？ 即使理查德本人还没有准备好为之辩护，但理查德做正确的事情有多大可能？
而且，如果没有知识渊博的评论员，我将不得不在下一个 DotNext上将Akinshin附加到电池上，并进行基准测试。