Douglas-Peucker向けの優先度付きキュー実装の検討


Nov. 29 2015:


折れ線を間引くで書いたように、 Douglas-Peuckerアルゴリズムを改良して指定した点数まで点を削減して折れ線を簡略化する場合、 優先度付きキューを使うことになる。

このアルゴリズムでは

  1. 始点と終点を結ぶ線分で最も距離が大きな点P1を選ぶ
  2. 始点と点P1を結ぶ線分で距離最大となる点P2をキューに登録(優先度は点P2と線分の距離)
  3. 点P1と終点を結ぶ線分で距離最大となる点P3をキューに登録(優先度は点P3と線分の距離)
  4. キューから距離が最大(=優先度最大)の点を選んで、2に戻る

という手順となるため、「キューに2つ登録して、1つ取り出す」ということを繰り返すことになる。

そこで今回はランダムな優先度のデータを

  1. 連続して登録し、連続して取り出す(要はソートしているだけ)
  2. 「キューに2つ登録して、1つ取り出す」を繰り返すDouglas-Peuckerを想定した試験

という操作に対してどの優先度付きキューの実装が良い性能をしめすのか、ベンチマークを取ってみた。

優先度付きキューの実装にはいくつか方法があるが、今回は以下の6種類を試してみた。

  1. Array.sort(): キューへの追加はArray.push()、キューから取り出すときに必要であればArray.sort()してArray.pop()する。非常に単純で楽チン。結果の検証用。
  2. Selection: キューへの追加はArray.push()、キューから取り出すときに最大要素を選択。enqueue: O(1), dequeue: O(n2)。
  3. Insertion: キューへの追加時に挿入ソートを行う。キューから取り出すときはArray.pop()するだけ。enqueue: O(n2), dequeue: O(1)。
  4. Binary Insertion: キューへの追加時に二分挿入ソートを行う。あとは3と同じ。enqueue: O(n2), dequeue: O(1)。
  5. Binary Heap: 二分ヒープ(wikipedia)での実装。ポインタなしで実装できるので省メモリ。java.util.PriorityQueueはこれらしい。enqueue: O(log(n)), dequeue: O(log(n))。
  6. Pairing Heap: ペアリングヒープ(wikipedia: en)での実装。gcc(libstdc++)のpriority_queueはこれらしい。enqueue: O(log(n)), dequeue: O(log(n))。実装にはこれを参考にした。

いずれもJavaScriptで実装した。

ベンチマーク結果

以下、Firefox 29とChromium 34での結果。単位はmsで、小さいほうが高速。 載せていないがVirtualBox上のWindows XPで測定してもほぼ同じ結果だった。

Firefox 29 on Ubuntu 12.04 LTS 64bit

Sequential

n Array.sort() Selection Insertion Binary Insertion Binary Heap Pairing Heap
1000 3 4 3 1 2 2
2000 2 14 8 1 1 1
5000 3 88 49 4 2 2
10000 7 346 185 11 4 5
20000 - 1307 744 32 8 10
50000 - - - 177 22 26
100000 - - - 688 48 66
200000 - - - 2909 128 164
500000 - - - - 413 512
1000000 - - - - 996 1235

Dauglas-Peucker (2-enqueue, 1-dequeue)

n Array.sort() Selection Insertion Binary Insertion Binary Heap Pairing Heap
1000 15 3 2 1 1 1
2000 49 9 6 1 0 1
5000 274 47 36 1 3 1
10000 1107 180 128 4 4 2
20000 - 685 554 13 9 6
50000 - - - 53 21 15
100000 - - - 189 45 36
200000 - - - 719 102 78
500000 - - - - 313 250
1000000 - - - - 729 592

Chromium 34 on Ubuntu 12.04 LTS 64bit

Sequential

n Array.sort() Selection Insertion Binary Insertion Binary Heap Pairing Heap
1000 5 11 7 2 2 5
2000 3 33 17 2 2 2
5000 3 211 104 6 7 4
10000 6 921 428 13 10 10
20000 - 3238 2083 38 21 21
50000 - - - 210 63 66
100000 - - - 924 157 167
200000 - - - 6875 393 383
500000 - - - - 1289 1207
1000000 - - - - 2917 2779

Dauglas-Peucker (2-enqueue, 1-dequeue)

n Array.sort() Selection Insertion Binary Insertion Binary Heap Pairing Heap
1000 33 4 3 0 1 0
2000 119 17 13 2 2 0
5000 913 102 76 3 5 3
10000 4008 435 309 6 10 7
20000 - 1663 1501 16 21 10
50000 - - - 138 61 37
100000 - - - 581 147 100
200000 - - - 2298 321 206
500000 - - - - 996 605
1000000 - - - - 2203 1492

ということで、上記の表からわかるのは、

  • Google Mapsで作ったルートやGPSのログ(代表的なロガーの記録点数は10万〜20万)を処理することを考えると、Array.sort()やSelection(選択ソート)、Insertion(挿入ソート)では遅すぎる。
  • Binary Insertion(二分挿入ソート)なら点の数が少なければ許容できるかも。
  • Binary Heapでの連続的な(Sequential)操作に対しては、FirefoxではPairing Heapよりも高速だが、ChromiumではPairing Heapよりも遅い。
  • 「2つ加えて1つ取る」操作に対してはPairing HeapのほうがBinary Heapより高速。
  • 全体として、Firefoxのほうが2〜3倍高速。

といったところ。

結論

以上より、Douglas-Peuckerを改良したアルゴリズムで使う優先度付きキューの実装は、Pairing Heapが良いようだ。

補足

さらに他のヒープでの実装を試してみた。

またスマートフォン(URBANO L01、Android 4.2)でもベンチマークを取ってみた。

Sequential

n=1000000 Pairing Heap Binary Heap d-ary Heap (d=3) d-ary Heap (d=4) Skew Heap Leftist Heap
Firefox 29 on Ubuntu 12.04 1237 974 886 822 1791 1904
Chromium 34 on Ubuntu 12.04 2740 2909 2852 2846 4867 5080
Firefox 29 on Android 4.2 9270 9730 9369 8905 26907 37929
Chrome 35 on Android 4.2 25851 29397 27159 24713 35926 48263

Dauglas-Peucker (2-enqueue, 1-dequeue)

n=1000000 Pairing Heap Binary Heap d-ary Heap (d=3) d-ary Heap (d=4) Skew Heap Leftist Heap
Firefox 29 on Ubuntu 12.04 590 697 612 558 803 838
Chromium 34 on Ubuntu 12.04 1251 2146 2103 1956 1911 2280
Firefox 29 on Android 4.2 4609 6731 5697 5640 17942 8418
Chrome 35 on Android 4.2 11902 26250 24070 22631 14342 21853

d-ary Heap(d=4)はUbuntuのFirefoxにおいて最も良い性能を示した。

AndroidのFirefoxやChromiumではBinary Heapよりは高速だったが「2つ加えて1つ取る」操作においてPairing Heapは超えられなかった。 Skew HeapやLeftist Heapは特に連続的な操作に対して弱いようだ。

総じてPairing Heapか、d-ary Heap(d=4)が高速といえる。