Haskell 和 C++ 之间 Coin Change 的性能差异

Question

我试图在 Haskell 中实现 Coin Change 问题。问题如下：

Given a set of coins and an infinite supply of those coins, find the minimum number of coins that it will require to make a certain value, say 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++ 版本需要更长的时间才能完成。以下是使用时间测量的时间：

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 代码的性能。我曾预计性能基本相当（至少在同一订单内）。我的 objective 是使两种语言的解决方案都简单（并且希望是惯用的）。

Answer 1

未装箱的矢量可能在此处有所帮助：

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

Answer 2

我发现取实际计算长度的变化是相当快的。（硬币列表必须按降序排列）

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]

Haskell 和 C++ 之间 Coin Change 的性能差异

Difference in performance for Coin Change between Haskell and C++

performance

haskell

comparison