FSharp的算法运行速度比Python慢

FSharp的算法运行速度比Python慢

通过电子邮件与我联系的Jon Harrop博士解释了发生的情况：

问题仅在于该程序已针对Python优化。当然，当程序员比另一种语言更熟悉一种语言时，这很常见。您只需要学习一组不同的规则，这些规则就应如何优化F＃程序。…突然出现了一些事情，例如使用“
1..n do中的for for”循环而不是“ for i” = 1到n
do“循环（通常更快，但在这里不重要），在列表上重复执行List.mapi以模仿数组索引（不必要地分配了中间列表），并且您使用F＃TryGetValue
for Dictionary来分配不必要地（接受引用的.NET TryGetValue通常更快，但在这里并没有那么快）

…但是真正的杀手级问题竟然是您使用哈希表来实现密集的2D矩阵。在Python中使用哈希表是理想的选择，因为它的哈希表实现已经过非常出色的优化（事实证明，您的Python代码的运行速度与F＃编译为本机代码一样快！），但是数组是表示密集代码的更好方法。矩阵，尤其是当您希望默认值为零时。

有趣的是，当我第一次编码算法，我 DID 使用一个表-我改变了实施的字典为了清楚起见，（避免数组边界检查使代码更简单-和更容易推理）。

乔恩（Jon）将我的代码（back :-)转换为其数组版本，并以100倍的速度运行。

故事的道德启示：

• F＃字典需要工作…使用元组作为键时，已编译的F＃比解释的Python哈希表要慢！
• 显而易见，但无害于重复：简洁的代码有时意味着……慢得多的代码。

谢谢你，乔恩-非常感谢。

编辑
：用Array代替Dictionary使得F＃最终以预期的已编译语言运行的速度运行，这一事实并没有消除对Dictionary速度的修复的需要（我希望MS的F＃人员正在阅读此书）。其他算法取决于字典/哈希，因此无法轻松切换为使用数组。使程序每当使用字典时都会遭受“解释器速度”的困扰，这可以说是一个错误。如果像某些人在评论中说的那样，问题不出在F＃上，而是.NET字典，那么我认为这是.NET中的错误！

EDIT2 ：最清晰的解决方案是更改此方法，该解决方案不需要算法切换到数组（某些算法根本不适合该算法）：

let optimalResults = new Dictionary<_,_>()

到这个：

let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)

这一更改使F＃代码的运行速度提高了2.7倍，从而最终击败了Python（提高了1.6倍）。奇怪的是， 默认情况下
，元组使用结构化比较，因此，原则上，字典对键进行的比较是相同的（有或没有结构化）。Harrop博士认为，速度差异可能归因于虚拟调度： “
AFAIK，.NET在优化虚拟调度方面做得很少，而在现代硬件上虚拟调度的成本非常高，因为它是跳过程序的“计算目标”与不可预测的位置相对应，因此破坏了分支预测逻辑，几乎可以肯定会导致整个CPU管道被刷新并重新加载
。”

简而言之，正如Don
Syme所建议的那样（请看底部的3个答案），“当将引用类型的键与.NET集合结合使用时，应明确使用结构化哈希”。（Harrop博士在下面的评论中还说，使用.NET集合时，应
始终 使用结构比较）。

亲爱的MS中的F＃小组，如果有一种自动解决此问题的方法，请这样做。