JavaScript
sort
アルゴリズム
quicksort

とても長い配列の上位M件だけをクイックソートより高速に取り出す

More than 1 year has passed since last update.

要約

  • めっちゃ長い配列の上位M件だけ ソートして(*) 取り出したい時に、全部ソートするのは無駄に感じる
  • QuickSortをちょっと改良すると無駄なソートを省ける
  • 単純な実装でも10倍の差が出た

(*)単純に上位M件を選択するだけでなく、ソートまでしたい。

2015/11/09 20:22 既存の記事に関する情報を追記
2015/11/09 22:16 C++のSTLの場合を追記
2016/11/10 10:22 プログラムにバグが有ったので修正

発想

QuickSelect(wikipedia英語版記事) というアルゴリズムがある。
これは、「配列をソートした時、n番目にくる要素を効率よく取り出す」アルゴリズムである。

例えば

arr = [a, b, c, d, e];

という配列をソートした時に3番目にくる値 arr[2] を知りたい場合、

  • a < c
  • b < c
  • c < d
  • c < e

という情報さえわかれば arr[2] = c が求められる。

  • a < ba > b
  • d < ed > e

などの情報は知る必要が無い。

この「知る必要が無い情報」、つまり「行う必要がない比較」を省くことで、目的の要素だけを効率良く取り出せるようにしたアルゴリズムが QuickSelect である。

本題

N件の要素を持った配列 arr に対して、ソート後の上位M件 sortedArr[0] ~ sortedArr[M-1] を取り出したい場合を考える。

もちろん全てソートしても目的は達成できるが、sortedArr[M] ~ sortedArr[N-1] までの要素は知る必要がないので、全体をソートするのは少し無駄に感じる。
QuickSelectのように、不要な比較は極力省いてしまいたい。

ソートといえば、QuickSortという有名すぎるソートアルゴリズムがある。
ピボットとなる値を決めて、それより大きい要素を後ろ、小さい要素を前に持ってくることでソートを行っていく分割統治法の一種である。
wikipediaのクイックソートの記事にあるアニメーションを見るとなんとなく何をやっているのか分かる。

分割統治法でソートをしていく時に、分割された区間がそもそも上位M件にはいらなかったらその区間を無視する というのが今回の考えである。というかQuickSelectもその考え方であるが。

jsで実装

[2016/11/10 10:22 プログラムにバグが有ったので修正]

コード全体はこちら
https://gist.github.com/Kiikurage/c05059274fdd54048dc3?ts=4
やっていることは単純で、今回の方法 QuickTopSort では、小区間のソートを行う前に、小区間がそもそも上位M件に入るのかを確認している(L61-L64)。それだけである。

速度

テストコードも上gistに。

100万件の配列から、上位1000件だけをソートして取り出すというもの。
30回実行して平均をとっている。
実行環境はChrome最新版, Mac OSX Yosemite, メモリ4GB。

アルゴリズム 実行速度(ms)
QuickSort 219.690
QuickTopSort 20.062

というわけで、10倍の差がでた。
当然、配列の長さやソートする長さ、また実装の方法によって性能差は変わってくるが
今回の方法は有効であるということは確認できた。

既存の記事(2015/11/09 20:22 追記)

コメント欄でUnordered partial sorting にそれらしきことが書いてあると教えていただいた。

そちらでは、「上位k個を取り出す(ソートは不要)」という問題を考えている。
同様に分割統治法を用いてソートしていきながら、上位k個以内の小区間になったらその区間はソートせずに全て選択して良いとしている。
早い話が、QuickSelectによりk+1番目の要素を探してそれより上位の要素をごそっと抜き出している。

分割統治法で大雑把にソートしていきながら、不要なソートを行わないようにする という同様のアプローチである。

C++のSTLの場合(2015/11/09 22:16 追記)

アルゴリズムの強者たちがメンテをしているSTLにも同様の物があるとの情報。調べてみた。

nth_element

これはソート後のn番目の要素を高速に取り出すというもの。
QuickSelectがやろうとしたことと同じである。
実装には、QuickSelectの上位互換のようなものである、IntroSelect使っているらしい

QuickSelectは、一般に要素数が少ない場合に効率が悪いという欠点がある。
IntroSelectではこの欠点を補うために、
まず大雑把にQuickSelectで目的の要素が含まれる区間を狭めていき、
区間が十分に小さくなったらHeapSelectに切り替えて選択を行う。

同様に、QuickSortの上位互換として、HeapSortを併用するIntroSortというものもある。

IntroSelectを行う過程で、大雑把にだが配列がソートされていく。その情報を無駄にせず利用するのがこの記事で書いた方法だった。

partial_sort

こちらが本命。配列の上位M件だけをソートするという今回のテーマと同様のもの。

さて、コレはどのように実装しているのか。
最初に想像したものは、
「本記事の手法において、QuickSortの代わりにIntroSortを使用したもの」
だった。

しかしどうやらこれは違うらしい。

http://www.sgi.com/tech/stl/partial_sort.html によれば、

partial_sort(first, last, last) has the effect of sorting the entire range [first, last), just like sort(first, last). They use different algorithms, however: sort uses the introsort algorithm (a variant of quicksort), and partial_sort uses heapsort.

というわけで、通常のsort には確かにIntroSortを用いているが、partial_sort ではHeapSortを用いているとのこと。

なぜHeapSortなのか

Heapは構築は素早く、O(N)だが、取り出すのは時間がかかり、O(M log M)となる。
よって、上位M個だけ取り出す場合に、M << N が成り立つならば、partial_sort の計算時間は O(N) に近似できる。
一方 M ≒ Nの場合、partial_sort の計算時間は O(N log N) に近似できる。
よって、最悪計算量を O(N log N) に抑えることが出来るのである。

一方、QuickSortやIntroSortの場合、平均計算量は O(N log N) であるが、通常HeapSortよりも高速なソートである。しかし最悪計算量が O(N^2) であるという欠点がある。
「とてつもなく遅い場合が低確率で存在するが、殆どの場合は高速なソート」、それがQuickSortである。

STLでは、「一般に、QuickSortには負けるがどんな時もそれなりに早く終る」、HeapSortを利用したのである。