tts*_*ras 40 python algorithm performance f# dynamic-programming
几年前,我通过动态编程解决了一个问题:
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
(如果您注意到上面的"mono":我在Windows下测试过,使用Visual Studio - 速度相同).
至少可以说,我......感到困惑.Python比F#运行代码更快？使用.NET运行时编译的二进制文件运行SLOWER而不是Python的解释代码？!？!
我知道VM的启动成本(在这种情况下为单声道)以及JIT如何改进Python等语言的东西,但仍然......我期望加速,而不是减速!
我也做错了吗？
我在这里上传了代码:
https://www.thanassis.space/fsharp.slower.than.python.tar.gz
请注意,F#代码或多或少是Python代码的直接逐行转换.
PS当然还有其他的好处,例如F#提供的静态类型安全性 - 但如果在F#下强制算法的结果速度更差......至少可以说,我很失望.
编辑:根据评论中的要求直接访问:
Python代码:https: //gist.github.com/950697
FSharp代码:https: //gist.github.com/950699
tts*_*ras 47
我通过电子邮件联系的Jon Harrop博士解释了发生了什么:
问题很简单,该程序已针对Python进行了优化.当程序员比其他语言更熟悉一种语言时,这种情况很常见.你只需要学习一套不同的规则来规定F#程序应该如何优化......有些事情在我身上跳出来,例如使用"for i in 1..n do"循环而不是"for i" = 1到n做"循环(一般来说速度更快但不重要)",在列表上重复执行List.mapi以模仿数组索引(不必要地分配中间列表)以及使用F#TryGetValue for Dictionary分配不必要的(接受ref的.NET TryGetValue一般来说速度更快但在这里没那么多)
...但真正的杀手问题是你使用哈希表来实现密集的二维矩阵.使用哈希表在Python中是理想的,因为它的哈希表实现已得到极好的优化(事实证明你的Python代码运行速度与编译到本机代码的F#一样快!)但是数组是表示密集的更好方法矩阵,特别是当您希望默认值为零时.
有趣的是,当我第一次编写这个算法时,我DID使用了一个表 - 为了清晰起见,我将实现更改为字典(避免数组边界检查使代码更简单 - 更容易推理).
Jon将我的代码(返回:-))转换为其数组版本,并以100倍的速度运行.
故事的道德启示:
谢谢Jon,非常感谢.
编辑:用数组替换字典使得F#最终以预期编译语言运行的速度运行,这并不能否定修复字典的速度(我希望来自MS的F#人正在读这个).其他算法依赖于字典/哈希,并且不能轻易切换到使用数组; 每当使用字典时,使程序遭受"解释器速度",可以说是一个错误.如果像正如一些人在评论中所说的那样,问题不在于F#而在于.NET Dictionary,那么我认为这是......在.NET中的一个错误!
编辑2:最清晰的解决方案,不需要算法切换到数组(一些算法根本不适合),改变这个:
let optimalResults = new Dictionary<_,_>()
进入这个:
let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)
这种变化使得F#代码运行速度提高了2.7倍,最终击败了Python(速度提高了1.6倍).奇怪的是,元组默认使用结构比较,所以原则上,字典对键的比较是相同的(有或没有结构).Harrop博士认为,速度差异可能归因于虚拟调度:"AFAIK,.NET几乎无法优化虚拟调度,现代硬件上的虚拟调度成本非常高,因为它是一个"计算goto",可以跳过程序与不可预测的位置相反,因此破坏了分支预测逻辑,几乎肯定会导致整个CPU流水线被刷新并重新加载".
用简单的话来说,并且正如Don Syme所建议的那样(查看底部的3个答案),"在结合.NET集合使用引用类型的键时,要明确使用结构哈希".(Harrop博士在下面的评论中也说我们在使用.NET集合时应该总是使用结构比较).
亲爱的F#团队,如果有办法自动解决这个问题,请做.
正如Jon Harrop指出的那样,简单地使用字典构建可以显着Dictionary(HashIdentity.Structural)提高性能(在我的计算机上为3倍).这几乎可以肯定是为了获得比Python更好的性能而需要进行的微创改变,并保持代码惯用(而不是用结构替换元组等)并与Python实现并行.
编辑:我错了,这不是值类型与引用类型的问题.性能问题与散列函数有关,如其他注释中所述.我在这里保留我的答案,因为这是一个棘手的讨论.我的代码部分修复了性能问题,但这不是干净且推荐的解决方案.
-
在我的计算机上,通过用结构替换元组,我使样本运行速度提高了两倍.这意味着,等效的F#代码应该比Python代码运行得更快.我不同意评论说.NET哈希表很慢,我相信与Python或其他语言实现没有显着差异.另外,我不同意"你不能一对一翻译代码期望它更快":对于大多数任务,F#代码通常比Python快(静态类型对编译器非常有帮助).在您的样品,大部分的时间都花在做哈希表查找,因此它是公平的想象,这两种语言应该是几乎一样快.
我认为性能问题与gabage收集有关(但我没有用探查器检查过).为什么使用元组可以在这里慢于结构已经在SO问题进行了讨论原因(为什么是在.NET 4.0中的引用类型(类新的元组类型),而不是一个值类型(结构))和MSDN页面(大厦元组):
如果它们是引用类型,这意味着如果要在紧密循环中更改元组中的元素,则可能会产生大量垃圾.[...] F#元组是引用类型,但团队有一种感觉,如果两个,也许三个元素元组是值类型,它们可以实现性能提升.一些创建内部元组的团队使用了值而不是引用类型,因为他们的场景对创建大量托管对象非常敏感.
当然,正如Jon在另一篇评论中所说,你的例子中明显的优化是用数组替换哈希表.数组是明显快得多(整数索引,没有散列,没有冲突处理,不重新分配,更紧凑的),但是这是非常具体的,以你的问题,它并不能解释与Python的性能差异(据我所知, Python代码使用哈希表,而不是数组).
为了重现我的50%加速,这里是完整的代码:http://pastebin.com/nbYrEi5d
简而言之,我用这种类型替换了元组:
type Tup = {x: int; y: int}
此外,它看起来像一个细节,但你应该移出List.mapi (fun i x -> (i,x)) fileSizes封闭的循环.我相信Python enumerate实际上并没有分配一个列表(所以在F#中只分配一次列表,或使用Seq模块,或使用可变计数器是公平的).