連結リストは遅いの？

Java Python c/c++

Java（5.0）の連結リストは遅いよ、という話があったのでちょこちょこと書いてみます。

リストといっても、大きく分けると二つになります。

  • 配列式
  • 連結式

配列式はメモリを連続的に確保した普通の配列の拡張のようなものです。
連結式は要素同士をポインタで連結して前後関係を確保しているもので一般的に「連結リスト」と呼ばれます。

余談ですが、
所謂ポインタを繋ぐことで実装されるリストは遅いというのは感覚として解ると思います。
なぜか、というのを書いていきます。

JavaでいうLinkedListやC++のSTLにおけるlistが連結式の代表格ですが、
これらは要素を繋ぐために必ず内部で「要素同士を繋げるprevとnextを持った要素」を生成して、
そこにオブジェクトの参照（ないしは実体）をつっこみます。


要素を連結するための要素を「要素を追加するたびに」newする時間は明らかにオーバーヘッドが高いです。
また、メモリ領域が連続していないのでCPUアクセスの際のプリフェッチやキャッシュの面で弱いです。


逆に、
JavaでいうArrayListやC++のSTLにおけるvectorは「メモリ領域が連続しており」
かつまた「終端への追加時」に必ず確保をする必要がありません。
予約領域に対して変化後のサイズが収まっていれば単にサイズを増やして所定のメモリ領域に対して追加するのみです。

    public boolean add(E o) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = o;
	return true;
    }

JavaのArrayListが「終端に追加する際に」しているのはこれだけです。
ensureCapacityは、sizeが増えることでいま確保している領域（Capacity）を超えないかどうかをチェックし、
超えていれば新しく確保を試みます。
これは、適切なCapacityを持つ配列をnewし、
今までの配列をすべて破棄するために、
System.arraycopy(oldData, 0, elementData, 0, size);
を呼び出すのでそれなりに重いですが、そうそう毎回は呼ばれません。

が、LinkedListはというと、

    private Entry<E> addBefore(E o, Entry<E> e) {
	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
    }

です。（addは終端に対するaddBeforeを実行します）
要素をいれるためのEntryをnewしていますね。


なので、
「末尾に追加するだけ」であればArrayListやvectorを使うのが正解です。
（Capacityが想定できるのであれば指定しておくとなお良いです）
反面、
「末尾以外に追加／削除」することが多いならLinkedListやlistを使うのが正解です。
上記の配列式だと末尾以外への操作はすべて
要素を（いれる／なくす）ための隙間を（あける／うめる）ために要素を隣に移動させなければならないので、
配列コピーを伴うためです。



じゃ、Pythonは？
というとPython（2.5）のlistはArrayListやvectorに類するものです。

listのappendの実体である
PyList_Appendは、中で

app1(PyListObject *self, PyObject *v)
{
	Py_ssize_t n = PyList_GET_SIZE(self);

	assert (v != NULL);
	if (n == PY_SSIZE_T_MAX) {
		PyErr_SetString(PyExc_OverflowError,
			"cannot add more objects to list");
		return -1;
	}

	if (list_resize(self, n+1) == -1)
		return -1;

	Py_INCREF(v);
	PyList_SET_ITEM(self, n, v);
	return 0;
}

こんなことをしています
サイズを調べ、
「必要なら」サイズを拡張し、
（PyListObjectのallocatedでCapacityを表しています）
新しいアイテムをそれに対して追加する。
といった感じです。
PyList_SET_ITEMはマクロでこんなことになります。

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

要素をいれているob_itemは単なる配列なんですね。


なので、「配列式」では回避できない中途に対するinsertには弱いです。

ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
	Py_ssize_t i, n = self->ob_size;
	PyObject **items;
	if (v == NULL) {
		PyErr_BadInternalCall();
		return -1;
	}
	if (n == PY_SSIZE_T_MAX) {
		PyErr_SetString(PyExc_OverflowError,
			"cannot add more objects to list");
		return -1;
	}

	if (list_resize(self, n+1) == -1)
		return -1;

	if (where < 0) {
		where += n;
		if (where < 0)
			where = 0;
	}
	if (where > n)
		where = n;
	items = self->ob_item;
	for (i = n; --i >= where; )
		items[i+1] = items[i];
	Py_INCREF(v);
	items[where] = v;
	return 0;
}

こんな感じ。
要素をずらすためのコピーをしていますね。
これは「要素が増えれば増えるほど」重いです。
（コピーする要素数に依存するので操作位置に依存します）


Pythonでも連結式のlistを使うことができる拡張くらいはあると思いますけどね。