Dictionaryクラスを使って高速化を試みる

F#

前回、バラバシ＝アルバートモデルの次数分布計算コードをF#で作ってみたわけである。
でもこのコード、aggregateがあまりにも遅い。いくら副作用がないとはいえ、この実行速度の遅さは許容しがたい。時間は大切なのだ。
なので今回は、内部でこっそりDictionaryを利用してチューニングしてみることにする。

以下変更部分のみ記載。

let aggregate list =

  let add (result:Dictionary<_,int list>) (data,one) =
    match result.TryGetValue(data) with
    | true , x -> result.[data] <- one::x
    | false , _ -> result.Add(data,[one])
    result

  list
  |> PSeq.fold add (new Dictionary<_,int list>())
  |> Seq.map (fun x -> (x.Key,x.Value))

let reduceCount (data,counts) =
  async { return (data , counts |> List.sum) }

let mapreduce list =
  list
  |> PSeq.map (fun data -> (data,1))
  |> PSeq.sort
  |> aggregate
  |> PSeq.map reduceCount
  |> Async.Parallel
  |> Async.RunSynchronously

aggregate内でSeq.foldするようにしたので、若干仕様を変えている。


Dictionaryはハッシュテーブルとして実装されているため、キーを使用した値の取得は非常に高速に行われる。また、TryGaetValueの結果をパターンマッチにかければ、キーの有無と値の束縛を一度に行える。
ここで、Dictionary.Addという副作用が入るが、aggregate外に副作用汚染が広まることはないので実質副作用のない関数とみても問題はない。
気になる実行時間だが、5倍〜6倍のはやさで動いた。