TIM Labs

2016年12月アーカイブ

そろそろ年末なので、Pythonの内容も正月らしいというか、遊びを取り上げよう。
ナンプレ(数独)のブームが来てから約10年が経過し、問題を人工知能を使って自動生成するのが普通になった。しかし、そのあたりを説明しだすと長くなるので、AIを使った自動生成の話は止める。

Pythonで、リストではなく、集合や辞書を多用して問題を解くことをやってみようと思う。
要するに、世の中であまりやっていないと思われる方法で解いてみよう。
実はこの方法の方が汎用性があり、抽象度を高くすることで、多種多様なナンプレのバラエティにも対応できる。

とりあえず、問題を用意した。以前学研の『IQナンプレ300vol.2』の表紙になった問題である。


IQNumPlay300V2 (141x200).jpg       num18sym.png

この問題を、以下のようにして解こうと思う。
問題の数字(ヒントという)は、数字の入っているマスを[x,y,n]の形の長さ3のリストで表す。
すると、問題全体は、このリストが数字の個数あれば表現できる。

以下のプログラムでは、リストhintに問題データを与えている。
もっと便利なインターフェイスを作るべきだが、問題を解くことと本質的に関係ないので、とりあえずこの形にしておく。

問題をあれこれ調べるために問題盤面が欲しいので、問題を示すhintを与えてBoardオブジェクトを作ると、Boardオブジェクトは初期化された状態になっている。
bd.print()により、現状の盤面が表示されるので、以下では問題そのものが表示されるはず。

次に、初期化状態のBoardオブジェクトを与えてSolverオブジェクトを作り、solve()メソッドで問題を実際に解く。

こんな感じになるといいな。

NumPlace.py

def main():
    hint = [[1,0,1],[1,1,2],[1,2,3],[2,3,4],[2,4,5],[2,5,6],[3,6,5],[3,7,6],[3,8,7],
            [5,0,2],[5,1,3],[5,2,4],[6,3,3],[6,4,4],[6,5,5],[7,6,6],[7,7,7],[7,8,8]]
    bd = Board(hint)
    bd.print()                       # 問題のプリント

    Solver(bd).solve(0)

main()
これを実行すると、
Labs$  python NumPlace.py

_ 1 _ _ _ 2 _ _ _ 
_ 2 _ _ _ 3 _ _ _ 
_ 3 _ _ _ 4 _ _ _ 
_ _ 4 _ _ _ 3 _ _ 
_ _ 5 _ _ _ 4 _ _ 
_ _ 6 _ _ _ 5 _ _ 
_ _ _ 5 _ _ _ 6 _ 
_ _ _ 6 _ _ _ 7 _ 
_ _ _ 7 _ _ _ 8 _ 

4 1 7 8 5 2 6 3 9 
5 2 8 9 6 3 7 4 1 
6 3 9 1 7 4 8 5 2 
1 7 4 2 8 5 3 9 6 
2 8 5 3 9 6 4 1 7 
3 9 6 4 1 7 5 2 8 
7 4 1 5 2 8 9 6 3 
8 5 2 6 3 9 1 7 4 
9 6 3 7 4 1 2 8 5 
となって欲しい。

 次回は、Boardクラスを作ろう。
Pythonには、数学の集合と同様の動きをする集合(set)が用意されている。
要素の個数に特に制限はなく、要素に順序もない。
もちろん要素の個数が増えれば、そのぶん集合のサイズが増加するはずだが、サイズを調べるとなかなか不思議な増え方をする。
>>> import sys
>>> a = set()
>>> sys.getsizeof(a)
224
>>> a = {1,2,3}
>>> sys.getsizeof(a)
224
>>> a = {0,1,2,3,4,5,6,7,8,9}
>>> sys.getsizeof(a)
736
空集合でも224バイトもある。 要素をいくつか追加しても、サイズは変化しない。 でも、あるとき、急にサイズが増えるようなのだ。 集合のサイズの増え方を調べるために、以下の実験をした。

sizeofset(n)は、最初に空集合をつくり、その後集合に数字を1つずつn個になるまで追加する。
そのとき、直前のバイトサイズよりも大きくなったときに、集合の要素数とバイト数を表示するようにした。

>>> def sizeofset(n):
...     a = set()
...     pvbsz = sys.getsizeof(a)
...     print('{0:10d}  {1:10d}'.format(len(a),pvbsz))
...     for i in range(1,n):
...         a.add(i)
...         bsz = sys.getsizeof(a)
...         if pvbsz != bsz:
...             print('{0:10d}  {1:10d}'.format(len(a),bsz))
...             pvbsz = bsz
... 
>>> sizeofset(10000000)
         0         224
         6         736
        22        2272
        86        8416
       342       32992
      1366      131296
      5462      524512
     21846     2097376
     87382     4194528
    174763     8388832
    349526    16777440
    699051    33554656
   1398102    67109088
   2796203   134217952
   5592406   268435680
これを見ると、サイズが6,22,86,342,...になったy瞬間に集合のバイトサイズが増えている。
87382個までは、大きくなるときには約4倍ずつ大きくなり、それ以上では約2倍ずつ大きくなっている。

大きくなった集合の要素を消していくと、集合のバイトサイズはどうなるだろうか。
実験ではこんな結果になった。


>>> a = {i for i in range(10000000)}
>>> sys.getsizeof(a)
268435680
>>> for i in range(10000000):
...     a.discard(i)
... 
>>> a
set()
>>> sys.getsizeof(a)
268435680
要素数1000万個の集合を作ってサイズを求め、次に要素を全部消した。
集合はset()と表示されたので空集合になっている。
しかし、サイズは要素数1000万個のときと同じであり、巨大な空集合ができてしまった(トホホ)。

一度大きくなった集合は、要素がいくら少なくなっても小さくならない。
気をつけなければ。
Pythonには複数のデータを扱うのに、リストだけでなく集合(set)もある。
今回は、集合にいっぱい要素を突っ込んだり消したりしたときの速度を調べてみる。
空集合を作り、自然数を1から10,000,000まで1000万個を突っ込んでみた。

>>> import time,os,psutil,sys
>>> pid = psutil.Process(os.getpid())
>>> 
>>> b = set()
>>> sz0 = pid.memory_info().rss
>>> t0 = time.time()
>>> for i in range(1,10000001):
...     b.add(i)
... 
>>> time.time() - t0, pid.memory_info().rss-sz0
(2.310807466506958, 592703488)
2.3秒/1000万個=0.23マイクロ秒/個のペースで追加できている。 そして、メモリは592MB消費したようだ。

同じことを内包を使って実行してみる。
>>> b = set()
>>> sz0 = pid.memory_info().rss
>>> t0 = time.time()
>>> b = {i for i in range(1,10000001)}
>>> time.time() - t0, pid.memory_info().rss-sz0
(0.6817171573638916, 592707584)
0.60秒/1000万個=0.06マイクロ秒/個で、4倍近く高速になっている。
でも1000万個追加するのに、前回のリストのときには0.36秒だったので、集合への追加はリストのアペンドに比べて倍近く時間が掛かっていることが分かる。
集合は、もし同じものがあったら追加されないので、そのあたりの判定も必要になる。

さて、追加だけでなく、削除もやっておこう。
集合の削除メソッドには、remove(x)とdiscard(x)がある。
discardは要素xが存在しなくてもエラーにはならず無視されるだけだが、removeではKeyErrorが発生してしまうので気をつけよう。
>>> sz0 = pid.memory_info().rss
>>> t0 = time.time()
>>> for i in range(10000000,0,-1):
...     b.discard(i)
... 
>>> time.time() - t0, pid.memory_info().rss-sz0
(2.336066484451294, -324263936)
>>> b
set()
消すのは、内包を使わないadd()とほぼ同じ時間かかることが分かった。

ということで、予想通り、集合でも内包を使った方が遥かに高速になるのであった。
100以下の偶数の自然数からなる集合 を考えよう。
Pythonではなく、数学的にはどう表現するであろうか。

{2,4,6,8,...100}
これでも良いのだが、ちょっと...という部分が気になる。これを、内包表記に書き換えると、
{ x | x は自然数で偶数かつx≦100 }
と表記できる。 | の左側に 元を書き、| の右側に条件を書く。

上記は数学での内包の説明である。
内包の英語は comprehension で、本来「理解」という意味なのだが、数学用語としては「内包」というのがある。

Pythonの場合、集合だけではなく、リスト、辞書にも使える。
次のコードは、1から1000万までの数をリストに順番に入れる。
a = []
for i in range(1,10000001):
    a.append(i)
これの実行時間を以下のようにして計測した。
>>> import time
>>> a = []
>>> t0 = time.time()
>>> for i in range(1,10000001):
...     a.append(i)
... 
>>> time.time() - t0
2.0536093711853027
約2秒かかっている。

次に、同じリストを内包を使って作ってみた。
>>> a = []
>>> t0 = time.time()
>>> a = [i for i in range(1,10000001)]
>>> time.time() - t0
0.3618910312652588
最初の a = [] は、前の測定と同じ条件にするために入れた。

結果は、内包を使うことで、2.05秒が0.36秒になり、5倍以上高速になったようだ。
内包にすることで、短くなり、速度も上がるようなので、内包が使える場合にはどんどん使った方が良さそうだ。

ということで、もっと内包についてネチネチ調べていこう。
Pythonでは、数値もオブジェクトである。そのため、相当無駄にメモリが使われてしまうことが分かった。
要するに、Pythonでいっぱい計算するのは、メモリ浪費があるから気をつけなければならない。
しかし、Pythonがよく使われるDeep Learningなどでは、大量の数値データを扱うのが普通だ。それも浮動小数点数になるので、全て別々のオブジェクトになる。

と考えると、PythonはAIには全然向いていない。
でも、良く使われている。

といっても、素のPythonを使うことはなく、PythonにNumPyをインポートし、さらに色々なものをインポートして使う訳だ。
そもそも、Pythonにはリストはあっても配列がない。そして、リストは、その性格上遅い。

ということで、NumPyの配列がどのくらいメモリを食うか調べてみる。
前回と同じサイズで、1000万要素の配列を作って調べた。

>>> import os,pusutil,numpy
>>> current_process = psutil.Process(os.getpid())
>>> import os, psutil, numpy
>>> current_process = psutil.Process(os.getpid())
>>> sz0 = current_process.memory_info().rss
>>> a = numpy.array([i for i in range(10000000)])
>>> sz1 = current_process.memory_info().rss
>>> sz1-sz0
80531456
最初に必要そうなものを全部importした。
numpy.arrayに、要素数1000万個のリストを渡して配列を作った。
渡した巨大なリストは、用済みになった時点で消えるはずである。
メモリ使用量は 80531456バイトであり、1要素あたり8バイト強しか増えていない。

さらに確認のため、配列オブジェクトについて調べてみる。

>>> type(a)
<class 'numpy.ndarray'>
>>> sys.getsizeof(a)
80000096
ちゃんとnumpy.ndarrayという型になっており、1000万要素の配列のバイト数は、8000万96バイトになっている。余分の96バイトは、配列オブジェクトの管理用などに使われていると思われる。


Pythonのリストでは、1要素あたり40バイトも増えていたのが、実際のデータのサイズと思える8バイトだけの増加になっている。
このことから、NumPyの配列では、数値自体はオブジェクトになっていないと言える。
つまり、C言語などと同じように、配列に直接数字が入っているのだ。
前回の実験で、同じ数字が別オブジェクトになるとしか考えられない実行結果が得られた。
今回は、それをきちんと確認しよう。
>>> a=123
>>> b=a
>>> c=123
>>> print(id(a),id(b),id(c))
140552436779360 140552436779360 140552436779360

数値のIDを調べるのに、一々変数に入れているが、これが重要なのだが、それについては後で説明する。 123をaとcに代入している。さらに、aをbに代入しているのだが、123の場合、a,b,c のIDは全て同じになっている。 次に、もうちょっと大きな数字として、12345で実験してみた。
>>> a=12345
>>> b=a
>>> c=12345
>>> print(id(a),id(b),id(c))
140552437718544 140552437718544 140552438458512
aとbはちゃんと同じIDになっているのだが、cのIDは異なる。 つまり、a, bの指すオブジェクト12345と、cのオブジェクト12345は異なっている。 これはどう考えれば良いだろうか? 小さい数の場合は、同じ整数値なら同じ整数値オブジェクトになるが、大きな値は違うようだ。 これをきちんと確認してみるために、次のプログラムを実行してみた。
>>> a = [i for i in range(100000)]
>>> b = [i for i in range(100000)]
>>> for i in range(100000):
...     if id(a[i])!=id(b[i]):
...         print(i, id(a[i]), id(b[i]))
...         break
... 
257 140552437718480 140552398636944
どうやら、256までは同じ整数オブジェクトで、257以上の場合、別の整数オブジェクトが生成されてしまうようだ。 これが、メモリを食っていた原因のようだ。

実数の場合にどうなるかを試してみた。
>>> a=1.0
>>> b=a
>>> c=1.0
>>> print(id(a),id(b),id(c))
140552438575488 140552438575488 140552438575512
実数の場合、1.0でも異なる実数オブジェクトが確保されるようだ。 ということは、実数データが大量にあると、すべて別オブジェクトになってしまうので、メモリを食い潰す可能性があるので要注意だ。 さて、最後に、変数に代入してからIDを調べていたが、もし変数に代入しないでIDを求めるとどうなるか試してみた。
>>> id(1234567890)
140552438458512
>>> id(123456789)
140552438458512
>>> id(1234567)
140552438458512
>>> id(123456)
140552438458512
数値が異なるのに、今度はIDが全部同じになっている。
なぜ?
説明は省略するので、自分で考えよう。

SICP読書会 2.3.4 - ...

概要

弊社では SICP の勉強会を行っています. 近頃は社外の方にも参加いただいており, 本記事では SICP読書会 2.3.4 - ... の会で解いた問題の解答例を紹介します.

前置き

読書会では 2.3.4 例: Huffman符号化木 の途中から読み進めました.

ここで話題となるHuffman符号とは, 文字列をビット列に変換する仕組みの一つです. 通常のエンコードでは1文字を同じビット数で表す固定長符号を使用するところ, Huffman符号では可変長符号を扱います. 出現頻度の高い文字を短いビット数で, 頻度の低い文字を長いビット数で表すことでデータ量を圧縮することが期待されます.

Huffman符号ではHuffman符号化木と呼ばれる二進木を用いて文字列のエンコードを行います. 今回解いた問題2.69から問題2.72では, このHuffman符号化木の生成方法および文字列のエンコード, デコードがテーマとなっています.

Pythonは、整数もオブジェクトになることが分かった。
今回は、要素が整数の長大なリストを作って、メモリがどのように消費するかを調べてみる。

個々のオブジェクトのバイトサイズは sys.getsizeof( <オブジェクト> ) で求まることは既に説明した。
今回は、プロセスのメモリがどういう状態になっているかを調べてみよう。

今まで、ipython3 を使って説明していたが、今回は python3 で説明する。ipythonの方が対話性能を頑張っている分、余計にメモリを食ったり、もろもろのことがあるので、よりシンプルなpython3で実験する。

>>> import os
>>> os.getpid()
15896
次に、psutilをインポートし、pidからカレントプロセスのオブジェクトを作る。
>>> import psutil
>>> current_process = psutil.Process(os.getpid())
これで、プロセスの様々な情報を得る準備ができた。 今回はメモリに注目するので、プロセスのmemory_info()を使う。 それでもたくさんの情報が出てきてウザイので、rssだけを表示しよう。
>>> current_process.memory_info()
pmem(rss=12869632, vms=70696960, shared=5763072, text=4096, lib=0, data=6778880, dirty=0)
>>> current_process.memory_info().rss
12869632
ここまでが準備だ。
プロセス関連の情報を得る方法を知っていると、色々便利なので、いざという時に使えるようになっておくことは重要だ。 さて、では巨大なリストを作ってみよう。とりあえず、0が10000000個(1千万個、10M個)のリストを作ろう。 作る前と後で、使用メモリサイズを計測する。
>>> sz0=current_process.memory_info().rss
>>> a = [0]*10000000
>>> sz1=current_process.memory_info().rss
>>> sz1-sz0
80326656
要素数10Mのリストを作って、使用メモリが80MB増加しているので、1要素あたり8バイト増加していることになる。リストの中身は全部0なので、同じ0オブジェクトが使われている訳で、整数のオブジェクトは1つ作られただけで、消費メモリに影響しない。

次に、全て違う値を入れてみよう。
>>> b = [i for i in range(10000000)]
>>> sz2=current_process.memory_info().rss
>>> sz2-sz1
405139456
10M個に対して約400MB増加しているので、1要素あたり40バイト増加したことになる。 リストの要素自体のサイズは8バイトなので、整数オブジェクトのサイズは32バイトのようだ。
>>> c = [i for i in range(10000000)]
>>> sz3=current_process.memory_info().rss
>>> sz3-sz2
405295104
bと同じ内容のリストcを作って、ほぼ同じ400MB増加した。 あれ、bとcで使われている整数はまったく同じだから、cを作るとき、新たな整数オブジェクトを用意する必要はないので、リストaと同じ80MB程度しか増えないはずでは? はて、何が起きているんだろう。
どうやら、数もオブジェクトのようだ。 
ならば、そのオブジェクトのバイト数を調べることができるのでは。

ということで調べたら、 sys ライブラリの中に getsizeof(オブジェクト) が用意されていたので、1のサイズを求めてみた。

In [1]: import sys

In [2]: sys.getsizeof(1)
Out[2]: 28
しかし、結果は28バイト。なんだかやらたに大きい。

In [67]: for obj in [[],[1],[1,2],(),(1,2),{},{1},{1,2},{'a':1},{'a':1,'b':2}]:
   ....:     print(sys.getsizeof(obj),'\t',obj)
   ....: 
64 	 []
72 	 [1]
80 	 [1, 2]
48 	 ()
64 	 (1, 2)
288 	 {}
224 	 {1}
224 	 {1, 2}
288 	 {'a': 1}
288 	 {'a': 1, 'b': 2}
どうやら、数字を1つ増やすごとに8バイト増えるようだ。 空リストは64バイト、空タプルは48バイト、{}は空集合ではなく、空辞書になるようだ。 そして、集合や辞書は、要素数に比例して大きくなるのではなく、たぶん階段状に増えていくものと予想される。

Pythonでは何でもオブジェクトになり、オブジェクトは単にデータが入っているだけではなく色々な物、仕掛けを隠し持っていて、そのためにサイズが増えているようだ。仕掛けの中には、ガーベッジコレクションも含まれているはずだ。

ここまでは、何でもオブジェクトにしたためと思われるので納得できる。

次に、文字列について調べた。
In [70]: for obj in ['','a','ab','abcdefghi','漢','漢字','?','+','+-*/']:
   ....:     print(sys.getsizeof(obj),'\t',obj)
   ....:
49      
58      a
51      ab
58      abcdefghi
76      漢
78      漢字
50      ?
50      +
53      +-*/
'a'は58バイト、'ab'は51バイト。
同じ1文字でも、アルファベットは58バイトで、記号は50バイトのようだ。
この不思議はどう考えればよいのだろうか。
前回、
B = [[]]*6
による繰り返しは、結局同じものを指していたのだが、実際に値を入れて変になることで確認した。 今回は、もっと便利な、明白な方法で調べる。
Pythonは何でもオブジェクトにしてしまう。本当に何でもなのだ。それをちょっとだけ実験する。

id(オブジェクト)なる関数があり、引数に何でも良いから入れると、そのオブジェクトID(識別子)を返してくる。
これを使って、調べてみよう。
In [4]: B = [[]]*6

In [5]: print("%0x\n%0x\n%0x"%(id(B[0]),id(B[1]),id(B[5])))
7f7817d2e5c8
7f7817d2e5c8
7f7817d2e5c8
まったく同じIDなので、[]のオブジェクトは1つしか無いことが分かった。

Pythonのオブジェクト、とくにリストは、リストの中にリストを自由に入れられ、複雑な構造も表現できる。
しかし、こういうオブジェクトをちゃんとコピーすることを考えよう。

Pythonでオブジェクトをコピーする方法がいくつかあるので、その比較実験を行ってみる。

import copy

A = [1,[2,[3,[4]]]]
B = A
C = A.copy()
D = copy.copy(A)
E = copy.deepcopy(C)
これで、元のオブジェクトAと、色々な方法でコピーしたB,C,D,Eが揃った。 ==で等しいかどうかチェックしてみた。
In [29]: A==B,B==C,C==D,D==E
Out[29]: (True, True, True, True)
同じである。
といっても、これは見かけだけの可能性があるので、IDを調べよう。
In [30]: print("%0x\n%0x\n%x\n%x\n%x\n"%(id(A),id(B),id(C),id(D),id(E)))
7f78179aeb08
7f78179aeb08
7f78179b4608
7f78179b0fc8
7f78179efc08
AとBは全く同じであり、C,D,Eはそれぞれ別のオブジェクトである。
In [31]: print("%0x\n%0x\n%x\n%x\n"%(id(A[1]),id(C[1]),id(D[1]),id(E[1])))
7f78179efa48
7f78179efa48
7f78179efa48
7f78179efd48
deepcopyしたEだけが異なることが分かった。つまり、ちゃんとコピーしたいときには、deepcopyしないとダメである。 次に、リストの最初の要素のIDを調べた。
In [32]: print("%0x\n%0x\n%x\n%x\n"%(id(A[0]),id(C[0]),id(D[0]),id(E[0])))
7f7835ba5a20
7f7835ba5a20
7f7835ba5a20
7f7835ba5a20
全部同じである。 リストの最初の要素はただの数字、整数の1であった。
 
ということは、整数さえもオブジェクトなのだろうか?
とても簡単なリストの実験をしてみよう。
リストで繰り返しがあるとき、*で済ませると楽ができる。 とても簡単な例。
In [54]: A = [1,2,1,2,1,2]

In [55]: B = [1,2]*3

In [56]: print(A,B)
[1, 2, 1, 2, 1, 2] [1, 2, 1, 2, 1, 2]

In [57]: A==B
Out[57]: True

In [58]: A[3]+=5

In [59]: B[3]+=5

In [60]: print(A,B)
[1, 2, 1, 7, 1, 2] [1, 2, 1, 7, 1, 2]

In [61]: A==B
Out[61]: True
リストA,Bは当然同じ動きをする。 では、リストの要素を数字ではなく、リストに変えてみよう。 つまり、リストのリストの場合、どうなるだろうか?
In [80]: A = [[],[],[],[],[],[]]

In [81]: B = [[]]*6

In [82]: print(A); print(B); print(A==B)
[[], [], [], [], [], []]
[[], [], [], [], [], []]
True

In [83]: A[3].append(1)

In [84]: B[3].append(1)

In [85]: print(A); print(B); print(A==B)
[[], [], [], [1], [], []]
[[1], [1], [1], [1], [1], [1]]
False
リストAとBを2つの方法で作り、一致していることを確認した。 次に、A[3]とB[3]に1をappendした。 AとBは同じで、同じ操作をしたのだから、結果も同じになるはずなのだが、なっていない。
*6 により[]を6個にしても、実体は1つのままのようだ。

このでは、[]で実験したが、オブジェクトだったら全て同様の結果になるであろう。
オブジェクトを指している変数を、別の変数に代入しても同じオブジェクトを指すようになるだけというのが良く説明されているが、こういう場合にも同じ現象が当然起きる。

実験では、[]が6個だから、全部書いてもたいしたことはない。
もし、[]が100個だったら、n個だったらどうすればオブジェクトとして別々の[]を指定個数並べられるのだろうか?

このアーカイブについて

このページには、2016年12月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2016年11月です。

次のアーカイブは2017年1月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。