配列の添字・挿入・容量拡張
添字による参照と途中への挿入を試し、動的配列が要素を移動する場面を学びます。
説明
配列は、番号を指定して要素を参照するデータ構造です。番号を添字と呼び、ここでは0から数えます。固定長の要素を連続した領域へ配置すると、先頭位置と要素の大きさから各要素の位置を計算できます。途中へ値を挿入するときは、後ろの要素を移動して場所を空けます。
最初に4バイト整数の配置を表にし、添字と位置の関係を調べます。次に、4要素分の領域へ挿入し、領域が満杯になったら8要素分へコピーします。最後にPythonのリストでも挿入・削除を行います。演習で用意する配列の容量と、Pythonのリスト内部の確保量は別のものです。
1添字から位置を求める
先頭位置を0x1000、整数一つの大きさを4バイトとします。添字iの要素は、先頭から4×iバイト先にあります。
values = [10, 20, 30]3個の整数; base = 0x1000先頭位置; [(i, hex(base + 4*i), value) for i, value in enumerate(values)]添字・位置・値を表示添字0・1・2に対して、位置は0x1000・0x1004・0x1008です。先頭から数え直す必要はなく、添字から位置を計算できます。この表の位置は配置規則を説明するために定めた値です。
2使用数と容量
4要素分の領域に、3個の値を置きます。Noneは未使用の場所を示します。使用数sizeと容量len(slots)を別々に表示します。
slots = [10, 20, 30, None]4要素分の領域; size = 3使用中の要素数; slots, size, len(slots)配置・使用数・容量使用数は3、容量は4なので、あと1個入ります。添字3の場所は確保されていますが、有効な値としては扱いません。未使用と値0を混同しないため、空きにはNoneを使います。
3後ろから一つずつ移動
添字1へ15を挿入します。20と30を右へ動かす必要があります。先に30を空きへコピーし、それから20を動かすと、移動前の値を上書きせずに済みます。
slots[3] = slots[2]30を右へコピー; print(slots)途中の配置; slots[2] = slots[1]20を右へコピー; print(slots)移動後の配置最初は30が二つ、次は20が二つ表示されます。移動の途中では元の値を残したままコピーしています。前から動かすと、20で30を上書きし、元の30を失うおそれがあります。
4挿入を終える
空いた添字1へ15を書き、使用数を1増やします。領域を増やさなくても、挿入位置より後ろの2要素は移動が必要でした。
slots[1] = 15空いた場所へ挿入; size += 1使用数を更新; slots, size, len(slots)満杯になった領域配列は10・15・20・30となり、使用数も容量も4です。添字はその時点での位置なので、20の添字は1から2に変わりました。
5容量を倍にする
末尾へ40を追加するには空きが必要です。ここでは満杯になったら容量を2倍にする規則を採用し、新しい8要素分の領域へ4個をコピーします。
grown = [None] * (2*len(slots))容量2倍の領域; grown[:size] = slots[:size]有効な要素をコピー; copied = sizeコピーした個数; slots = grown新領域へ切り替え; slots, copied配置とコピー数4個をコピーしたため、今回の拡張には要素数に比例する作業が発生します。容量を倍にするのはこの演習の規則で、Pythonのリストが常に倍増するという意味ではありません。
6空き領域への末尾追加
新しい領域には空きがあります。40と50を順に末尾へ書き込みます。既存の要素は移動しません。
slots[size] = 40; size += 140を追加; slots[size] = 50; size += 150を追加; slots[:size], size, len(slots)有効な値・使用数・容量使用数6、容量8です。容量に余裕がある末尾追加は書き込みだけで済みます。途中への挿入は、空きがあっても後続要素の移動が必要です。
7Pythonのリストで同じ挿入
Pythonのlistは長さを変更できます。insertは指定位置より後ろをずらし、appendは末尾へ追加します。内部の容量管理はPythonが行います。
items = [10, 20, 30]初期値; items.insert(1, 15)添字1へ15を挿入; items.append(40)末尾へ40を追加; items挿入後の並び10・15・20・30・40となります。listが保持するのはオブジェクトへの参照で、最初の4バイト整数の配置例と同じメモリ表現ではありません。添字と挿入位置の考え方は共通しています。
8削除で後続要素が詰まる
添字1の15を削除します。その場所を空欄のまま残すのではなく、後ろの20・30・40が一つずつ前へ詰まります。
removed = items.pop(1)添字1を削除して取得; removed, list(enumerate(items))削除値と新しい添字取り出した値は15で、20の添字は1に戻ります。配列の途中への挿入・削除は、後続要素数に応じた移動を伴います。末尾での操作とは費用が違います。
まとめ
添字は位置を表し、挿入や削除によって後続要素の添字が変わります。
使用数と容量は異なります。空きがある末尾追加と、容量拡張を伴う追加では必要な作業が違います。
固定幅整数の連続配置とPythonのlistの参照配列を混同せず、どの要素が動くかに注目します。
操作履歴と解説を振り返れます。
Python 3
values = [10, 20, 30]; base = 0x1000; [(i, hex(base + 4*i), value) for i, value in enumerate(values)][(0, '0x1000', 10), (1, '0x1004', 20), (2, '0x1008', 30)]
slots = [10, 20, 30, None]; size = 3; slots, size, len(slots)([10, 20, 30, None], 3, 4)
slots[3] = slots[2]; print(slots); slots[2] = slots[1]; print(slots)[10, 20, 30, 30] [10, 20, 20, 30]
slots[1] = 15; size += 1; slots, size, len(slots)([10, 15, 20, 30], 4, 4)
grown = [None] * (2*len(slots)); grown[:size] = slots[:size]; copied = size; slots = grown; slots, copied([10, 15, 20, 30, None, None, None, None], 4)
slots[size] = 40; size += 1; slots[size] = 50; size += 1; slots[:size], size, len(slots)([10, 15, 20, 30, 40, 50], 6, 8)
items = [10, 20, 30]; items.insert(1, 15); items.append(40); items[10, 15, 20, 30, 40]
removed = items.pop(1); removed, list(enumerate(items))(15, [(0, 10), (1, 20), (2, 30), (3, 40)])
演習完了