相关疑难解决方法(0)

Haskell的网站介绍了一个非常有吸引力的5行快速排序功能,如下所示.

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

它们还包括"C中的真正快速排序".

// To sort array a[] of size n: qsort(a,0,n-1)

void qsort(int a[], int lo, int hi) 
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l …

我正在尝试将一些代码从Python转换为C++,以便获得一点速度并提高我生锈的C++技能.昨天我感到震惊的是,在Python中,从stdin读取行的简单实现要比C++快得多(参见本文).今天,我终于想出了如何在C++中使用合并分隔符(与python的split()类似的语义)拆分字符串,现在我正在体验似曾相识!我的C++代码需要更长的时间才能完成工作(尽管不是一个数量级,就像昨天的课程一样).

Python代码:

#!/usr/bin/env python
from __future__ import print_function                                            
import time
import sys

count = 0
start_time = time.time()
dummy = None

for line in sys.stdin:
    dummy = line.split()
    count += 1

delta_sec = int(time.time() - start_time)
print("Python: Saw {0} lines in {1} seconds. ".format(count, delta_sec), end='')
if delta_sec > 0:
    lps = int(count/delta_sec)
    print("  Crunch Speed: {0}".format(lps))
else:
    print('')

C++代码:

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

void split1(vector<string> &tokens, const string …

作为编程挑战的一部分,我需要从stdin读取一系列空格分隔的整数(在一行上),并将这些整数的总和打印到stdout.有问题的序列可以包含多达10,000,000个整数.

我有两个解决方案:一个用Haskell(foo.hs)编写,另一个用等价的,用Python 2(foo.py)编写.不幸的是,(编译的)Haskell程序一直比Python程序慢,而且我不知道解释两个程序之间的性能差异; 请参阅下面的基准部分.如果有的话,我会期望Haskell占上风......

我究竟做错了什么？我如何解释这种差异？有没有一种简单的方法来加速我的Haskell代码？

(有关信息,我使用的是2010年中期的Macbook Pro,配备8Gb RAM,GHC 7.8.4和Python 2.7.9.)

foo.hs

main = print . sum =<< getIntList

getIntList :: IO [Int]
getIntList = fmap (map read . words) getLine

(编译ghc -O2 foo.hs)

foo.py

ns = map(int, raw_input().split())
print sum(ns)

基准

在下文中,test.txt由一行1000万个以空格分隔的整数组成.

# Haskell
$ time ./foo < test.txt 
1679257

real    0m36.704s
user    0m35.932s
sys     0m0.632s

# Python
$ time python foo.py < test.txt
1679257 

real    0m7.916s
user …

我知道quicksort的O(n log n)平均时间复杂度.伪快速排序(当你从足够远的地方看它,具有适当高的抽象级别时只是一个快速排序),通常用于演示函数语言的简洁性如下(在Haskell中给出):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

好的,所以我知道这件事有问题.最大的问题是它没有排序,这通常是quicksort的一大优势.即使这没关系,它仍然需要比典型的快速排序更长的时间,因为它在分区时必须进行两次列表传递,然后它会进行昂贵的附加操作以将其拼接回来.此外,选择第一个元素作为枢轴不是最佳选择.

但即便考虑所有这些,这个快速排序的平均时间复杂度与标准快速排序不同吗？即,O(n log n)？因为追加和分区仍然具有线性时间复杂度,即使它们效率低下.

你好Haskellers在那里!

我觉得有关性能的问题经常出现,并且关于哪些函数/算法/库快速稳定的知识很少.

当然有一些库Criterion允许自己进行测量,并且有一个可以调用的分析器

> ghc -O2 --make program.hs -prof -auto-all
> ./program +RTS -s

正如@DonStewart在用于分析Haskell程序性能的工具中所解释的那样

我知道:

• 使用read和show通常是一个瓶颈(对于数字的read功能,有Numeric一个性能加速的包
• 还有是Sequence,Array,Vector和Map库,这往往是更适合来解决,而不是用列表或嵌套列表的问题
• Text并且Bytestring是比String更好的选择
• 我最近看到,即使使用标准数字生成器也会显着减慢程序速度,而且mwc-random速度要快得多.
• Python的答案也比编译的Haskell更快？透露,标准排序算法肯定是可以改进的
• 的使用Int,而不是Integer,BangPatterns和严格的褶皱常常产生性能的提高
• 有conduit和pipes为"stricten" IO,(我不得不承认我没有使用尚未)
• 类型签名通常是一种改进

还有哪些常见的陷阱和瓶颈？

怎么解决？

我想到的主题是:

• 功能
• 数据结构
• 算法
• LANGUAGE扩展(GHC)？
• 编译选项？

我正在学习haskell,我看到的函数定义是:

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

是否可以只用一次遍历列表而不是3来编写它？

Haskell中的纯函数是否有可能改变变量的局部副本,就像在函数式编程是一个骗局中提到的那样.大卫·诺伦？如果不是这样的原因是什么原因,如果有的话,有没有人能指出我的例子？

类似的问题在函数中被问到,这些函数看起来对调用者来说是纯粹的,但在内部使用变异,并且普遍的共识似乎是纯函数执行变异是可行的,只要突变是在变量的局部副本上执行的(即效果)突变不会逃避功能并具有非局部效应).

问题出现了,当我翻译成沉冒泡排序(局部突变,全球突变,可变数据结构,冒泡齐),这并没有发生变异的名单,以共同Lisp和相比,在冒泡Common Lisp中冒泡,这确实发生变异列表.结果是我发现(在Common Lisp中)对于非常大的列表而言,变异列表的版本明显比没有变异列表的版本快得多.

我在lisp语言系列中接受了一些培训,现在我正在为自己的好处学习一些Haskell.在lisp中,功能样式是可以的,但有一些情况下必须使用命令式样式才能获得不错的性能,例如

• 附加

  追加是缓慢的,因为它必须复制它的第一个参数(有时x100和成功摆脱它的版本一样慢).解决方法是将第一个列表的最后一个指针移动到第二个列表的开头,而不是附加.当然这是一种破坏性的操作.

• 分类

  quicksort的功能版本创建了许多中间列表,这些列表以某种方式违背了算法的目的,即尽可能快.AFAIR,在常见的lisp中,sort是唯一没有功能版本的破坏性功能.

• 长度

  这在lisp中是一项代价高昂的操作,因为必须在整个列表中查找其长度.这不一定是这样,afaik clojure以对数时间计算列表的长度.解决方案通常是在命令性循环中动态计算长度.

我的问题是,我们如何处理haskell中的这些问题？

问题中的一般术语(与专业相反)意味着函数可以对项目进行排序,只要它们是一个类型的实例Ord.

考虑一个最着名的haskell广告

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

上述实施不是就地.
我试图写一个就地版本.就地快速进行快速排序很容易.通常,我们只需要一个可变数组,我选择了Foreign.Marshal.Array.
我的实现是就地并运行得很好,但我对它的类型签名不满意

(Ord a, Storable a) => [a] -> IO [a]

更确切地说,类型约束Storable a使我恼火.

显然,如果我们想要对项目进行排序,Ord则需要约束,而不Storable需要.
相比之下,经典的快速排序的类型或者签名sort的Data.List,是Ord a => [a] -> [a].约束只是Ord. …