設計
パフォーマンス
動的配列

動的配列に値を挿入する際の速度についての考察

ここ最近、競技プログラミングや機械学習などというものに触れ、アルゴリズムの勉強をすることが多くなった。
その中では常に、プログラムのパフォーマンスに留意しながらソースコードを書かなければならない。
日々業務に励んでおられる諸兄方におかれても、それぞれプログラムが少しでも速く動くよう常にこれを気にしながら実装を考えられていることと思う。

確かに、プログラムの実行速度を決めるのはアルゴリズムだ。
しかし、たまには基本に立ち返り、そもそも今使っている道具自体の能力に関して熟考してみるのもありなのではなかろうかと思い、少しだけ調べてみることにした。

テーマは表題の通り、動的配列だ。

例えば何百万という数のデータを扱うとなると、現実的にはデータベースを用いるのが普通だろう。
しかし、場合によってはこの数のデータをプログラムの中で扱わなければならない場合がある。
あ、はい、競技プログラミングとかを想定しています。

その場合、もし入ってくるデータの数が決まっており、さらにデータの順番も気にしなくても良いという事であればただの配列で事足りる。
Javaでいえば
String[] strs = new String[1000];
などとして、for文で回してインデックスに一つずつ上から順番に入れていけばいいだけの話だ。
速度に何らの問題など発生しないだろう。

しかし、入ってくるデータの数が事前にわからず、さらに「入れるたびに順番に並べなければならない」となると話が変わってくる。
そもそも現実にそんな要件があるのかという話はさておき、だ。
もしこの要件を満たす実装をしなければならないとなると、パフォーマンスにどれほどの影響が出るのだろうか。
ちょっと前にArrayListを使ったプログラムでこのパフォーマンス問題が発生したので、今回ちょっとだけ頑張ってみることにした。
Javaでやっても良かったのだが、最近Pythonのmatplotlibの使い方を覚えたのでそれを使う。

方針としては、動的配列の「後ろに追加する」か「前に追加する」かをそれぞれ数万回やって、速度を見る。
追加する回数は、1000回、2000回、3000回……  ……98000回、99000回、100000回の100パターンとする。

後ろに追加していくパターン

Python3
import time
from matplotlib import pyplot

a = []
b = []

for i in range(1000, 100000, 1000):
    t = []
    start = time.time()
    for j in range(i):
        t.append(j) #後ろに追加していきますよ
    b.append((time.time() - start) * 1000)
    a.append(i)

pyplot.plot(a, b)
pyplot.show()

実行結果
Figure_0.png
はい、縦軸これミリ秒なんですね。
マシンの状態如何でグラフがギザギザになってしまっているが、追加する数に応じて線形に処理時間が増えており、全体としてはパフォーマンスに劇的な劣化は見られないと言える。

前に追加していくパターン

Python3
import time
from matplotlib import pyplot

a = []
b = []

for i in range(1000, 100000, 1000):
    t = []
    start = time.time()
    for j in range(i):
        t[0:0] = [j] #違うのはここだけ
    b.append((time.time() - start) * 1000)
    a.append(i)

pyplot.plot(a, b)
pyplot.show()

実行結果
Figure_1.png
なぁんという事でしょう(圧倒的 Before & After 感)。
見てください、まるで青きドナウのようなこの美しい曲線を。

上の方とかマッターホルンみてえになってんじゃねえかというツッコミをお待ちしております。

スライスを使う方法の代わりにinsertを使うという手もあるが、実行速度はどっこいどっこいと言ったところだった(スライスの方が若干速い)。
後ろに追加する方法と比較すると、まさに桁違いの性能差が出てしまう。

どうやらこれは、JavaのArrayListやPHPの配列でも同じ現象が起こる。
内部的に実際に何が起こっているのかはわからないが、以下のように仮定してみよう。

既に存在する動的配列の先頭に要素を追加すると、追加するインデックスよりも後ろにある要素はそれぞれ一つずつ新しいインデックスへ移動する。

1回目は移動なし、2回目の時は1つだけ移動、3回目の時は2つだけ移動、…… n回目の時はn-1個分だけ移動。
つまりこの仮定に基づけば、N個の要素を配列の頭に入れるという処理のパフォーマンスはざっくりと$O(N^2/2)$になる。
二次関数的にパフォーマンスは劣化していってしまうという事だ。
もし挿入先のインデックスがランダムだった場合は移動しなければならない配列の数もランダム(0~n個)になるので、一つも移動しなくていい場合から全て移動しなければならない場合まであることを考えるとパフォーマンスは平均で$O(N^2/4)$になる。
いずれにせよ、二次関数的なことに変わりはない。

実際に動かしてみた結果を見れば、この仮定も正しいんじゃないかという気がしてこないだろうか?
詳しく中身を知っているという方がおられたら、是非ともご意見を賜りたい。

恐らく、Javaの配列のコピー用に用意されているSystem.arraycopyArrays.copyOfRangeなどでも、同じような性能劣化が発生するはずだ。
少なくとも以前の問題発生時に、これに関しても時間がとてもかかることは実証済みである。
JavaにおいてはLinkedListを用いるという手もあるが、こちらは逆に、読み込みに時間がかかる。
とても、かかる。
そちらに関しても、そのうち何かしらの検証ができればと思っている。

「動的配列に値を挿入するのは遅い」というのは周知の事実だったのかもしれない。
しかしそれを実感してみると、とても身に染みる。
動的配列を使う際は、データ追加の方法には十分注意されたし、ということで今回の投稿とさせて頂く。

こういった小さなことの積み重ねが、何か大きなものの達成の礎になると信じて。

○実行環境
OS : Windows10 Pro 64bit
CPU : Intel(R) Core(TM)i5-2520M CPU @ 2.50GHz 2.50GHz
Memory: 8.00GB
Drive : 250GB SSD