実験・実装 · 基礎から応用へ

配列と連結リストの走査を測る

詰めた整数配列とノード列で同じ総和を計算し、計測区間とPython実装の影響を分けて考えます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 同じ要素を同じ順番でたどる
  2. PythonのlistをCの整数配列と同一視しない
  3. 構築後に走査を計測する
  4. 件数を増やしたときに確かめること
  5. キャッシュを調べるなら別の観測を足す
  6. 結果の書き方を決める
  7. この記事をロゲイアに質問する理解を確かめる

同じ要素を同じ順番でたどる

配列と連結リストは、どちらもn要素を全て読むなら走査にO(n)の仕事が必要です。しかし、同じ計算量だから実行時間まで一致するわけではありません。この実験では0から9999までの整数を、arrayモジュールの詰めた配列と、next参照を持つノード列へ入れます。両方で同じ順序の総和を求め、既知の式n(n−1)/2と照合します。まず答えを一致させてから、構築を除いた走査だけを測ります。計算量、データの配置、言語処理系の仕事を分けて考えるのが目的です。

PythonのlistをCの整数配列と同一視しない

Pythonの通常のlistは、一般にPythonオブジェクトへの参照を持ちます。ここでは整数値を詰めて持つarrayを使いますが、Pythonのループで値を取り出す処理には依然として処理系の費用があります。ノードも専用の小さなクラスで作り、各要素に値と次ノードへの参照を持たせます。アロケータが実際にどこへ置くかを、このコードだけで固定してはいません。したがって、差が出たとしても、それを全てキャッシュミスのせいと断定しないでください。低水準言語の配列とポインタを直接比較する実験とは条件が異なります。

構築後に走査を計測する

次のコードは配列とノード列を先に作り、正しさを確認してから五回ずつ測ります。perf_counterの差を使い、各回の値を残します。最小値だけを都合よく採用するのではなく、ばらつきと測定条件も見ます。assertによる結果照合も測定内に含まれるため、厳密な最適化比較へ拡張するなら、その費用をどう扱うかをそろえる必要があります。両者の構築時間や解放の費用は、この測定値に含めていません。後からまとめて「リスト操作全体の時間」と呼ばないようにします。

Python 3
from array import array
from time import perf_counter
class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next_node=None):
        self.value, self.next = value, next_node
n = 10000
packed = array("q", range(n))
head = None
for value in reversed(range(n)):
    head = Node(value, head)
def packed_sum():
    total = 0
    for value in packed:
        total += value
    return total
def linked_sum():
    total, node = 0, head
    while node is not None:
        total += node.value
        node = node.next
    return total
expected = n * (n - 1) // 2
for fn in (packed_sum, linked_sum):
    assert fn() == expected
    samples = []
    for _ in range(5):
        start = perf_counter()
        assert fn() == expected
        samples.append(perf_counter() - start)
    print(fn.__name__, samples)

件数を増やしたときに確かめること

件数を1000、10000、100000へ変えると、走査時間やメモリ使用量が変わります。全てを一度に大きくせず、結果の総和が毎回正しいことを確認します。小さい入力では時計や関数呼び出しの費用が目立ち、大きい入力ではキャッシュやメモリ帯域の影響が変わる場合があります。ノードを作る順序や参照先の並びを変えるなら、それは別の実験条件として記録します。連結リストの挿入が容易な性質と、先頭から全てを読む費用は別なので、走査の結果だけで全用途の優劣を決めないようにします。

キャッシュを調べるなら別の観測を足す

配列では近い要素が近いアドレスへ置かれるため、空間的局所性を利用しやすいという説明があります。連結リストでは次の参照を読んでから進む依存が生じます。ただし今回の時間だけでは、キャッシュミス数や実際のCPU待機時間を直接測っていません。低水準の原因を調べたいなら、対象環境で利用できる性能カウンタと、同じ仕事をする低水準実装を追加で検討します。Pythonのループの違い、整数表現、オブジェクト管理を変えずにキャッシュだけを変えた実験だとは述べないようにします。

結果の書き方を決める

報告にはPythonの版、要素数、五回の時間、構築を除いたこと、両者の総和が一致したことを記載します。特定環境で配列が速かった場合も、常に何倍速いという定数として扱いません。途中の要素を頻繁に入れ替える用途、既知ノードへ追加する用途、添字で位置を指定する用途では、必要な操作の組合せが変わります。構造を選ぶときは、読み取り、更新、探索、必要なメモリを合わせて評価します。この実験は、その判断のうち「全件走査」を観察するための一つの材料です。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 8

AI基盤へ進む · STEP 5

学習コースから次を選ぶ