p.4 の貪欲法。素朴なアルゴリズムよりこちらの実装のほうが楽に思える。
前回の遅いアルゴリズムとの速度比較。 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.Ord の Down みたいな小技は、知っているとお得感がある。
