几年前，我通过动态编程解决了一个问题:

https://www.thanassis.space/fillupDVD.html

解决方案是用 Python 编写的。

作为拓展视野的一部分，我最近开始学习 OCaml/F#。有什么比直接将我在 Python 中编写的命令式代码移植到 F# 更好的方法来测试水域 - 然后从那里开始，逐步走向函数式编程解决方案。

第一个直接端口的结果......令人不安:

在 Python 下:

  bash$ time python fitToSize.py
  ....
  real    0m1.482s
  user    0m1.413s
  sys     0m0.067s

在 FSharp 下:

  bash$ time mono ./fitToSize.exe
  ....
  real    0m2.235s
  user    0m2.427s
  sys     0m0.063s

(如果您注意到上面的“单声道”:我也在 Windows 下进行了测试，使用 Visual Studio - 相同的速度)。

至少可以说，我……很困惑。 Python 运行代码比 F# 快？使用 .NET 运行时编译的二进制文件运行速度比 Python 的解释代码慢？!？!

我知道虚拟机的启动成本(在这种情况下是单声道)以及 JIT 如何改进 Python 等语言的性能，但仍然......我预计会加速，而不是减速!

也许我做错了什么？

我已经在这里上传了代码:

https://www.thanassis.space/fsharp.slower.than.python.tar.gz

请注意，F# 代码或多或少是 Python 代码的直接逐行翻译。

附:当然还有其他收获，例如F# 提供的静态类型安全性 - 但如果在 F# 下命令式算法的结果速度更差……至少可以这么说，我很失望。

编辑:根据评论中的要求直接访问:

Python 代码:https://gist.github.com/950697

FSharp 代码:https://gist.github.com/950699

最佳答案

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

The problem is simply that the program has been optimized for Python. This is common when the programmer is more familiar with one language than the other, of course. You just have to learn a different set of rules that dictate how F# programs should be optimized... Several things jumped out at me such as the use of a "for i in 1..n do" loop rather than a "for i=1 to n do" loop (which is faster in general but not significant here), repeatedly doing List.mapi on a list to mimic an array index (which allocated intermediate lists unnecessarily) and your use of the F# TryGetValue for Dictionary which allocates unnecessarily (the .NET TryGetValue that accepts a ref is faster in general but not so much here)

... but the real killer problem turned out to be your use of a hash table to implement a dense 2D matrix. Using a hash table is ideal in Python because its hash table implementation has been extremely well optimized (as evidenced by the fact that your Python code is running as fast as F# compiled to native code!) but arrays are a much better way to represent dense matrices, particularly when you want a default value of zero.

有趣的是，当我第一次编写这个算法时，我DID使用了一个表——为了清楚起见，我将实现更改为字典(避免数组边界检查使代码更简单- 而且更容易推理)。

Jon 将我的代码(返回 :-))转换为 array version ，它以 100 倍的速度运行。

故事的寓意:

• F# 字典需要工作...当使用元组作为键时，编译的 F# 比解释 Python 的哈希表慢!
• 很明显，但重复也无妨:更简洁的代码有时意味着……更慢的代码。

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

编辑:将 Dictionary 替换为 Array 使得 F# 最终以编译语言预期运行的速度运行这一事实，并不否定修复 Dictionary 速度的需要(我希望 F#来自 MS 的人正在阅读这篇文章)。其他算法依赖于字典/哈希，不能轻易切换到使用数组；每当使用字典时，使程序遭受“解释器速度”，可以说是一个错误。如果像评论中的一些人所说的那样，问题不在于 F#，而在于 .NET 字典，那么我认为这......是 .NET 中的一个错误!

EDIT2:最清晰的解决方案，不需要算法切换到数组(有些算法根本不适合)是改变这个:

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

进入这个:

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

此更改使 F# 代码的运行速度提高了 2.7 倍，从而最终击败了 Python(速度提高了 1.6 倍)。奇怪的是元组默认使用结构比较，所以原则上，字典对键所做的比较是相同的(有或没有结构)。 Harrop 博士推测速度差异可能归因于虚拟调度:“AFAIK，.NET 几乎没有优化虚拟调度，并且虚拟调度的成本在现代硬件上非常高，因为它是一个“计算的 goto”，将程序计数器跳转到不可预测的位置，从而破坏分支预测逻辑，几乎肯定会导致整个 CPU 管道被刷新和重新加载”。

简而言之，正如 Don Syme (look at the bottom 3 answers) 所建议的，“在将引用类型的键与 .NET 集合结合使用时，请明确说明结构散列的使用”。 (Harrop 博士在下面的评论中还说，我们应该始终在使用 .NET 集合时使用结构比较)。

尊敬的 MS 中的 F# 团队，如果有办法自动解决此问题，请执行。

关于python - FSharp 运行我的算法比 Python 慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5850243/