sta*_*man 3 lisp performance haskell functional-programming imperative
我在lisp语言系列中接受了一些培训,现在我正在为自己的好处学习一些Haskell.在lisp中,功能样式是可以的,但有一些情况下必须使用命令式样式才能获得不错的性能,例如
附加
追加是缓慢的,因为它必须复制它的第一个参数(有时x100和成功摆脱它的版本一样慢).解决方法是将第一个列表的最后一个指针移动到第二个列表的开头,而不是附加.当然这是一种破坏性的操作.
分类
quicksort的功能版本创建了许多中间列表,这些列表以某种方式违背了算法的目的,即尽可能快.AFAIR,在常见的lisp中,sort是唯一没有功能版本的破坏性功能.
长度
这在lisp中是一项代价高昂的操作,因为必须在整个列表中查找其长度.这不一定是这样,afaik clojure以对数时间计算列表的长度.解决方案通常是在命令性循环中动态计算长度.
我的问题是,我们如何处理haskell中的这些问题？
Tho*_*son 11
正如delnan所说,这些问题是使用错误的数据结构,例如当你想要一个向量时的链表.
你的特定行动
追加:缺点是O(1),所以我怀疑你指的是分配cons细胞的行为,细胞上的模式匹配,以及细胞的最终GC.除非您优化列表,否则这是不可避免的,这在某些情况下会发生.
sort:我建议你看一下ST monad,它允许你使用在纯上下文中需要变异的算法.有关示例,请参阅vsort实现.
length:当然,获取链表长度的唯一方法是遍历列表.如果您经常需要长度,那么请考虑使用Set,Map或Vector - 所有这些都记录了可以在O(1)中访问的总大小.
一般来说
ST可变性.