Pythonプログラミング（ステップ７・リスト（配列）・要素ごとの操作の基本）

このステップの目標

• リストを用い、要素への適正なアクセスに配慮したプログラムが書ける
• 計算によってアクセス位置を変えたり、配列要素の並べ替え操作を伴う処理、および必要なデータを探索するアルゴリズムを理解できる

１．リスト（配列）の基本

コンピュータを使って大量のデータを処理するために必須の機能、それがリスト（または配列）だ。 プログラミングの入門編といえども、リストは是非マスターしておきたい。

これまで書いてきたプログラムでは、処理の過程で、変数に名前を与えながら、

a=int(input())
b=100
c=a+b

のように記述していた。これは、その都度、データを入れる「箱」を用意するイメージである。

ところが、例えば、1000人から成る集団があって、それぞれの情報（例えば体重）を使った処理をしたいような場合（あるいは、データの件数が不定の場合）には、データ全体をひとまとめに扱って、通し番号（＊＊番目）で管理するほうが理にかなっている。 こちらは、マンションの集合ポストのように、全体として大きな入れ物が用意されていて、それがさらに（番号の付いた）個別の箱に分けられているイメージである。

Pythonに限らず、一般のプログラミング言語では、こうした用途に使うために、配列データ構造(array data type)が用意されている。 Pythonの世界では、これをリスト（list）と呼んでいる。

リストの生成

リストを用意するのはとても簡単で、

a = [ ]                   # 「空」のリストaを生成
b = [0,1,2,3,4,5,6,7,8,9] # 0..9までの要素からなるリストbを生成
c = [-1]*100              # 値が-1の100個の要素からなるリストcを生成

のように [ ] 表現し、それぞれの要素をコンマで区切る。 それを変数に代入することで、リストにラベルがつけられる。

1行目は空のリストを作成する例、2行目は0から9までの数値が入った10個の要素からなるリストを作成する例である。 3番目では、それぞれの値が-1の100個の箱を持つリストを生成している（[-1]というリストを100回繰り返す(*100)）。

リストに要素を追加するには a.append(1) のように リスト.append(データ）を用いる。最初空であったリストaは、この操作で [1] というリストになる。

リストの要素の数は len(b)で得られる（lenはlength）。上の例ではbには要素が10個あるので len(b) は 10 となる。

リストの連結

２つのリストを + によって連結することができる。

a = [1,2] 
b = [3,4,5]
d = a + b   # d には[1,2,3,4,5]がセットされる

もし、リストの末尾にリストを追加する場合は リスト.extend(追加リスト)とする：

a = [1,2] 
b = [3,4,5]
a.extend(b) # aに[3,4,5]を追加して、[1,2,3,4,5]とする

リストの要素へのアクセス

リストの中身（データ）には、通し番号（添字, index）を付け、要素ごとにアクセスする。

a[3] = 17
x[i] = x[i-1] + x[i+1] - 2 * x[i]

といった具合に、[ ] の中で何番目のハコであるかを指定する。 箱の場所は、整数値で指定しても良いし、変数や数式であっても構わない。

添字は0から始まり、要素数-1までの範囲で指定するのが基本である。 xを100個の要素からなるリストとすると、最後の箱はx[99]である†。

リストの中身をそっくりコピーする場合、

a=[1,2,3,4,5,6,7,8,9,10]
・・・
b=a

のように書いてはいけない。この場合、bはaの「別名」を表し、データそのものはコピーされない。 であるから、面倒だけれども、

a=[1,2,3,4,5,6,7,8,9,10]

・・・
b=[ ]                        # 空のリストを作成し
for i in range(0,len(a),1):  # aの要素数分、順に、
   b.append(a[i])            # bの末尾にaの要素を追加する

のように、反復処理を使って、要素毎に逐一追加（または代入）する必要がある‡。

参考：スライシング

要素を１つずつ指定するのが煩わしいケースも多いので、Pythonにはリストの一部を「切り出す」機能が用意されている。 要素指定のカギ括弧を リスト名[n:m:s] と記述すると、『要素の n 番目から m-1 番目まで s おきに』を表す。 このとき、添字がちょうど m の要素は含まれない点に注意。sを省略すると『1ずつ』と解される。 また、mを空欄にすると「最初から」、nを空欄で「最後まで」となる。 以下にいくつか例を示す：

a = [0,1,2,3,4,5,6,7,8,9,10]

b = a[0:10:2] # bに [0, 2, 4, 6, 8] をセット（10は含まない）
c = a[:5]     # cに [0,1,2,3,4] をセット（5は含まない）
d = a[5:]     # dに [5, 6, 7, 8, 9, 10] をセット
e = a[:]      # eに [0,1,2,3,4,5,6,7,8,9,10] をセット
f = a[5:-1]   # fに [0,1,2,3,4,5,6,7,8,9] をセット

最後から２番目の例のように [:]を使うと、リストを丸々コピーできるので便利である。 また、負の数は最後の要素から起算した位置、と解釈される。

範囲の指定は、要素の「間」を指していると考えるとわかりやすいかもしれない。

2. リストへのアクセスと操作

リストを使うと、アクセスする場所（添字の値）を変数や式を使って指定することで、様々なデータの処理や加工が可能となる。

次の例題は、リスト中のデータを、ひとつ「右」（添字が大きい位置）にずらし、一番「右」のデータは、 一番「左」に移動（つまりデータの位置を右向きにシフト、あるいは回転）し、結果を表示するコードの例である。

# coding: utf-8

x=[0,1,2,3,4,5,6,7,8,9]

t=x[9]
for i in range(9,0,-1):
    x[i]=x[i-1]
x[0]=t

for i in range(0,10,1):
    print(i,"番目の値=",x[i])

プログラムの見所

forループで変数 i を「カウントダウン」方式で操作している理由、変数 t が必要な理由をよく考えてみるとよい。

x=x[-1:]+x[:-1]

　練習：リストの要素のシフト

例題8aをもとにして、リストxのデータを「左」にシフトし、結果を表示するプログラムを書きなさい。

　練習：リストの内容の反転

以下に示すひな形をもとに、リストxの要素の並び順を逆転させた上で出力するプログラムを書きなさい。

# coding: utf-8

x=[9,8,7,6,5,4,3,2,1,0]

...
...
	
for i in range(0,10,1):
    print(i,"番目の要素=",x[i])

　ヒント

x=[9,8,7,6,5,4,3,2,1,0]
x.reverse()	
for i in range(0,10,1):
    print(i,"番目の要素=",x[i])

　練習：あみだくじ

左図のあみだくじの「行き先」を求めるPythonプログラムを書いてみなさい。反復処理を使うこと。結果は

0 -> 7
1 -> 0
2 -> 1
...

のように出力すること。

　ヒント

# coding: utf-8


x=[0,1,2,3,4,5,6,7]
...
...
...

for i in range(0,8,1):
   print(i,"->",x[i])

３．リスト内のデータの検索

データの中から必要なものを探し出すのは、情報を扱う上での基本である。 そして、我々はコンピュータを使って、膨大なデータの検索を、日常的に行っている。 この節では、リストを一種のデータベースに見立てて、情報の探索のいくつかの基本パターンを紹介する。

データの検索（線形探索）

# coding: utf-8

x=[12, 11, 9, 13, 8, 4, 3, 5, 6, 1]

n=int(input("検索する数値:"))

k=-1
for i in range(0,len(x),1):
    if x[i]==n:
        k=i
        break

if k<0:
    print("その数は見つかりませんでした")
else:
    print("その数は",k,"番目の位置にありました")

プログラムの見所

変数kを最初に-1にセットしておき、リスト中に入力した数値が見つかったら、その添字をkに代入しforループを抜けている。そうすると、もしkが初期値のまま（-1）であれば、 if x[i]==n:の判定が「真」とはならなかった、つまり、その数が見つからなかったことになる。もしkが0以上なら、それはデータの位置（添字の値）になっている。

# coding:utf-8
x=[12, 11, 9, 13, 8, 4, 3, 5, 6, 1]
n=int(input("検索する数値:"))
k=x.index(n)
print("その数は",k,"番目の位置にありました")

最大値・最小値

数値計算や、統計処理などを行う際に、リスト中のデータの中で一番大きな値が必要になることがよくある。 以下は、リスト中の最大値を見つけるプログラムの例である。

# coding: utf-8

x=[2.1, 5.3, 7.3, 4.7, 9.2, 1.2, 3.1, 5.3, 8.3, 4.8]

maxval=x[0]
for i in range(0,len(x),1):
    if x[i]>maxval:
        maxval=x[i]

print("最大値:",maxval)

プログラムの見所

5行目から8行目にかけてがリストの中から最大値を見つける処理で、アルゴリズムをまとめると：

1: 仮の最大値として、最初の要素の値を設定する（仮の最大値は、本当の最大値を超えない値ならば何でも良い）
2: リストの中身を順に最後まで調べる：
3: 　　もし、i番目の値が、仮の最大値より大きければ、仮の最大値としてi番目の値をセットする
4: この時点での、仮の最大値を、リスト全体を通しての最大値とする

上の手順をちょっとだけ変更すれば、最小値を見つけるアルゴリズムになる。

‡ Pythonの機能を使うと、リストの中の最大値は max(リスト)、最小値はmin(リスト)で取得できるが、ここではアルゴリズムの学習のため、敢えてひとつずつ調べる方法を紹介した。max()関数を使うと、例題8cは以下のように書き直せる。

# coding: utf-8                                                                                                                                      
x=[2.1, 5.3, 7.3, 4.7, 9.2, 1.2, 3.1, 5.3, 8.3, 4.8]
maxval=max(x)
print("最大値:",maxval)

整列済みのデータ内からの探索（二分探索）

リストの中に、ある値を持ったデータが含まれているかどうかを調べるには、添字を0から順に変えながら値を比較すればよい（線形探索）が、 データの件数が膨大になると、無視できない手間となる。 けれども、もしデータが既に（ここでは昇順に）整列済みの場合は、二分探索法(binary search algorithm)と呼ばれる、 シンプルながらも効率的なアルゴリズムが利用できる。

以下は、この二分探索を使って、キーボードから入力した数値が、リストxの中のどの区間（何番目の要素の間）に位置するかを調べ、表示するPythonプログラムの例である。 入力値を$v$とすると、$x_i \le v \lt x_{i+1}$ となるような $i, i+1$ が出力される。 このプログラムでは、N=10 件の既に昇順に整列済みのリストを用いており、 データの最小値よりも小さい$v$を入力すると [-1,0] が、最大値より大きな$v$については [N-1, N] が出力される。

# coding: utf-8

x=[ 1.2, 2.1, 3.1, 4.7, 4.8, 5.3, 5.3, 7.3, 8.3, 9.2]

val=float(input("探したい値:"))

il=-1
ih=len(x)
while True:
    if ih-il<=1:
        break
    i=(il+ih)//2
    if x[i]<=val:
        il=i
    else:
        ih=i

print("そのデータは",il,"番目と",ih,"番目の要素の間に位置します")

プログラムの見所

forループの箇所がこのコードの中心部分で、 変数ilを下端、ihを上端として、その中間位置i=(il+ih)//2でのリストの値とデータを比較し、 その大小関係に応じて、下端または上端の位置を更新している。 いわば、『挟み打ち』にする作戦である（下図）。 ここで、除算に / でなく // 演算子を使っている点に注意（整数での除算を行うため）。

# coding: utf-8
import bisect

x=[ 1.2, 2.1, 3.1, 4.7, 4.8, 5.3, 5.3, 7.3, 8.3, 9.2]
val=float(input("探したい値:"))

ih=bisect.bisect(x,val)
il=ih-1

print("そのデータは",il,"番目と",ih,"番目の要素の間に位置します")

　練習：最小値

リスト中の最大値を見つけるプログラム（例題 8c）を修正し、最小値を見つけ、出力するコードを作成しなさい。

　練習：線形探索

二分探索のアルゴリズムを使った例題8dは高速ではあるが、プログラムの動作を理解するのは少し慣れが必要かもしれない。

この課題では、最もシンプルなアルゴリズムである線形探索（リストの先頭から順にひとつずつ要素を調べるやり方）によって、入力した値が（以下に示すひな形コードの）昇順に並んだリスト中のデータのどの区間に属するかを探索する（例題8dと同様の動作をする）プログラムを作成してみなさい。

　ヒント

# coding: utf-8

x=[1.2, 2.1, 3.1, 4.7, 4.8, 5.3, 5.3, 7.3, 8.3, 9.2]

val=float(input("探したい値:"))

for i in range(...):
  ...
  ...
	
print("そのデータは",il,"番目と",ih,"番目の要素の間に位置します")

　練習：データのカウント

以下のひな形をもとに、与えられた整数のリスト(x)中に、指定した値のデータが何個含まれるかをカウントして、結果を出力するプログラムを作成しなさい。

例えば、1を検索すると3個、3を検索すると2個、5を検索すると0個、と出力するようにしなさい。

# coding: utf-8

x=[3, 1, 0, 1, 8, 1, 2, 3, 9, 4]

val=int(input("探したい値:"))
...
for i in range(...):
  ...
  ...
	
print("データ中に",val,"は",count,"個含まれています")

　ヒント

　練習：フィボナッチ数列

フィボナッチ数列は、初項を $x_0 = 1, x_1 = 1$ として、漸化式 $x_n = x_{n-1} + x_{n-2}$ $(n \ge 2)$ によって計算される数列で、数理的な問題や自然現象、造形物など、 色々な事象と関わることで良く知られている。 具体的には、1, 1, 2, 3, 5, 8, 13, 21, ... と単調に（しかも急激に）値が増大する数列となる。

以下のひな形をもとにして、リストの i 番目の要素に順に $x_i$ をセットし、$x_{29}$ までの値を出力するプログラムを作成しなさい。

# coding: utf-8


x=[1]*30

	
# xの内容を出力
for i in range(0,len(x),1):
   print("x[{0}]= {1}".format(i,x[i]))

亀場で練習：フィボナッチの正方形列

下図は、一辺の長さがフィボナッチ数列になるような大きさの正方形を並べて描いたものである。 漸化式 $x_n = x_{n-1} + x_{n-2}$ から、「２つ前までの正方形の辺の長さの和が、ちょうど次の正方形の辺の長さになる」ような関係が成り立っている。 原点（中央）から描画を開始し、図のようなパターンを描くプログラムを作成しなさい。

フィボナッチ数列の計算部分は、ひとつ上の練習問題のコード使うと良い。

　ヒント