F# の Set と HashSet のパフォーマンス

ハマったのでメモしておきます。

経験的には、要素の追加/削除などの処理は F# の Set よりも HashSet の方が速いです。F# の Set は binary tree だと思うので（ですよね？）これらの計算量は O(log n)、対して HashSet は O(1) なので、まあそうだよね、と思います。

しかし、実務のコードで HashSet がエラく遅くて F# の Set に置き換えたら高速になったケースがあったので、テストコードを書いてみました。

open System
open System.Collections.Generic
open System.Diagnostics

[<EntryPoint>]
let main argv =
  let size = 100000 (* 10万要素 *)

  (* F# の Set と HashSet のパフォーマンス比較。
     集合が空になるまで先頭要素の削除を繰り返す処理。*)

  (* ---- F# Set ---- *)
  do
    let watch = Stopwatch()
    watch.Start()
    let mutable collection = seq { 1 .. size } |> Set.ofSeq
    while not collection.IsEmpty do
      collection <- collection |> Set.remove (collection |> Seq.head)
    printfn "F# Set : elapsed = %A" watch.Elapsed

  (* ---- HashSet ---- *)
  do
    let watch = Stopwatch()
    watch.Start()
    let collection = HashSet<int>( seq { 1 .. size } )
    while collection.Count > 0 do
      collection |> Seq.head |> collection.Remove |> ignore
    printfn "HashSet : elapsed = %A" watch.Elapsed

  0

実行結果：

F# Set : elapsed = 00:00:00.2876429
HashSet : elapsed = 00:00:10.7875533

HashSet 激遅ですね。

どうも先頭要素を取り出す処理（collection |> Set.head の部分。LINQで書くなら collection.First()）が遅いみたいです。とはいっても先頭要素の取得が必ず遅いわけではなく、遅くなってしまう条件があるようです。上記のプログラムでは取り出した先頭要素は毎回 Remove されていますから、毎回取り出される先頭要素が異なります。このような場合に先頭要素の取得に時間がかかるようです。

HashSet の要素の列挙ってどういう実装になっているんでしょう。ヘタレなのであんまり分かりませんが、確かにハッシュテーブルは要素の検索には向いていても列挙には向かなそうです。先頭要素が削除されてしまうと、ハッシュテーブルから先頭要素を探索する処理が必要になるから遅いのかな？

（…ここまで書いて気づきましたが、この記事ってたまたま比較対象に F# の Set を使っただけで、F# は殆ど関係ないですね。まあいいか。）