北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

"アルゴリズムクイックリファレンス" のノート (2)

p.4 の貪欲法。素朴なアルゴリズムよりこちらの実装のほうが楽に思える。

github.com

前回の遅いアルゴリズムとの速度比較。 variance introduced by outliers が大きくていいのかは気になる。貪欲法の方が 2,000 倍以上速いので、むしろ前回の slow の実装に問題がありそう。

$ stack exec bench-convexhulls -- --output=convexhull.html
points generated
fromList [Point 2.1377835882015472e-2 0.37675969687894406,Point 0.13059550359891225 0.8854193459395515,Point 0.14393294171704973 0.6508550014289608,Point 0.14678966702903884 0.21690928594716652,Point 0.1757711424912075 0.38256258657810427,Point
 0.28131270801990793 0.5923766278106027,Point 0.3174033812169047 2.044354461161324e-2,Point 0.3439496349547865 0.6634254643623526,Point 0.35531986020882733 0.9939481921271572,Point 0.4572955120772927 0.8085648753413374,Point 0.47351659627409937
 0.654837905224889,Point 0.5475827076206295 0.6856510548569369,Point 0.5982120295123295 0.11060895459648956,Point 0.7500144155213943 0.4153833924540856,Point 0.7612610246351973 0.8364323883690482,Point 0.7686159957030524 0.9395602140690221,Poin
t 0.8566170876792828 0.3887263627739349,Point 0.8958593880534803 0.8857736692653796,Point 0.9108407836308833 0.7138539153041928,Point 0.9771895259588333 0.6526386332297055]
benchmarking slow
time                 5.779 ms   (5.547 ms .. 6.036 ms)
                     0.987 R²   (0.975 R² .. 0.998 R²)
mean                 5.858 ms   (5.748 ms .. 6.044 ms)
std dev              407.6 μs   (267.3 μs .. 603.6 μs)
variance introduced by outliers: 41% (moderately inflated)

benchmarking greedy
time                 2.451 μs   (2.413 μs .. 2.495 μs)
                     0.997 R²   (0.992 R² .. 0.999 R²)
mean                 2.452 μs   (2.421 μs .. 2.520 μs)
std dev              148.3 ns   (51.28 ns .. 270.0 ns)
variance introduced by outliers: 72% (severely inflated)

HTMLはこちら。

https://cdn.rawgit.com/hiratara/hs-nutshell-algorithm-examples/master/convexhull.html

降順に並べるときに使う Data.OrdDown みたいな小技は、知っているとお得感がある。