警告の行番号を小さい順に保つ
配列とは、同じ大きさのデータを、メモリに隙間なく並べた入れ物です。リストの途中に1つ入れると何が起きるかを、手間の数で言えるようになります。
gcc が出した警告の行番号が、3、8、15、22と小さい順に並んでいます。10行目の警告を足すとき、10は15の手前に入ります。入れる場所を空けるために、後ろの要素を動かさなければなりません。
このレッスンのゴール
メモ
リストがメモリにどう置かれるかを説明し、途中に入れる手間を数えることができる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| 配列 | 同じ大きさの要素を、隙間なく並べた入れ物 | |
| 要素 | 配列に入っている、1つ1つの値 | |
| 添字 | 要素の位置を表す番号。インデックスとも言う | numbers[2] |
| ずらす | 場所を空けるため、要素を1つ隣へ動かすこと | |
| 容量 | 配列が確保している、要素を入れられる数 |
学生が入力するセルは、このプレビューでは空白です。
配列の要素は隙間なく並ぶ
配列は、メモリの連続した場所に、要素を順に置きます。1つの要素の大きさは、どれも同じです。
だから、n番目の要素の場所は計算で決まります。先頭の場所に、要素の大きさかけるnを足すだけです。
例: 先頭が1000番地の配列
| 添字 | 計算 | 場所 |
|---|---|---|
| 0 | 1000 + 4 × 0 | 1000番地 |
| 1 | 1000 + 4 × 1 | 1004番地 |
| 2 | 1000 + 4 × 2 | 1008番地 |
| 3 | 1000 + 4 × 3 | 1012番地 |
学生が入力するセルは、このプレビューでは空白です。
要素の大きさと全体の大きさ
python3 -c "import array; a = array.array('i', [10, 20, 30]); print(a.itemsize, len(a) * a.itemsize)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
gcc が10個の整数に使う大きさ
printf '#include <stdio.h>\nint main(void){int a[10];printf("%%zu\\n",sizeof a);return 0;}' | gcc -x c -o /tmp/size - && /tmp/sizeここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
途中に入れると、後ろの要素をずらす
配列は隙間なく並ぶので、途中に1つ入れる場所は空いていません。入れる場所から後ろの要素を、1つずつ右へずらして空けます。
ずらす数が、手間の大きさです。先頭に入れると全部をずらし、末尾に入れると1つもずらしません。
例: [3, 8, 15, 22] に10を入れる
| 手順 | 何をするか | 配列の様子 |
|---|---|---|
| 1 | 22を右へずらす | [3, 8, 15, _, 22] |
| 2 | 15を右へずらす | [3, 8, _, 15, 22] |
| 3 | 空いた場所に10を入れる | [3, 8, 10, 15, 22] |
学生が入力するセルは、このプレビューでは空白です。
ずらした数を数えるコード
# 警告の行番号は小さい順です。10 行目の警告を足します。
numbers = [3, 8, 15, 22]
value = 10
moves = 0
# 後ろから見て、value より大きい要素を右へずらします。
i = len(numbers) - 1
while i >= 0 and numbers[i] > value:
moves = moves + 1
i = i - 1
numbers.insert(i + 1, value)
print(numbers, "ずらした数:", moves)
# value を 1 に変えて、もう一度実行しましょう。
Python の insert を使う
python3 -c "a = [3, 5, 8]; a.insert(1, 4); print(a)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
insert は添字を渡すだけなので、いつも一瞬で終わると思いがちです。実際は、入れる場所から後ろの要素を全部ずらします。だから、長いリストの先頭に入れる作業は、短いリストよりずっと手間がかかります。
いっぱいになったら、大きい領域に引っ越す
配列の容量は、作ったときに決まります。いっぱいのまま1つ足すときは、もっと大きい領域を確保します。
今ある要素を全部、新しい領域に写してから、新しい要素を入れます。多くの言語は、容量を2倍にします。写す作業は、たまにしか起きません。
容量が2倍に増えていく様子
# 容量4の入れ物に、10個の要素を足していきます。
capacity = 4
used = 0
copies = 0
for item in range(10):
if used == capacity:
# いっぱいなので、2倍の領域に引っ越します。今ある要素を全部写します。
copies = copies + used
capacity = capacity * 2
used = used + 1
print("容量", capacity, "写した回数", copies)
# 10 を 20 に変えて、もう一度実行しましょう。