首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >haskell中与“命令式”算法相关的性能

问haskell中与“命令式”算法相关的性能
EN

Stack Overflow用户
提问于 2013-08-04 17:43:57
回答 2查看 480关注 0票数 3

我在lisp语言系列中接受了一些培训,为了我自己的利益,我现在正在学习一些Haskell语言。在lisp中,函数样式是可以的,但是在一些情况下,命令式风格是获得良好性能所必需的。

  • 追加 追加是缓慢的,因为它必须复制其第一个参数(有时x100的速度与成功摆脱它的版本一样慢)。补救办法是将第一个列表的最后一个指针移动到第二个列表的开头,而不是追加。当然,这是一次破坏性的行动。
  • 排序 quicksort的函数版本创建了许多中间列表,这在某种程度上违背了算法的目的,即尽可能快。AFAIR,在普通的lisp中,排序是唯一没有功能版本的破坏性函数。
  • 长度 在lisp中,这是一个代价高昂的操作,因为要获得它的长度,必须从整个列表中取下来。这不一定是这样,afaik clojure以对数时间计算列表的长度。解决方案通常是在命令式循环中动态计算长度。

我的问题是,在haskell,我们如何处理这些问题?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2013-08-04 18:08:42

正如delnan所说,这些问题都与使用错误的数据结构有关,例如当您想要向量时使用链接列表。

您的特定操作

  • 附加: cons是O(1),所以我怀疑您指的是分配cons单元格的行为、单元格上的模式匹配以及单元格的最终GC。这是相当不可避免的,除非您优化了列表,这确实发生在某些情况下。
  • 排序:我建议您看看ST monad,它允许您使用需要在纯上下文中进行变异的算法。有关示例,请参阅vsort实现。
  • 长度:当然,获得链接列表长度的唯一方法是遍历列表。如果您经常需要长度,那么请考虑使用集合、映射或向量--所有这些都记录在O(1)中可以访问的总大小。

In General

  • 查看ST的易变性。
  • 对正确的问题使用正确的数据结构。了解Hackage必须提供哪些结构(向量、数组、哈希映射、哈希表、花过滤器等)。
票数 11
EN

Stack Overflow用户

发布于 2013-08-04 21:17:33

append不是一个通用的东西。追加到双结束队列与附加到“反”列表中是不同的。附加破坏性是不同的复制上-附加。根据您的标准,您可以为缓慢性、线程安全性或简单性进行优化,您对“问题”的定义将发生变化。

正如delnan和Thomas DuBuisson提到的,如果您选择正确的数据类型,Haskell有所有这些选项。

所以,如果你有一个你想要优化的特定算法,很可能会有一种方法把它转换成一个快速的无损版本,一个选项在通常的乘性log(n)减速下模拟破坏,或者一个选项在一个附加的恒定减速下运行参照透明的破坏。

要获得这种翻译的麻烦的好例子,请查看持久联合查找或函数图库的算法。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/18045736

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档