第2回 - リストについて補足、計算量の理論、Big O 記法

0. 前回の復習
   • 演習 2-1. 再帰的な関数
1. Python のリストについて補足
   • 「参照」という考え方
     • 演習 2-2. リストの参照
   • 「スライス」とは
     • 演習 2-3. リストのスライス
   • 二次元リスト
     • 演習 2-4. 二次元リストの練習
2. 計算量の理論とは
   • 演習 2-5. 計算量の予想
   • Big O 記法とは
     • 演習 2-6. 関数の序列
   • プログラムの計算量をあらわす
     • 演習 2-7. 隠れた計算量
3. ブレイクアウトルーム練習
   • 演習 2-8. リストのリストを使った演習
4. 本日の課題
   • 小課題2. リストのリストを使った図形描画 (12月20日締切)
   • チャレンジ課題A. すべての組合せを表示する (12月27日締切)

雑談

社会人になると、おカネについての知識は 英語やプログラミングと同じくらい重要になる:

• 「大学の設備・サービス・先生はなぜこんなにヘボいのか?」 → 「お金がないから」
  「国の設備・サービス・役所はなぜこんなにヘボいのか?」 → 「人が足りないから」 = 「お金がないから」
  
• ある組織・企業が、どのくらいの金をどのように使っているかを知ることは重要だ。
  とくに重要な書類は 2つ:
  • 貸借対照表 (現在の持ち物をあらわす)
  • 損益計算書 (過去1年間の増減をあらわす)
• 上場企業・大学では、こうした情報はすべて公開されている:
  • 東京工業大学 (学生数:1万人, 教員:1500人):
    • 資産: 2300億円 (現金: 150億円 - 「流動資産」)
    • 収入: 450億円 (交付金: 200億円, 企業: 100億円, 授業料: 47億円)
    • 支出: 430億円 (人件費: 210億円, 施設費: 120億円)
    • 収入 - 支出 = 20億円儲かっている。
  • 早稲田大学 (学生数:5万人, 教員:5500人):
    • 資産: 3900億円 (現金: 320億円)
    • 収入: 1000億円 (学費: 650億円, 補助金: 120億円)
    • 支出: 940億円 (人件費: 490億円, 施設費: 400億円)
• 秘密が多い組織 (例: 大学入試センター) などでも、 おカネの出入りを見ればだいたいどんなことを計画しているかわかってしまう。
• 会計に関する知識 (e.g. 日商簿記など) は持っておいて損はない。

0. 前回の復習

• Pythonでコマンドラインから引数を利用する方法を学習した。
• 再帰的な関数を書く方法を学習した。
  • ケンタウロス = 半分は馬、あとの半分は人間。
  • 再帰的ケンタウロス = 半分は馬、あとの半分は再帰的ケンタウロス。
  • 再帰的自己描画 (実はフーリエ変換の説明)

1. Python のリストについて

1.1. 「参照」という考え方

第一の最後の授業で、 「文字」や「画像」といった概念がじつは幻想にすぎないことを説明した。 実際にはコンピュータの記憶装置は箱の羅列のようなもので、 原始的な命令で扱えるのデータは 8ビットか、せいぜい64ビットまでである。

• 数値とか、True / False などのデータ型は 64ビットあれば扱える。
• 文字列とか、リストとかは普通これよりも大きくなるので、1回の命令では扱えない。

Python を含む、ほとんどのプログラミング言語では この事実を微妙にごまかしている。

整数型の場合

整数・小数型のデータは小さいので、 これらのデータを変数に代入した場合、 メモリ上のデータが本当に移動・コピーされる。

a = 3
b = a       # 変数 a の値が変数 b にコピーされる。
b = b + 1   # b に1を足す。
print(b)    # "4"
print(a)    # "3"

リストの場合

しかし文字列型やリスト型のデータは大きすぎるので、 これらは一度、メモリ上に作成されたら動かさず、ひとつのものを共有する。 つまりこれらのデータは不動産として扱われるのである。

a = [5,9,4,0,7,3]
b = a        # 変数 a の値が変数 b にコピーされる。
b[0] = 1     # b[0] に 1を代入。
print(b)     # [1,9,4,0,7,3]
print(a)     # [1,9,4,0,7,3] … ???

リスト型の場合、変数 a や b には データそのものが入っているのではなく、そのデータへの参照 (アドレス) が入っていると考える。実際のリストは、変数の外に存在する。

以下の代入文

b = a

(注意: この名前は新山が勝手に考えたもので、一般的ではない)

関数呼び出しにリストを渡す場合

「リストの参照をコピーする」という考えは、 とくに関数呼び出しのときに重要である。 たとえば、ふつうの関数呼び出しでは引数の値 (整数) は コピーされるため、以下の例では関数 assign() 呼び出し後でも 変数 a の値は変わらない:

# ふつうの関数
def assign(x):
    x = 999
    return

a = 123
assign(a)
print(a)     # 123

ところが、以下の例では関数 destroy() には リストの参照がコピーされるだけで、リストはひとつである。 destroy() は x で参照される リストの 1番目の要素に 999 を代入する。このような場合、 関数に渡したリスト a の値が変わってしまう。 このような処理を破壊的な操作とよぶ。

# 破壊的な関数
def destroy(x):
    x[1] = 999
    return

a = [0,1,2]
destroy(a)
print(a)     # [0,999,2]

同じリストを2度作成する

リストは [5,9,4,0,7,3] などという式を評価した時点で 作成される。つまり、リストが2度書かれている場合、 a, b は実際に別々のリストとなり、 不動産の法則は成りたたない:

a = [5,9,4,0,7,3]  # 新しいリストが作成される。
b = [5,9,4,0,7,3]  # 新しいリストが作成される。
b[0] = 1     # b[0] に 1を代入。
print(b)     # [1,9,4,0,7,3]
print(a)     # [5,9,4,0,7,3]

この場合、メモリの内容は次のようになっている:

リストを本当にコピーする

しかし、どうしても本当にデータをコピーしたい時もある。 このような場合は .copy() を使う。 (見慣れない構文だが、この方法は後日解説)

a = [5,9,4,0,7,3]
b = a.copy() # 変数 a のリストが実際にコピーされる。
b[0] = 1     # b[0] に 1を代入。
print(b)     # [1,9,4,0,7,3]
print(a)     # [5,9,4,0,7,3]

a.copy() を実行すると内部で for文のようなものが実行され、 各要素がコピーされるため、そのぶん時間がかかる。 これは、以下のようにしてみるとわかる。

a = [0]*100000000  # ゼロが1億個の入ったリスト。
b = a              # リストの参照のコピー (一瞬で終わる)。
...
c = a.copy()       # リスト全体のコピー (時間がかかる)。

ちょっとした小技 : リストの要素のくり返し

Pythonの特別な書き方として、リストに代入する際

a = [0,0,0,0,0,0,0,0,0,0]

a = [0] * 10

1.2. 「スライス」とは

たとえば、以下のようなリストがあるとする:

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

この場合、aの部分列は、以下のようにして取り出せる (このような操作を、リストのスライスという) :

なお、リストをスライスした場合、もとのリストは変化しない。 リストのスライス内の要素はもとのリストと共有されておらず、 つねに新しいリストである。

#   0    1    2    3    4    5    6    7    8
s = ["H", "E", "A", "D", "A", "C", "H", "E"]

1.3. 二次元リスト

Python では、リストの中にさらにリストを入れることができる。 この機能を使うと、あたかもリストを二次元のリスト (行列) のように扱うことができる。 (この機能は第一の 小課題 8 で ひそかに使っていた)

m = [[5, 9, 4], [0, 7, 3]]
a = m[0]        # m の 0番目の要素 (リストの参照) をaにコピー
print(a)        # [5,9,4]
print(a[2])     # 4
b = m[1]        # m の 1番目の要素 (リストの参照) をbにコピー
print(b)        # [0,7,3]
print(b[0])     # 0

さらにこれは短縮して以下のように書くことができる:

print(m[0][2])  # 4
print(m[1][0])  # 0

実は「リストの中にリストが入る」というのは正しくない。 実際に入っているのは「リストの参照」であるので、 正しくは「リストの中にさらに『リストの参照』が入る」というべきである。 これを図に表すと以下のようになる:

参照ということは、つまり破壊的な操作が可能ということを意味する。 たとえば

a = m[0]        # m の 0番目の要素 (リストの参照) をaにコピー
a[2] = 8        # a の 2番目の要素を 8 に変更
print(m[0][2])  # 8

あるいはもっと簡単に

m[0][2] = 8     # (m の 0番目の要素) の 2番目の要素を 8 に変更
print(m[0][2])  # 8

二次元リストの初期化

1次元の場合は、たとえば n個の要素をもつリストを作成するのに

a = []
for i in range(n):
    a = a + [0]

m = []
for i in range(n):
    a = []
    for j in range(n):
       a = a + [0]
    m = m + [a]

m = []
for i in range(n):
    a = [0]*n
    m = m + [a]

m = []
for i in range(n):
    m = m + [[0]*n]

注意: 以下の方法はうまく動かない。なぜか考えよ。

m = [[0]*n]*n   # ダメ

2. 計算量の理論とは

同じく 第一の最後の授業で、 すべてのコンピュータは原始的な命令の組み合わせだけで動作することを説明した。 コンピュータ上で「Pythonのプログラムが動く」ように見えるのも、 じつは幻想である。本来、コンピュータでは原始的な (ネイティブ) 命令だけを使ったプログラムしか動かない。 Pythonのプログラムが実行されているように見えるのは、 「Pythonプログラムを実行する」ような架空の演算装置を エミュレータ (仮想機械) として動かしているからである。 このエミュレータ自身はネイティブ命令だけを使って書かれている。

Pythonに限らず、すべてのコンピュータ上のプログラムは 演算装置上でネイティブ命令を 1つずつ実行することにより動作する。

現在のコンピュータでは:

• 動作周波数が 1GHz の場合、1秒間に約1ギガ個 (= 1,000,000,000個) のネイティブ命令を実行可能。
• メモリが 1Gバイト の場合、約1ギガ個 (= 1,000,000,000個) の8ビットの数値を格納できる。

計算量の理論の大原則は非常に単純である:

たとえば

a = 1

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

同様に

a = [0] * 20

b = [0] * 2000

計算量の理論で厄介なのは、じつはこうした操作に 「隠れた」実行時間・メモリ使用量があることである。 たとえば

b = [0] * 2000

b = []
for i in range(2000):
    b = b + [0]

計算量の理論は、こうしたプログラムの「隠れた」実行時間・メモリ使用量を 細かく計算し、最終的に以下のような質問に答えるのが目的である:

たとえば 前回の 2進数 (0 と 1) の組み合わせをすべて出力する関数 combo で n=100 とすると、 これは1秒間に 1ギガ個の組み合わせを表示できたとして

2.1. Big O 記法とは

関数には序列 (オーダー, order) というものがある。

• x-1 と x² を比べると、xが正のときは x² のほうが大きくなる。

  → したがって、x² のほうがオーダーが大きい。

• x+100 と x² を比べると、最初は x+100 のほうが大きいが、 x=11 以降は x² のほうが大きくなる。

  → したがって、x² のほうがオーダーが大きい。

• 99999x+99999 と x² を比べると、最初は 99999x+99999 のほうが大きいが、 どこかで x² のほうが大きくなる。

  → したがって、やはり x² のほうがオーダーが大きい。

同様に…

• x² と x³ を比べると、 x³ のほうがオーダーが大きい。
• 100x²+123x+456 と 0.01x³ を比べると、 0.01x³ のほうがオーダーが大きい。

さらに…

• x² と 2^x を比べると、 2^x のほうがオーダーが大きい。
• x¹⁰⁰ と 2^x を比べると、 2^x のほうがオーダーが大きい。
• x^なんとか と 2^x を比べると、 つねに 2^x のほうがオーダーが大きい。

ちなみに、O(x) より小さいオーダーの関数もある。

数学的に厳密な定義は以下のとおり:

2.1. プログラムの計算量

Big O 記法は、あるアルゴリズム (プログラム) の計算量や メモリ使用量を表すのによく使われる。

def sum(n):
    s = 0
    for i in range(n):
        s = s + (i+1)
    return s

この関数 sum(n) は、与えられた値 n に対して n回の同じ処理を繰り返すので「O(n) オーダーの計算量をもつ」ということができる。 いっぽうでこの関数は変数を1つしか使っていないので、 メモリ使用量はつねに一定 O(1) である。

def fill(n):
    a = [0] * n
    return a

注意

「オーダー」という考え方は、(定数要素によって左右される) 実際の計算時間を 考えなくてよいので便利であるが、計算量のオーダーが小さいからといって、 かならずしも実行時間が短いわけではないことに注意! たとえば以下の関数 doit() は実行時間がかかるが、 その計算量は O(1) である。(ループの回数が入力値 n に比例しないため)

def doit(n):
    s = n
    for i in range(1000000000):
        s = s + (i+1)
    return s

• 注: Wikipedia では 「計算量」「メモリ使用量」はそれぞれ 「時間計算量」「空間計算量」と書かれているが、 この授業ではよりカジュアルな言葉を用いることにする。

3. ブレイクアウトルーム演習

ブレイクアウトルーム演習の方法:

1. ブレイクアウトルーム中はカメラを使うこと。
2. まず自己紹介をする。名前・所属・趣味などを簡単に説明する。
3. 最初の問題をやる担当者を決める。 その人が自分の PC の画面共有をおこない、課題のプログラムを考えながら書く。 このとき周囲の人は手助けすること。
4. 終わったら、次の担当者が次の問題をやる。これを繰り返す。
5. 授業終了の5分前にブレイクアウトルームを終了させるので、 それまでに全問題を終わらせる。

# grid.py
m = [[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
m[0][0] = 1
m[1][1] = 1
m[2][2] = 1
m[3][3] = 1
m[4][4] = 1
for i in range(len(m)):
    print(m[i])

4. 本日の課題