Haskell和C ++之间硬币找零性能的差异

Question

Haskell和C ++之间硬币找零性能的差异

6

我正在尝试在Haskell中实现硬币找零问题。问题如下：

给定一组硬币和无限个这些硬币，找到使一个特定值n所需的最小硬币数。

我在Haskell中编写了以下程序：

import Data.Vector ((!), generate)
import Control.Applicative
import Control.Monad

coins = [1, 5, 10, 25, 100] :: [Int]

coinchangev :: Int -> [Int] -> Int
coinchangev n cs = v ! n
 where v = generate (n+1) f
       f 0 = 0
       f n = 1 + minimum [v ! x | x <- map (n-) cs, x >= 0]

main :: IO ()
main = do n <- read <$> getLine :: IO Int
           putStrLn . show $ coinchangev n coins

我用C++编写了以下程序：

#include <iostream>
#include <vector>

using namespace std;
typedef vector<int> row;

const row coins {1, 5, 10, 25, 100};
#define INT_MAX 9999999;

int coinchange(const int n, const row& coins) {
    row v(n+1, 0);

    for (int i=1; i<n+1; i++) {
        int min = INT_MAX;

        for (int j=0; j<coins.size(); j++) {
            int x = i - coins[j];
            if (x >= 0 && v[x] < min) {
                min = v[x];
            }
        }

        v[i] = 1 + min;
    }

    return v.back();
}

int main() {
    int n; cin >> n;
    cout << coinchange(n, coins) << endl;

    return 0;
}

我使用ghc -O3（版本为7.8.4）编译了Haskell版本，使用g++ --std=c++1y -O3（版本为4.8.4）编译了C++版本。对于输入10000000，我的Haskell程序比我的C++程序需要更长的时间来完成。以下是使用time测量的计时结果：

Haskell：

6.40user 0.85system 0:07.26elapsed 99%CPU (0avgtext+0avgdata 2664316maxresident)k
152inputs+0outputs (1major+647822minor)pagefaults 0swaps

C++：

0.08user 0.00system 0:00.08elapsed 97%CPU (0avgtext+0avgdata 39964maxresident)k
0inputs+0outputs (0major+936minor)pagefaults 0swaps

我的问题是为什么我看到这样大的差异以及我可以采取哪些步骤（如果有的话）来提高Haskell代码的性能。我原本期望性能基本相同（至少在相同顺序内）。我的目标是在两种语言中保持解决方案简单（并希望是惯用的）。

- Ajit Singh

说实话，我对自己使用向量的方式也不太确定，也许这就是问题所在？ - Ajit Singh

1

为什么人们一直认为-O3是GHC选项？ GHC的优化级别最高只有2。 - Carl

@Zeta，感谢您的反馈，但我不知道如何利用这些信息来使它更快。也许您可以指点我正确的方向？ - Ajit Singh

使用 [x | x <- map ((v!) . (n-)) cs, x >= 0] 替代 [v ! x | x <- map (n-) cs, x >= 0] 将执行时间降低到

2.18user 0.29system 0:02.48elapsed 99%CPU (0avgtext+0avgdata 983660maxresident)k 0inputs+0outputs (0major+226603minor)pagefaults 0swaps

。 - Ajit Singh

1

性能分析会告诉你什么？ - jberryman

显示剩余3条评论

2个回答

0

我发现计算实际找零的长度非常快。（硬币列表必须按降序排序）

module Main where

change :: Int -> [Int] -> [Int]
change 0 _ = []
change _ [] = []
change amount coins@(c:cs)
   | c <= amount = c : change (amount - c) coins
   | otherwise  = change amount cs

main :: IO ()
main =
  print $ length $ change 10000000 [100, 25, 10, 5, 1]

- Jean-Baptiste Potonnier

2

嗨，这个解决方案很快，因为它不像我的实现那样做相同的事情——它只是找到一种产生n的方法，而不是使用最少数量的硬币。考虑 n=15 和 coins = [12, 10, 5, 1]。这会得到4，而正确答案是2。 - Ajit Singh

好的，明白了！我之前没有看到过这种情况！现在问题对我来说更加有趣 :) - Jean-Baptiste Potonnier

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chi · Accepted Answer

未装箱的向量可能会有所帮助：

import Data.Vector.Unboxed as U ((!), constructN, length)

coinchangev :: Int -> [Int] -> Int
coinchangev n cs = v ! n
 where v = constructN (n+1) f
       f w = case U.length w of
             0 -> 0
             m -> 1 + minimum [w ! x | x <- map (m-) cs, x >= 0]

原始代码：

$ time ./CoinChange 
100000

real    0m12.543s
user    0m11.742s
sys 0m0.800s

非装箱变量：

$ time ./CoinChange2
100000

real    0m1.598s
user    0m1.588s
sys 0m0.012s

原始的C++代码：

$ time ./CoinChange_cpp 
100000

real    0m0.084s
user    0m0.072s
sys 0m0.012s