Life Goes On

まあまあだけど楽しんでる方です

Haskell vs F# その後

mkotha さんに直してもらったりして、Haskellのコードはだいぶ速くなりました。どうも2重ループの内側がボトルネックのようなので、そこを展開して、データ構造も変えて、UNPACKプラグマは効くので残して、正格評価を1ヶ所だけ。性能と可読性のバランスがそこそことれたかなと思ってます。C++ や F# のコードにも同じような改修を加えたら、Haskell はまた抜かれてしまいました。まぁでも、目くじら立てるほどの差でもないので、そのままにしています。
実行環境が Windows というアドバンテージがあるとはいえ、C++ も超える F# の健闘が光ります。明示的な副作用がない関数プログラミングでこれだけ速いとうれしい。コード書いてても気持ちがいいし、Microsoft でなければもっと流行っていいはず。
最終形のコードを以下に載せておきます。
ついでに Scala でも書いてみました。C++ の2倍くらいの時間でしたが、書くだけで疲れてチューニングする元気もないので、処理時間はなしでコードだけ。

Haskell のコード

Data.Vector を早く標準モジュールに採用してほしい。cabal install するくらいはいいけど、プロファイラが使えないのが痛い。cabal install するときは -p オプションを忘れずに。

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U

data Node = Node {
  df :: {-# UNPACK #-} !Double,
  pu :: {-# UNPACK #-} !Double,
  pm :: {-# UNPACK #-} !Double,
  pd :: {-# UNPACK #-} !Double,
  iu :: {-# UNPACK #-} !Int,
  im :: {-# UNPACK #-} !Int,
  id :: {-# UNPACK #-} !Int
  }

induceBackward :: V.Vector Node -> U.Vector Double -> U.Vector Double
induceBackward nodes values = values `seq` V.convert (V.map value nodes)
  where
  next k = U.unsafeIndex values (U.length values `div` 2 + k)
  value (Node df pu pm pd iu im id) = (pu * next iu + pm * next im + pd * next id) * df

iteration = 10000

main :: IO()
main =  print (maximum [value i | i <- [0..iteration-1]])
  where
  value i = (foldr induceBackward (lastValues i) testTree) U.! 0
  lastValues i = U.replicate 201 (fromIntegral i)
  createNode j = Node 1.0 (1.0/6.0) (2.0/3.0) (1.0/6.0) (j+1) j (j-1)
  testTree = map (\i -> V.fromList (map createNode [-i..i])) [0..99]

F# のコード

自分の中で No.2 言語の座に躍り出ました。はてな記法も対応してほしい。

[<Struct>]
type ShortRateTreeNode = 
  val DF : double
  val PU : double
  val PM : double
  val PD : double
  val IU : int
  val IM : int
  val ID : int

  new (df, pu, pm, pd, iu, im, id) = {
    DF = df
    PU = pu
    PM = pm
    PD = pd
    IU = iu
    IM = im
    ID = id
    }

let induceBackward (nodes : ShortRateTreeNode []) (values : double []) : double [] =
  let next k = values.[values.Length / 2 + k]
  let value (node : ShortRateTreeNode) =
    (node.PU * next node.IU + node.PM * next node.IM + node.PD * next node.ID) * node.DF
  Array.map value nodes

let ITERATION = 10000

let maturityValues i = Array.create 201 (double i)
let createNode j = ShortRateTreeNode(1.0, 1.0/6.0, 2.0/3.0, 1.0/6.0, j+1, j, j-1)
let testTree = Array.init 100 (fun i -> Array.map createNode [|-i..i|])
let value i = (Array.foldBack induceBackward testTree (maturityValues i)).[0]
stdout.WriteLine (Array.max (Array.init ITERATION value))

C++ のコード

性能の話になると、けっきょく引き合いに出されるんですよね。

# include <vector>
# include <utility>
# include <memory>
# include <cstdio>

using namespace std;

struct node
{
  double df;
  double pu;
  double pm;
  double pd;
  int iu;
  int im;
  int id;
};

auto_ptr<vector<double> > induce_backward(const vector<node> &nodes, const vector<double> &values)
{
  const int n_nodes = nodes.size();
  auto_ptr<vector<double> > ret(new vector<double>());
  ret->reserve(n_nodes);
  const int n = values.size() / 2;
  for(int j = 0; j < n_nodes; j++)
  {
    const node &node = nodes[j];
    double sum = (node.pu * values[n + node.iu] + node.pm * values[n + node.im] + node.pd * values[n + node.im]) * node.df;
    ret->push_back(sum);
  }
  return ret;
}

const int iteration = 10000;

int main()
{
  vector<vector<node> > test_tree;
  for(int i = 0; i < 100; i++)
  {
    test_tree.push_back(vector<node>());
    vector<node> &nodes = test_tree.back();
    for(int j = -i; j <= i; j++)
    {
      node node = struct node();
      node.df = 1.0;
      node.pu = 1.0/6.0;
      node.pm = 2.0/3.0;
      node.pd = 1.0/6.0;
      node.iu = j+1;
      node.im = j;
      node.id = j-1;
      nodes.push_back(node);
    }
  }
  double maxval = 0;
  for(int i = 1; i <= iteration; i++)
  {
    auto_ptr<vector<double> > values(new vector<double>(201, (double)i));
    for(int j = 99; j >= 0; j--)
      values = induce_backward(test_tree[j], *values);
    maxval = max(maxval, (*values)[0]);
  }
  printf("%f\n", maxval);
  return 0;
}

Scala のコード

3年くらい前に触ったときと比べると、API が格段に充実しています。でも疲れた・・・

object ScalaBackwardInductionTest {
  class Node(j : Int) {
    val df = 1.0
    val pu = 1.0 / 6.0
    val pm = 2.0 / 3.0
    val pd = 1.0 / 6.0
    val iu = j + 1
    val im = j
    val id = j - 1
  }

  def induceBackward(nodes : Array[Node], values : Array[Double]) : Array[Double] = {
    def next(k : Int) : Double = values(values.length / 2 + k)
    def value (node : Node) : Double =
      (node.pu * next(node.iu) + node.pm * next(node.im) + node.pd * next(node.id)) * node.df
    return nodes.map(value)
  }

  val iteration = 10000

  def main(args : Array[String]) {
    def createStep(i : Int) : Array[Node] = Array.range(-i, i+1).map(j => new Node(j))
    val testTree : Array[Array[Node]] = Array.range(0, 99+1).map(createStep)
    def lastValues(i : Int) : Array[Double] = Array.fill(201)(i.toDouble)
    def value (i : Int) : Double = testTree.foldRight(lastValues(i))(induceBackward)(0)
    println((0 to iteration-1).map(value).max)
  }
}