1. はじめに

今回は実務プログラミングにおいて知らず知らずのうちに遅いコードになっていそうな例をいくつか挙げて、それを計算量の観点から高速化してみたいと思います。

2. 計算量を意識することにどんな意味があるか

身近な例として、Qiita Contribution ランキングの作成を考えてみましょう。ランキングを作成するためには、各ユーザーの Contribution 数を大きい順に並び替える処理、すなわちソートが必要になります。

Qiita ユーザー数は現在およそ $30$ 万人です。標準ライブラリの sort を用いれば、それほどの計算時間はかからないと思います。しかし仮にこれを愚直な sort アルゴリズム (例えば、挿入ソートやバブルソートなど) で実行したら恐ろしいことになります。

愚直なソートは、並び替える要素の個数の 2 乗に比例した時間がかかります。すなわち $n$ を並び替える個数として $O(n^2)$ かかります。$1$ 秒間で $10^8$ ステップの処理を実行できるとすると、

$n = 200,000$ として $n^2 = 40,000,000,000$、すなわち $400$ 秒程度かかる

ということになります。データサイズとして $20$ 万というのは手頃であり、私たちが普段実世界で扱うデータサイズとして典型的なサイズだと思います。そのサイズのデータに対して単純な $1$ 回のクエリで $10$ 分弱要するのは容認できないことと思います。これに対して標準ライブラリの sort は $O(n\log{n})$ で動くアルゴリズムが用いられています。そちらを用いれば

$n = 200,000$ として $n\log{n} \simeq 3,500,000$、すなわち $1$ 秒もかからない

ということになります。実際にどの程度の時間がかかるかを正確に見積もることは大変難しいですが、まずはこのようなざっくりとした推定をすることは非常に有効です。使用するアルゴリズムの違いによってこれほどの違いが生じます。ここから得られる教訓として以下のことが言えると思います:

プログラムは「一瞬で終わる」わけではない
プログラムは「とにかく動けばよい」わけではない
雑な実装をすると、大きな損をすることになりかねない
標準ライブラリがあるなら、なるべく使おう
標準ライブラリがあっても、中身の計算量を意識しよう (後で例を挙げます)

本記事では、ついやってしまいそうな「計算量的に大きく損する実装」を取り上げて、改善する例を示していきたいと思います。

3. データ構造の中身の話

3-1. LinkedList (Java) の i 番目へのアクセスは遅い

少し前に以下の記事がとても話題になりました！

軽い気持ちでLinkedListを使ったら休出する羽目になった話

計算量を意識するべき事例として大変示唆に富んでいます。多くの人がこれを読んで「似たような失敗をやってはいないだろうか」と不安な気持ちになったのではないでしょうか。LinkedList は Java で使える連結リスト構造の実装です。やっていたことは

「連結リスト構造の i 番目の値を取得する」という処理を i = $0, 1, \dots, n-1$ に対して行う

というものでしたが

連結リスト構造の i 番目の取得は $O(n)$ かかる (前または後ろから見ていくため)
配列の i 番目の取得の取得は $O(1)$ かかる

という大きな違いがあります。LinkedList で get(i) の処理を各 i に対して行っていたのというのはつまり

「毎ステップごとにスタート地点 (or ゴール地点) からやり直して i 番目まで辿っていた」

ということです。それによって処理が非常に遅くなって休出する羽目になったいうストーリーでした。以下のグラフは記事から引用したもので、1 回 1 回のループの処理にかかっている時間を表したものですが、確かに $O(n)$ かかっているのが見て取れます (後半減っているのは後ろから見るように切り替わっているからです)。

1 回 1 回のループの処理に $O(n)$ かかっているのでループ全体では $O(n^2)$ かかることになります。$n = 10,000$ 程度であってもかなりの計算時間を要することになります。

結局リスト構造を素直に前から順番に見ていく処理に切り替えることで、1 回 1 回のループの処理が $O(1)$ となり、全体として $O(n)$ となったというストーリーでした。

3-2. vector (C++), ArrayList (Java), list (Python) からの検索処理は遅い

こちらも以下の記事が話題になりました。

Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由

Python に限らず各言語においてやってしまいがちな遅い処理として

C++ の std::vector において値 v の検索 $O(n)$
Java の ArrayList において値 v の検索 $O(n)$
Python の list[^list] において値 v の検索 $O(n)$

が有名です。なお、Python の list は前節で登場した連結リスト構造とは根本的に異なるものです。std::vector (C++) と ArrayList (Java) と list (Python) は細かい違いはあれど、サポートしている処理や計算量は類似していて、どれも可変長配列とよばれるものです。可変長配列の各操作に対する計算量と、各言語での記述方法を下表にまとめます:

やりたいこと	計算量	std::vector (C++)	ArrayList (Java)	list (Python)
i 番目へのアクセス	$O(1)$	a.at(i)	a.get(i)	a[i]
長さの取得	$O(1)$	a.size()	a.size()	len(a)
末尾へ v を追加	$O(1)$ (ならし)	a.push_back(v)	a.add(v)	a.append(v)
ソート	$O(n\log{n})$	sort(a.begin(), a.end())	Collections.sort(a)	a.sort()
値 v の検索	$O(n)$	find(a.begin(), a.end(), v) != a.end()	a.contains(v)	v in a

可変長配列は LinkedList とは異なり、普通にランダムアクセスができます。また、末尾への要素追加もならし計算量 $O(1)$ でできます。ならし計算量の意味合いについては今回は省略しますが、実際上は普通に $O(1)$ と考えて差し支えないです。またソート処理は C++ は IntroSort ベース、Python は TimSort ベースのようです。さて、表で見るように「値 v の検索」は $O(n)$ と遅いです。しかし特に Python では

if v in a:

と直観的に書きやすいため、ついやってしまいがちです。a のサイズが小さければ問題ないのですが、巨大サイズの a に対してはつらいことになります。

これらのデータ構造において値 v の検索にかかる計算時間が $O(n)$ になるのは線形探索法と言って、逐次的に各要素を確かめるような処理になっているためです。もし配列が予めソートされていれば、二分探索法によって $O(\log{n})$ で検索できるようになります。std::vector (C++) では std::lower_bound()、ArrayList (Java) では binarySearch()、list (Python) では bisect が使えます。ただし処理内容に細かい違いがあるので注意が必要です。

また、巨大サイズの配列に対して検索処理が多発するような場合には、そもそも可変長配列以外のデータ構造を検討するのもよさそうです。次節でも登場する連想配列 (ハッシュ)などは有力な選択肢になります。具体的には以下の記事¹にあるとおり、list の代わりに set (や dict) を用います。

Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由

3-3. vector (C++), ArrayList (Java), list (Python) からの削除処理は末尾を除いて遅い

可変長配列において値 v を検索するのが遅いことについて述べましたが、それと同じくらいやってしまいがちなこととして、

C++ の std::vector において削除処理 $O(n)$
Java の ArrayList において削除処理 $O(n)$
Python の list において削除処理 $O(n)$

が挙げられます。

やりたいこと	計算量	std::vector (C++)	ArrayList (Java)	list (Python)	備考
i 番目へのアクセス	$O(1)$	a.at(i)	a.get(i)	a[i]	普通にランダムアクセスできます
長さの取得	$O(1)$	a.size()	a.size()	len(a)
末尾へ v を追加	$O(1)$ (ならし)	a.push_back(v)	a.add(v)	a.append(v)
末尾要素の削除	$O(1)$	a.pop_back()	-	a.pop()	末尾を取り除くのは基本的に速いです
i 番目の要素の削除	$O(n)$	a.erase(a.begin()+i)	a.remove(i)	a.pop(i)	計算量を意識せずやってはいけないです
要素 v の削除	$O(n)$	-	-	a.remove(v)	計算量を意識せずにやってはいけないです

std::vector (C++) や ArrayList (Java) や list (Python) は基本的かつ便利なデータ構造なのですが、削除操作を最後尾以外に対して行うと基本的に遅く、ボトルネックになりやすいです。最後尾以外からの削除が遅い理由ですが、配列から要素を削除したとき、その要素の後ろにあるものをすべて前に詰めるからです。こうしたことを理解しておくと、上記の表の計算量について納得できると思います。以上の事情を説明した資料として以下が参考になると思います:

C++でのvector.erase()は遅い　(追記の内容なども)
LinkedList と ArrayList の使い分け方

なお、最後尾への要素の追加・削除だけでなく、先頭への要素の追加・削除も $O(1)$ でできるようにしたデータ構造として std::deque (C++) や ArrayDeque (Java) や collections.deque (Python) があります。

やりたいこと	計算量	std::deque (C++)	ArrayDeque (Java)	collections.deque (Python)
先頭へ v を追加	$O(1)$	a.push_front(v)	a.addFirst(v)	a.appendleft(v)
先頭要素の削除	$O(1)$	a.pop_front()	a.removeFirst(v)	a.popleft()
末尾へ v を追加	$O(1)$	a.push_back(v)	a.addLast(v)	a.append(v)
末尾要素の削除	$O(1)$	a.pop_back()	a.removeLast(v)	a.pop()

しかしながらやはり一般には

値 v の検索
i 番目の要素の削除
値 v の削除

は遅いので、こういった処理を頻繁に行う場合には、状況に応じて別のデータ構造を考えるのがよさそうです。代表的なものとしては以下のものが挙げられます。ただしいずれも「i 番目の要素へのアクセス」ができなくなることは要注意です。

連結リスト構造 (削除自体が $O(1)$ でできますが、削除する値 v の検索が必要ならば結局 $O(n)$ かかることになります)
平衡二分探索木 (検索も削除も挿入も自在に $O(\log{n})$ でできて、$k$ 番目に大きい値の取得も $O(\log{n})$ でできます、つまり実質オンラインソートのできるデータ構造です)
バケット (要素値が整数で値の上限値が小さいならば有力です、検索も削除も挿入も $O(1)$ でできます)
連想配列 (ハッシュ) (バケットを応用したもので、検索も削除も挿入も $O(1)$ でできて有力です)

これらを各言語で使用するときには、以下のライブラリがあります:

データ構造	C++	Java	Python	備考
連結リスト	std::list	LinkedList	-
平衡二分探索木	std::set, std::map, tree (g++拡張)	-	-	ハッシュに比べて「$k$ 番目に小さい要素の取得」も $O(\log{n})$ でできる部分では強いデータ構造ですが、残念ながら std::set や std::map にそのメソッドはなく、g++ 拡張の tree にはあるようです
連想配列	std::unordered_map	HashMap	dictionary	C++ では std::map を連想配列として用いるのも場合によっては有力です

3-4. 様々な言語での事情

C++、Java、Python に限らず、ここまで述べて来たような事情は多くの言語で当てはまります。特に

連結リスト構造
可変長配列
デック
連想配列
ヒープ (本記事では登場していないですが、基本的なデータ構造です、C++ の std::priority_queue など)
平衡二分探索木 (要素の大小関係も扱うとなると万能感のあるデータ構造です)

といったデータ構造は基本的なものなので、多くの言語で用意されています (ヒープや平衡二分探索木は用意していない言語も多そうです)。これらのデータ構造の中身や各操作に対する計算量を勉強しておくことで、どんな言語を用いても計算量事情を押さえやすくなります。最後に以下の表にまとめて整理します。実装依存の部分もあり、恐らく言語によって微妙に変わる部分もあることを了承いただければと思います。「-」はそのデータ構造が基本的にはサポートしていないことを表しています。

やりたいこと	連結リスト	可変長配列	デック	連想配列	ヒープ	平衡二分探索木	備考
i 番目へのアクセス	$O(n)$	$O(1)$	$O(1)$	-	-	-	可変長配列やデックの取り柄です
サイズの取得	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(1)$	実装依存ですが基本的に $O(1)$ です
要素 v を追加	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(\log{n})$	$O(\log{n})$	挿入位置とか関係なしにとにかく v を追加したいケースを想定しています
末尾へ v を追加	$O(1)$	$O(1)$	$O(1)$	-	-	-
末尾要素の削除	$O(1)$	$O(1)$	$O(1)$	-	-	-
先頭へ v を追加	$O(1)$	$O(n)$	$O(1)$	-	-	-
先頭要素の削除	$O(1)$	$O(n)$	$O(1)$	-	-	-
i 番目に要素を挿入	$O(n)$	$O(n)$	$O(n)$	-	-	-	i 番目という概念が必要なら可変長配列やデックを用いざるを得ないでしょう
i 番目の要素の削除	$O(n)$	$O(n)$	$O(n)$	-	-	-	i 番目という概念が必要なら可変長配列やデックを用いざるを得ないでしょう
指定イテレータに要素追加	$O(1)$	-	-	-	-	-	連結リストのためにあるような操作です
指定イテレータの削除	$O(1)$	$O(n)$	$O(n)$	-	$O(\log{n})$	$O(\log{n})$	連結リストの取り柄と言えそうですが、平衡二分探索木でもよい感は少しあります
値 v の検索	$O(n)$	$O(n)$	$O(n)$	$O(1)$	-	$O(\log{n})$	連想配列や平衡二分探索木が得意です
値 v の削除	$O(n)$	$O(n)$	$O(n)$	$O(1)$	-	$O(\log{n})$	連想配列や平衡二分探索木が得意です
最小値の取得	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(1)$	$O(\log{n})$	ヒープや平衡二分探索木が得意です
$k$ 番目に小さい値の取得	-	-	-	-	-	$O(\log{n})$	このクエリが多発するなら平衡二分探索木は有力です

また各言語についての事情がわかりやすい資料を以下に紹介していきます (随時追加します):

3-5. バケットを使う

前節の最後にバケットの話が少し出て来ましたが、追加する値が $0$ 以上 $A$ 未満の整数値であることがわかっていて $A$ が $10^6$ 程度の小ささであって、メモリ消費量が気にならない場合には、バケットは最強です。アイディアは非常に単純で以下のような配列を用意するだけです。

num[i] := i が何個あるか

初期化としてはすべて $0$ にしておきます。これは「何も入っていない状態」を表します。

やりたいこと	計算量	実装	備考
要素 v の検索	$O(1)$	num[v] > 0 かどうか	特に、要素 v の個数もわかります
要素 v を追加	$O(1)$	num[v] += 1
要素 v の削除	$O(1)$	num[v] -= 1	先に num[v] > 0 かどうか判定しておくのがよいです

挿入される要素 v が重複しないことがわかっている場合には、num[v] は $0$ か $1$ の値しかとらないので bool 値にできます。その場合、バケットはビットとみなすこともできます。バケットを有効活用する例として

バケットソート
エラトスネテスのふるい ($1$ 以上 $n$ 以下の素数を $O(n\log\log{n})$ ですべて求めます)

があります。バケットソートは $O(n + A)$ の計算時間で実現することができて、$A = O(n)$ の場合にはクイックソートよりも高速に動作することもしばしばです。

4. 累積和・前処理

もう 1 つ、割とやってしまいそうな具体例を挙げます。なお本記事で紹介する累積和については以下の記事で改めて詳しく書きました。

累積和を何も考えずに書けるようにする！

4-1. 累積和

例えば文章が与えられて、$n$ 個の単語が登場していて、それが例えば以下のように頻度が小さい順に並んでいたとします。

計算量 1
オーダー 1
P 1
NP 1
...
私 593
を 782
です 814
が 831
は 953

自然言語処理において、しばしば低頻度単語を unk といったマクロで置換することが重要です。頻度が小さい方から順に unk と置換していって、文書全体の unk の割合が $1$ 割になるようにするタスクを考えてみましょう。

「最初の i 個の頻度の和が全体の単語数の $1$ 割を超えないようなギリギリ最大の i を求める」

という方針で考えてみます:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n; // 単語の種類数
    vector<int> nums; // 各単語の個数

    /* 入力読み込み */
    cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    /* 全体の単語数の算出 */
    int total = 0;
    for (int i = 0; i < n; ++i) total += nums[i];

    /* 処理 */
    int result = 0;
    for (result = 1; result <= n; ++result) {
        int sum = 0; // 最初の result 個の個数の和
        for (int i = 0; i < result; ++i) {
            sum += nums[i];
        }
        // 全体の 1 割を超えたら break
        if (sum > total / 10) break;
    }
    --result; // result は条件を満たさない最小の値なので 1 を引く

    cout << "You shold replace the first " << result << " words." << endl;
}

さて、このプログラムには計算量的に無駄な部分があります。それは、「最初の result 個の個数の和」を毎回計算している部分です。計算時間を評価してみましょう。簡単のために break はしないものします。そうすると、result 回目のループでは result 個の値を足し算しています。したがって result = $1, 2, ..., n$ についてループを回すと

$1 + 2 + \dots + n = \frac{1}{2} n(n+1)$

回の計算ステップを必要とします。すなわち $O(n^2)$ です。
これは以下のように改善できます。result 回目のループで求めたいのは

nums[0] + nums[1] + ... + nums[result-2] + nums[result-1]

ですが、よく考えると前回の result-1 回目のループで

nums[0] + nums[1] + ... + nums[result-2]

が計算されています。したがって、前回の結果 sum に nums[result-1] を加算してあげればよいです。以下のように実装できます:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n; // 単語の種類数
    vector<int> nums; // 各単語の個数

    /* 入力読み込み */
    cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    /* 全体の単語数の算出 */
    int total = 0;
    for (int i = 0; i < n; ++i) total += nums[i];

    /* 処理 */
    int result = 0;
    int sum = 0; // 途中までの総和
    for (result = 1; result <= n; ++result) {
        sum += nums[result-1]; // 前回の結果に nums[result-1] を加算

        // 全体の 1 割を超えたら break
        if (sum > total / 10) break;
    }
    --result; // result は条件を満たさない最小の値なので 1 を引く

    cout << "You shold replace the first " << result << " words." << endl;
}

今度は 1 回 1 回のループの演算は軽くなったので計算量オーダーは $O(n)$ に改善できました。このように配列の最初の i 個の値を累積して求めて行ったものを累積和と呼びます。

4-2. 累積和のさらなる活用: 前処理して区間和クエリ

累積和にはもっと便利な使い方があります。

sum[i] := 配列 array[] の最初の i 個の値

という配列を用意します。これは前節と似た実装で簡単に用意することができます。メモリはその分消費してしまいますが、この配列を用意しておくことで以下のようなクエリに爆速で答えることができます。

【区間和クエリ】
query(a, b): 配列 array の a 番目から b 番目の手前までの総和を求める

注意点として、配列の部分配列に関する標準ライブラリでは、array[a:b] (Python ではこんな書き方) のように書いた場合、b は含まない仕様になっていることが多いです。

この区間和クエリの処理はもちろん以下のように愚直に実装できるのですが、

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    vector<int> array; // 配列

    /* 入力読み込み */
    cin >> n;
    array.resize(n);
    for (int i = 0; i < n; ++i) cin >> array[i];

    /* クエリ処理 */
    int a, b;
    while (cin >> a >> b) { // クエリがたくさん来ることを想定
        if (a == -1 && b == -1) break; // a も b も -1 だったら exit する仕様にしておく

        int result = 0;
        for (int i = a; i < b; ++i) {
            result += array[i]; // 愚直に足す
        }
        cout << "query(" << a << ", " << b << "): " << result << endl;
    }
}

これでは毎回のクエリ毎に b - a 回の計算をすることになります。計算量で言えば毎回 $O(n)$ の計算をすることになります。しかし前処理として累積和を予め計算しておけば、

sum[b] - sum[a]

という計算をするだけでよいことがわかります！！！！！

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    vector<int> array; // 配列

    /* 入力読み込み */
    cin >> n;
    array.resize(n);
    for (int i = 0; i < n; ++i) cin >> array[i];

    /* 累積和の計算 */
    vector<int> sum(n+1);
    sum[0] = 0; // 最初の 0 個の和は何もないので 0
    for (int i = 0; i < n; ++i) {
        sum[i+1] = sum[i] + array[i]; // 累積和を計算, index に注意！！！
    }

    /* クエリ処理 */
    int a, b;
    while (cin >> a >> b) { // クエリがたくさん来ることを想定
        if (a == -1 && b == -1) break; // a も b も -1 だったら exit する仕様にしておく

        int result = sum[b] - sum[a]; // 累積和を利用して区間和計算
        cout << "query(" << a << ", " << b << "): " << result << endl;
    }
}

これで毎回のクエリに $O(1)$ で計算することができます。クエリ処理を行う前に累積和を計算する前処理が必要ですが、クエリがたくさん来る状況では累積和を前計算しておく価値は高いです。累積和に限らず、このような前処理を行っておくことで、計算時間をオーダーレベルで減らせるケースは多々あります。

なお、累積和を有効活用して計算量落とす話題として、この記事に挙げられている問題が面白いです。

5. 差分更新の話

最適化問題をアルゴリズム的に解決しようと思ったときの 1 つのアプローチとして、「今ある解を改良することを繰り返す」という山登り法が大変有効です。山登り法が使える場面としては

シフトスケジューリング問題において、今得られているシフトを一部組み替えることで、よりよいシフトを作ることを繰り返す
積み付け問題において、今得られている積み付け解を一部組み替えることで、よりよい積み付け解を得ることを繰り返す
配送計画問題において、お客さんを回る順序を最適化するときに、今得られている順序を一部入れ替えることで、より効率良い順序を得ることを繰り返す

などが挙げられます。注意点としては、このような山登り法を用いる場面では、真の最適解を得ることは諦めていることです。真の最適解を得ることは往々にして現在のコンピュータ・アルゴリズム技術では厳しいことが多く、現実的な計算時間内で少しでもよい解を得ようとするアプローチです。

このとき重要になって来るのは、できるだけ沢山の探索を行うことです。全てのパターンをしらみつぶすことは不可能なので、可能な限り探索領域を広くとれるようにすることが重要です。そのための 1 つの秘訣は評価関数の差分更新です。「今得られている解」と「少し組み替えてみた解」の良し悪しを比較するために評価関数を計算するわけですが、現実世界の問題ではしばしば評価関数の計算が非常に重たいです。「今の解」と「組み替えた解」の両方を愚直に計算するのでは時間がかかってしまいます。そこで

「組み替えた解」が「今の解」を少し変形しただけのものであることを活かして、評価関数の更新を高速に行う

ということがしばしば重要になります。こうした考え方は山登り法だけでなく

コンピュータ将棋の AI を作る際に、少し進んだ盤面の評価値を、今の盤面との差分更新によって求める

といった話にも繋がって来ます。実は差分更新による高速化の簡単な具体例はすでに前の章で登場しています。「4-1. 累積和」はまさに、「最初の i 個の頻度の総和を求める」処理を「前回の i - 1 個の頻度の総和」からの差分を更新することによって求めています。

おわりに

比較的ありがちな、うっかり計算量的に損してしまいそうな場面として思いついたものを特集してみました。これ以外にも様々な事例があると思われるので、見つけたら随時追記していきたいと思います。コメント等にて、様々な事例をお聞きしたいです。

引用記事中で、Python の list の実装は連結リスト構造である旨の解説がされているのですが、実際は可変長配列によって実装されています。 ↩

特集！知らないと損をする計算量の話