![]() |
1
103
因为有几个 我在这儿转转,想澄清一些问题。
有 两个明显的缺点 功能快速排序实现的。在下面,让我们从 Haskell introduction :
第三个缺点有些隐蔽:与就地变量不同,这个实现 不断从堆中请求内存 对于列表中的cons单元,可能会将内存分散到所有地方。因此,该算法具有 缓存位置差 . 我不知道现代函数式编程语言中的智能分配器是否能缓解这种情况,但在现代计算机上,缓存丢失已成为一个主要的性能杀手。 结论是什么? 但是这个算法 当被约束到不可变域时,性能更差。其原因是,该算法具有一个独特的特性,即受益于许多(有时是低级的)微调,这些微调只能在阵列上有效地执行。对quicksort的简单描述忽略了所有这些复杂性(在函数和过程变量中)。 在阅读了工程排序函数之后,我不再认为快速排序是一种优雅的算法。有效实施,这是一个笨重的混乱,一个工程师的作品,而不是一个艺术家(不贬值工程!)!这有自己的审美观)。 但我也要指出,这一点是特别的快速排序。并不是所有的算法都能接受同样的低级调整。很多算法和数据结构 可以 在不可变的环境中不损失性能。 不变性甚至可以 不需要昂贵的拷贝或跨线程同步,从而降低性能成本。 不变性昂贵吗? 在quicksort的特殊情况下,有一个成本确实是不变性的结果。但总的来说, 不 |
![]() |
2
41
作为函数式编程的基准,这有很多问题。亮点包括:
因此,这个比较是一个很好的说明,为了编写高性能的代码,您必须详细理解您的语言(和算法)。但这不是一个很好的比较FP与非FP。如果你想的话,去看看 Haskell vs. C++ at the Computer Languages Benchmark Game 现在,假设您确实需要一个更合理的Quicksort基准,认识到这可能是FP与可变算法的最坏情况之一,并且忽略了数据结构问题(即假设我们可以有一个不变数组):
请注意对函数式快速排序的修改,以便尽可能只遍历一次数据,并与内置排序进行比较。当我们运行它时,会得到如下信息:
因此,除了知道尝试编写自己的排序是一个坏主意之外,我们还发现,如果对不可变的quicksort进行某种程度的谨慎实现,则它将受到大约3倍的惩罚。(还可以编写一个三等分方法,返回三个数组:小于、等于和大于轴的数组。这可能会稍微加快速度。) |
![]() |
3
10
我不认为Scala版本实际上是尾部递归的,因为您正在使用
另外,仅仅因为这是习惯性的Scala代码,并不意味着这是最好的方法。 最好的方法是使用Scala内置的排序函数之一。这样你就得到了不变性保证,并且知道你有一个快速的算法。 参见堆栈溢出问题 How do I sort an array in Scala? |
![]() |
4
8
不变性并不昂贵。如果您测量一个程序必须执行的任务的一小部分,并根据启动的易变性选择解决方案(例如测量快速排序),那么它肯定会很昂贵。
让我们从另一个角度来考虑这个问题。让我们考虑这两个函数:
当您使用不可变的数据结构进行编程时,您可以对代码进行结构调整,以利用其优势。它不仅仅是数据类型,甚至是单个算法。程序将是 设计 以不同的方式。 这就是为什么标杆管理通常毫无意义。要么你选择一种或另一种风格的自然算法,并且这种风格获胜,要么你对整个应用程序进行基准测试,这通常是不切实际的。 |
![]() |
5
7
排序数组是宇宙中最重要的任务。毫不奇怪,许多优雅的“不可变”策略/实现在“排序数组”微基准上失败。不过,这并不意味着不变性“总体上”是昂贵的。在许多任务中,不可变实现的性能与可变实现的性能相当,但数组排序通常不是其中之一。 |
![]() |
6
7
如果你只是简单地将你的命令式算法和数据结构重写成函数式语言,这确实是昂贵和无用的。为了让事情变得更好,您应该使用函数式编程中的特性:数据结构持久性、惰性计算等。 |
![]() |
7
7
斯卡拉 这是一个几乎和Java版本一样快的版本。;)
此版本生成数组的副本,使用Java版本对其进行排序并返回副本。Scala不会强制您在内部使用不可变结构。 因此Scala的好处是,您可以根据需要利用可变和不可变。缺点是,如果你做错事,你并不能真正得到不变性的好处。 |
![]() |
8
7
众所周知,QuickSort在执行时会更快,所以这很难进行公平的比较! 说了这些。。。Array.concat? 另一个 非常 这个 比较这两种方法时,最重要的问题是:“这种扩展到多个节点/核心的效果如何?” http://en.wikipedia.org/wiki/Quicksort#Parallelizations scala版本可以在函数递归之前简单地分叉,如果有足够的可用内核,它可以非常快速地对包含数十亿个条目的列表进行排序。
与单线程命令式方法相比,这种方法有什么不同呢。。。 因此,或许更重要的问题是: “考虑到单个核不会变得更快,同步/锁定对并行化来说是一个真正的挑战,可变性是否昂贵?” |
![]() |
9
2
有人说,面向对象编程使用抽象来隐藏复杂性,而功能编程使用不可变来消除复杂性。在Scala的混合世界中,我们可以使用OO隐藏命令式代码,让应用程序代码变得一窍不通。实际上,集合库使用了大量的命令式代码,但这并不意味着我们不应该使用它们。正如其他人所说,小心使用,你真的得到了最好的两个世界在这里。 |
|
user29759326 · 如何返回递归函数中的最后一个值? 5 月前 |
|
malife89 · 将java中的字符串读取为正确的日期格式 5 月前 |
![]() |
Tim · 在java中,有没有更快的方法将字节数组写入文件? 5 月前 |
![]() |
rudraraj · java中未声明最终变量 5 月前 |
![]() |
Bala Ji · 以下BFS的实施效率如何? 5 月前 |