はじめに

今回はlistなどのデータ構造の話を深めにします。

その前に

ソースファイルを分離する

適当な場所にソースファイルを書き、？？？.pyという名前で保存します。名前や保存場所は自分で決めてね。そしてWSLなどのターミナルでそのフォルダに移動し、

> python3.8 ？？？.py

でそのソースを実行します。もし対話型で起動したい時は

> python3.8 -i ？？？.py

で起動しましょう。もし対話型で起動した後にソースを読み込みたい時は

>>> exec(open("./？？？.py").read())

僕は学習環境としては対話モードが優れていると思っているので対話型をオススメしますが、各々の環境は各自に任せます。

WSLはフォルダ階層が複雑になるのでアレです。

その他

対話型で1個前のコマンドを実行したい時は↑キーを、なんかいい感じに補完して欲しい時はTABキーを押しましょう。これはWSLのターミナルでも有効です。

今後「こういう書き方って許されるのかな？」「こう書くとどんな結果になるんだろう？」って思う事はそこそこあると思います。そういう時は自分でサクッと書いてみましょう。こういう陽に説明されない知識は役に立つので。

List

よく使うメソッド関数を列挙します。

>>> d = [1, 2, 3, 4, 5]

listのdを定義したとします。

基本的にListでi番目の要素にアクセス(これをランダムアクセスと言います)するにはO(i)かかります。なので特定の要素をゴニョゴニョする処理はO(n)かかって遅い事に注意しましょう。これはどの言語でもそうです。しかし、全体に対する操作はキレイに書くことができるので便利です。関数型プログラミングでもよく使う。

ランダムアクセスが必要ならarrayなどメモリ領域が連続しているデータ構造か特定の用途に特化した強いデータ構造を使いましょう。しかし、柔軟性は下がります。例えばi番目を削るとかの処理はその後の要素を全部移動させなければならないためO(n)です。

関数型プログラミングではmapやfilterなどの高階関数を多用します。

>>> squares = list(map(lambda x: x * x, range(10)))
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

イメージとしてはrange(10)で[0, 1, ..., 9]を作って、mapでそれぞれの要素を2乗する関数をかける感じです。しかし、PythonならListを生成する時もっと簡単に書く事ができます。

>>> squares = [x*x for x in range(10)]

恐らくこちらのほうが読みやすく感じるのでは無いでしょうか。これをリスト内包表現と呼びます。これにはifも書く事ができます。

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

より複雑な例を

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]
>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

行と列を入れ替えていますね。

集合型

集合を管理します。以下の様に書くかset()関数を使いましょう。

>>> d = {1, 2, 3, 5, 6, 9}
>>> even = {x for x in range(10) if x % 2 == 0 }
>>> d - even
{1, 3, 5, 9}
>>> d | even
{0, 1, 2, 3, 4, 5, 6, 8, 9}
>>> d & even
{2, 6}
>>> d ^ even
{0, 1, 3, 4, 5, 8, 9}
>>> 1 in d
True
>>> 8 in d 
False

集合に要素が存在するかはO(log n)で判別できます。

辞書型

Key => Valueの辞書を作ります。dict()関数でも作れます。

>>> d = {1: 10, 'a': 'ddd'}
>>> d[1]
10
>>> d['a']
'ddd'
>>> 1 in d
True
>>> 0 in d
False
>>> {x: 2*x for x in (3, 4, 8)}
{3: 6, 4: 8, 8: 16}

inでkeyが存在するかをO(log n)で判定できます。keyとvalueそれぞれの型は違っても構いません。こういう事ができるのは動的型付け言語の醍醐味。

ループテクニック

dict型のfor文

items()メソッドでループを回せる

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

enumerateでインデックス取得

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

その他

sorted()関数やreversed()関数を使うとそのようなlist(厳密にはイテラブル)を返す。元のlistを破壊しない。

あーと代入は

a, b = 2, 3

と書ける。例えばswapも

a, b = b, a

と書ける。

練習問題

• リスト内包表現を用いて、引数nを受け取りn×nの単位行列のlistを返す関数を作って下さい。
• 2つの行列を受け取り掛け算した行列を返す関数を作って下さい。
• n要素のリストdが与えられる。各要素に対して同じ要素の個数を表示しろ。(但しn <= 10^5とする)