はじめに

Twitter で CamelCase の文字列を Camel Case にするという話を見かけたので、やってみました。

文字列に含まれる文字は ['a'..'z'] ++ ['A'..'Z'] を想定しています。

  • 追記: 寄せられたご意見について追記しました。

split

分割するということなので split パッケージを使ってみます。

実行結果

ghci> splitCC "CamelCase"
"Camel Case"

fold

split パッケージを使った実装は直感的でコードもコンパクトです。

しかし、見た感じ効率悪そうですよね。(リスト全体を分割した後で unwords かけるため)

そのため、fold バージョンも実装してみましょう。

実行結果

ghci> foldSplitCC "CamelCase"
"Camel Case"

QuickCheck

念の為 QuickCheck を使ってランダムテストを行ってみましょう。

実行結果

$ stack test
splitcc-0.1.0.0: test (suite: splitcc-test)

+++ OK, passed 100 tests.

splitcc-0.1.0.0: Test suite splitcc-test passed

ベンチマーク

次は gauge を使ってどっちが速いか確認してみましょう。

実行結果

$ stack bench
Benchmark splitcc-bench: RUNNING...
splitCC/10                               mean 2.847 μs  ( +- 261.0 ns  )
splitCC/1000                             mean 287.2 μs  ( +- 3.935 μs  )
splitCC/100000                           mean 29.10 ms  ( +- 1.348 ms  )
splitCC/1000000                          mean 287.3 ms  ( +- 735.0 μs  )

foldSplitCC/10                           mean 219.3 ns  ( +- 2.955 ns  )
foldSplitCC/1000                         mean 25.65 μs  ( +- 246.5 ns  )
foldSplitCC/100000                       mean 2.640 ms  ( +- 22.98 μs  )
foldSplitCC/1000000                      mean 27.43 ms  ( +- 1.795 ms  )
Benchmark splitcc-bench: FINISH

AutoBench

最後に AutoBench を使って視覚的に実行時間の変化を確認してみましょう。

  • AutoBench を利用する際、デフォルトの設定では、入力の型は NFData 型クラスのインスタンスになっている必要があります。

AutoBench の結果

AutoBench の結果
AutoBench の結果

一応ターミナルにもこんな感じで詳細な結果も出力してくれます。

     • Executed benchmarking file ✔
     • Generating test report ✔
     • Analysing performance results...

 ―― Test summary ――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

  Programs       foldSplitCC, splitCC
  Data           Random, size range [0,10000..200000]
  Normalisation  nf
  QuickCheck     ✔
  GHC flags      n/a

 ―― Analysis ――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

  foldSplitCC
    Size          0       10000   20000   30000   40000   50000   60000   70000
                  80000   90000   100000  110000  120000  130000  140000  150000
                  160000  170000  180000  190000  200000
    Time    (ms)  0.000   0.179   1.225   1.978   2.112   6.172   4.232   1.248
                  0.217   5.961   5.184   2.715   5.186   2.690   6.810   4.810
                  7.073   7.760   5.122   8.280   18.66
    Std dev (ms)  1.742
    Average variance introduced by outliers: 83% (severely inflated)

    Fits          y = 1.18e-23 + 8.49e-17x + 2.98e-13x²
                  y = 3.45e-13 + 4.71e-8x
                  y = 3.47e-34 + 5.68e-29x + 9.70e-24x² + 1.70e-18x³

  splitCC
    Size          0       10000   20000   30000   40000   50000   60000   70000
                  80000   90000   100000  110000  120000  130000  140000  150000
                  160000  170000  180000  190000  200000
    Time    (ms)  0.000   1.080   9.397   13.53   6.133   39.55   29.14   9.504
                  1.596   44.46   38.58   16.35   35.41   17.94   38.40   52.06
                  59.35   62.88   40.68   58.27   105.0
    Std dev (ms)  10.54
    Average variance introduced by outliers: 62% (severely inflated)

    Fits          y = 2.41e-12 + 3.29e-7x
                  y = 8.06e-15 + 1.92e-8xlog₂(x)
                  y = 8.20e-23 + 1.21e-16x + 2.07e-12x²

  Optimisation:

    splitCC ≥ foldSplitCC (1.00)

 ――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

splitCC ≥ foldSplitCC (1.00) ということなので foldSplitCC の方が良い結果となりました。

まとめ

  • リストを何度も走査すると遅くなるので、fold で書くと良いよ!
  • 関数の振る舞いが変化していないか確認するために QuickCheck を使おう!
  • ベンチマークの実行はとても簡単なので積極的にやってみよう!
  • AutoBench を使って可視化すると楽しいよ!

寄せられたご意見

問題設定として convertRGBconvert R G B でいいの?

直感的に良くないですが、全然考えてなかったので今回は良いことにしておきたいと思います・・・。

グラフの隅に、“splitCCは線形でfoldsplitCCは2次”とか書いてあって本当にそうだと巨大な列で結果が逆転してしまうんだけどそれは間違いだよね。

これは (たぶん) グラフをプロットする際の値の選択が良くなかったため、間違った計算量が推論されてしまっています。

具体的にはこのような表示があり、ここから選ぶことになるのですが全然わからないので 1 を選択した結果、今回の図のようになりました。

  ▸ Select trend lines for the graph of results:

  foldSplitCC
    1)  y = 1.18e-23 + 8.49e-17x + 2.98e-13x²
    2)  y = 3.45e-13 + 4.71e-8x
    3)  y = 3.47e-34 + 5.68e-29x + 9.70e-24x² + 1.70e-18x³

  ▸ Select a fit       [1..3]
  ▸ View fits          [V]
  ▸ View statistics    [S]
  ▸ Don't plot         [X]

> 1

  splitCC
    1)  y = 2.41e-12 + 3.29e-7x
    2)  y = 8.06e-15 + 1.92e-8xlog₂(x)
    3)  y = 8.20e-23 + 1.21e-16x + 2.07e-12x²

  ▸ Select a fit       [1..3]
  ▸ View fits          [V]
  ▸ View statistics    [S]
  ▸ Don't plot         [X]

> 1

以下のように正しく選ぶと

――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

  ▸ Select trend lines for the graph of results:

  foldSplitCC
    1)  y = 2.80e-13 + 3.83e-8x
    2)  y = 9.34e-16 + 2.22e-9xlog₂(x)
    3)  y = -7.13e-3 + 1.34e-6log₂(x) + 4.22e-5log₂²(x)

  ▸ Select a fit       [1..3]
  ▸ View fits          [V]
  ▸ View statistics    [S]
  ▸ Don't plot         [X]

> 1

  splitCC
    1)  y = 2.15e-12 + 2.94e-7x
    2)  y = 7.18e-15 + 1.71e-8xlog₂(x)
    3)  y = 6.99e-23 + 2.79e-16x + 1.76e-12x²

  ▸ Select a fit       [1..3]
  ▸ View fits          [V]
  ▸ View statistics    [S]
  ▸ Don't plot         [X]

> 1

このように、正しい計算量になります。

AutoBench の真の結果
AutoBench の真の結果

MyString を定義するのが面倒な場合は以下のようにすると良いよ

splitCC ≥ foldSplitCC (1.00) っていうのはどういう意味

  • splitCC ≥ foldSplitCC の部分は splitCC よりも foldSplitCC 関数の方がパフォーマンスが向上していることを示しています。
  • (1.00) は QuickCheck によって生成されたテストケースを入力として利用した時に全てのテストケース (100%) で性能が改善されたという意味です。0.5 などとなっていた場合はテストケースによっては性能が向上していないということです。