egisatoshi/egison3 — pull request #19 by xenophobia (2013-05-10 10:23:07+00:00)
Title: Collectionを内部でSequenceとして扱うようにした。

Collectionをリストとして扱うと、consパターンはO(1)だが、snocパターンがO(n)かかってしまうため、両端への挿入＆参照が共にO(1)のSeq型に変更しました。
また、cons・snocパターンのマッチにかかる時間を計るベンチマークを追加しました。

以下にベンチマーク結果を示します。
cons・snocがほぼ同じ計算量でマッチできるようになっていますが、
リストより複雑なデータ構造へ変更した結果consにかかる時間が僅かに増えています。

（リストにくらべてFinger-treeは結合も速いはずですが、検証するベンチマークプログラムを思いつけませんでした。）

List版:
```
Running 1 benchmarks...
Benchmark benchmark-collection: RUNNING...
warming up
estimating clock resolution...
mean is 1.250129 us (640001 iterations)
found 143971 outliers among 639999 samples (22.5%)
6 (9.4e-4%) low severe
143965 (22.5%) high severe
estimating cost of a clock call...
mean is 28.14957 ns (7 iterations)

benchmarking collection/cons-bench
5001
5001
5001
5001
mean: 281.2067 ms, lb 280.0250 ms, ub 282.0460 ms, ci 0.950
std dev: 1.266066 ms, lb 0.0 s, ub 1.453733 ms, ci 0.950
variance introduced by outliers: 22.222%
variance is moderately inflated by outliers

benchmarking collection/cons-bench-large
50001
collecting 3 samples, 1 iterations each, in estimated 7.861080 s
50001
50001
50001
mean: 2.646408 s, lb 2.644789 s, ub 2.647865 s, ci 0.950
std dev: 2.395866 ms, lb 0.0 s, ub 2.523556 ms, ci 0.950
variance introduced by outliers: 22.222%
variance is moderately inflated by outliers

benchmarking collection/snoc-bench
5001
collecting 3 samples, 1 iterations each, in estimated 18.07244 s
5001
5001
5001
mean: 6.638375 s, lb 6.261870 s, ub 6.831204 s, ci 0.950
std dev: 326.3519 ms, lb 0.0 s, ub 333.9883 ms, ci 0.950
variance introduced by outliers: 22.222%
variance is moderately inflated by outliers
Benchmark benchmark-collection: FINISH
```

Seq版:
```
Running 1 benchmarks...
Benchmark benchmark-collection: RUNNING...
warming up
estimating clock resolution...
mean is 1.241936 us (640001 iterations)
found 138381 outliers among 639999 samples (21.6%)
8 (1.3e-3%) low severe
138373 (21.6%) high severe
estimating cost of a clock call...
mean is 27.72004 ns (7 iterations)

benchmarking collection/cons-bench
5001
5001
5001
5001
mean: 317.3253 ms, lb 316.6940 ms, ub 317.8430 ms, ci 0.950
std dev: 816.2378 us, lb 0.0 s, ub 896.6588 us, ci 0.950
variance introduced by outliers: 22.222%
variance is moderately inflated by outliers

benchmarking collection/cons-bench-large
50001
collecting 3 samples, 1 iterations each, in estimated 9.006444 s
50001
50001
50001
mean: 3.007008 s, lb 3.003828 s, ub 3.009579 s, ci 0.950
std dev: 4.030461 ms, lb 0.0 s, ub 4.453148 ms, ci 0.950
variance introduced by outliers: 22.222%
variance is moderately inflated by outliers

benchmarking collection/snoc-bench
5001
5001
5001
5001
mean: 318.2809 ms, lb 316.4258 ms, ub 319.2430 ms, ci 0.950
std dev: 1.609930 ms, lb 0.0 s, ub 1.666403 ms, ci 0.950
variance introduced by outliers: 22.222%
variance is moderately inflated by outliers
Benchmark benchmark-collection: FINISH
```