TIM Labs
前回、特定の値に対する微分係数を求めた。
式で書けば, 関数 f(x) に 対して x=a のときの微分係数 f'(a) を求めた。
そのとき、
x = Variable(np.array([5.0],dtype=np.float16))
として変数xを用意したのだが、np.array([5.0])で、スカラーを要素数1個の配列でわざわざ与えた。
ということは、配列に対しても、そのまま動くのではないだろうか。

ということで、 sin(x) を -np.pi <= x <= np.pi の区間内の複数の点に対して一気に計算してみよう。

まず、配列の生成を確認。
>>> np.array(np.linspace(-np.pi, np.pi, 21))
array([-3.14159265, -2.82743339, -2.51327412, -2.19911486, -1.88495559,
       -1.57079633, -1.25663706, -0.9424778 , -0.62831853, -0.31415927,
        0.        ,  0.31415927,  0.62831853,  0.9424778 ,  1.25663706,
        1.57079633,  1.88495559,  2.19911486,  2.51327412,  2.82743339,
        3.14159265])
この配列を与えて、chainerの変数xを配列で作ってしまおう。
>>> x = Variable(np.array(np.linspace(-np.pi, np.pi, 21), dtype=np.float16))
>>> x.data
array([-3.140625  , -2.828125  , -2.51367188, -2.19921875, -1.88476562,
       -1.5703125 , -1.25683594, -0.94238281, -0.62841797, -0.31420898,
        0.        ,  0.31420898,  0.62841797,  0.94238281,  1.25683594,
        1.5703125 ,  1.88476562,  2.19921875,  2.51367188,  2.828125  ,
        3.140625  ], dtype=float16)
値が少々違うが、これはnp.float16としたため、精度が落ちているのでやむを得ないだろう。

F.sin(x)にて配列xの各値に対して、まとめてsin(x)が求まるはずである。
>>> y = F.sin(x)
>>> y.data
array([ -9.67502594e-04,  -3.08349609e-01,  -5.87402344e-01,
        -8.09082031e-01,  -9.51171875e-01,  -1.00000000e+00,
        -9.51171875e-01,  -8.09082031e-01,  -5.87890625e-01,
        -3.09082031e-01,   0.00000000e+00,   3.09082031e-01,
         5.87890625e-01,   8.09082031e-01,   9.51171875e-01,
         1.00000000e+00,   9.51171875e-01,   8.09082031e-01,
         5.87402344e-01,   3.08349609e-01,   9.67502594e-04], dtype=float16)
yの値は、 -1 <= sin(x) <= 1 に収まっているようだ。


次に、y.backward() で微分してみよう。
>>> y.backward()
Traceback (most recent call last):
  File "", line 1, in 
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/variable.py", line 388, in backward
    gxs = func.backward(in_data, out_grad)
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/function.py", line 382, in backward
    return self.backward_cpu(inputs, grad_outputs)
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/functions/math/trigonometric.py", line 25, in backward_cpu
    gx *= gy[0]
TypeError: ufunc 'multiply' output (typecode 'O') could not be coerced to provided output parameter (typecode 'e') according to the casting rule ''same_kind'
>>>
ということで、backward()したとたんに叱られた。
要素数1だと大丈夫だったのだが、複数個に対してはダメなんだ。
何か悪いことをしたらしい。
 
次回までに原因を考えることにし、今日はここまで。
DLするためには、微分して勾配を求める必要がある。
ということで、まず、簡単な微分をしてみよう。

Chainerを動かすためには、まず最初に色々なものをimportしなければならない。
とりあえず、「おまじない」だと思って、プログラムの最初に書いておこう。

# おまじない
import numpy as np
import chainer
from chainer import cuda, Function, gradient_check, Variable 
from chainer import optimizers, serializers, utils
from chainer import Link, Chain, ChainList
import chainer.functions as F
import chainer.links as L
微分するためには、まず変数を作らないといけない。
それも、Pythonの変数ではなく、Chainerの変数として作らないといけない。
そのために、ちゃんとVariableをimportしているので、さっそくやってみよう。

>>> x = Variable( 5.0 )
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/variable.py", line 95, in __init__
    raise TypeError(msg)
TypeError: numpy.ndarray or cuda.ndarray are expected.
Actual: <class 'float'>
>>>
エラーメッセージから、Variableに直接5.0を与えてはだめで、型がnumpy.ndarrayかcuda.ndarrayになっていないとダメらしい。
ということで、要素数1個だけの配列にして、変数xを作って、y=x**2-2x+1 を与え微分してみた。
微分は、y.backward()にて行われている。
>>> x = Variable(np.array([5.0]))
>>> y = x**2 - 2 * x + 1
>>> y.data
array([ 16.])
>>> y.backward()
>>> x.grad
array([ 8.])
x=5のときのy=f(x)の値は、
y = x**2 - 2 * x + 1 にてforward処理が行われ、y.dataに値が求まっていて、f(5)=16が確認できる。

微分はy.backward()で行われ、結果は x.gradに入り、yのメンバーの何かに入るのではない。
今回は、yに含まれる変数がxただ1つだったが、DLでは多変数の微分(偏微分)が行われ、それぞれの変数の.gradに偏微分(微分係数)が入る。

y = x**2 - 2 * x + 1 をxで微分すると、dy/dx = 2*x - 2 なのだが、x=5のときの微分係数が求まるだけである。
x=5のときの微分係数が8であることは、次のようにしても確かめられる。

>>> dy = 2 * x - 2
>>> dy.data
array([ 8.])

何も指定しなかったので、
>>> type(x.data[0])
&lr;class 'numpy.float64'>
>>> type(y.data[0])
<class 'numpy.float64'&l\gt;
>>> type(x.grad[0])
<class 'numpy.float64'>
という風に、全部float64になってしまった。
DLでは精度はそれほど要らないので、とりあえずfloat32と思ったが、float16も用意されているので、使ってみた。
>>> x = Variable(np.array([5.0],dtype=np.float16))
>>> y = x**2 - 2 * x + 1
>>> y.backward()
>>> x.grad[0]
8.0
>>> type(x.grad[0])
<class 'numpy.float16'>

今回は簡単過ぎる微分だったので、次はもうちょっと高度な微分をやらせてみよう。
新年を迎えたので、何か新しいことをしようということで選んでみたのがChainerである。

去年の春、AlphaGoから人工知能の狂乱ブームが始まり、猫も杓子も Deep Learning を勉強しているようで、オライリージャパンの『ゼロからはじめるDeep Learing』がやたらに売れている。
もう4万部を突破しているようだが、あの本を4万人もの人が読んで理解できるなら、日本のIT技術者の層は予想より遥かに厚かったことになるが、実際には人工知能ブームに流されて買っただけで積読状態ではないかと思っている。

Deep Learning(以下DL)でよく利用されている言語がPythonである。といっても、Pythonの基本部分ではなく、NumPyを始めとする拡張部分を使いまくってDLを実現している。つまり、Pythonの基本部分を使いこなすだけでDLのコードが書けるわけではない。

ちょっと勉強し、拡張機能を使えば、かなり簡単にDLを実現できるが、もっともっと安直に横着に怠惰に使いたいという人間の本性を満たすために、さまざまなフレームワークが提供されている。

Googleが開発し公開したTensorFlowが一番有名で、日本語でも書籍が複数冊出ているようだ。
ネット上でも、色々な情報が出ているようだ。
ということで、TensorFlowは避けることにした(笑)

それで、何か別のものはないかと探して見つかったのがChainerというDLのフレームワークである。

とりあえず、本家(http://chainer.org/)を知っておくべきだ。
Chainerは、東大や京大出身者が集まって作ったベンチャー企業であるPreferred Infrastructure社からさらにスピンアウトしたPreferred Networksが作っている。
スピンアウトといっても、役員が一緒なので、ベンチャーの企業内ベンチャーみたいなものだろうか。

たとえば、深層学習フレームワーク Chainer の開発と今後の展開 という62ページのプレゼン資料もある。
著者の得居誠也氏は、現役の東大の情報科学専攻の大学院生である。
その他にもいろいろ資料がネット上にあるので、そのうち紹介しようと思う。

DLでは海外のソフトが圧倒的に強いのだが、そういうのは避けて、日本発のを弄ることにした。

まず、インストールしなければいけないのだが、pipで簡単にインストールできる。
 
pip install chainer

そして、Pythonを起動して、import して、バージョンを確認してみた。
>>> import chainer
>>> chainer.__version__
'1.19.0'
>>> 
これで、とりあえず動いているらしいことが分かった。 勉強開始だ!

去年からAIブームが続いているが、同時に「データサイエンス」さらには「データサイエンティスト」という言葉もよく聞く。

そして、データサイエンスを学習するための本として、以前は統計学などの本が紹介されていたのだが、最近はタイトルに「データサイエンス」が直接入ることが多くなった。

データサイエンスの本というと、やはり以下の、岩波書店の「岩波データサイエンス」を思い出す。

iwaDS1 (280x400).jpg       iwaDS2 (281x400).jpg


iwaDS3 (281x400).jpg       iwaDS4 (279x400).jpg

全6巻の予定で刊行中であり、今までに4巻出ており、4ヶ月に1冊のペースで毎回データサイエンスにちなんだ特集を組んでいる。

各冊、144ページが標準で、税込み1500円と、岩波書店にしては珍しいページ数であり、価格なのだ。

データサイエンスをきっちり順番に勉強していくための学習書というより、データサイエンスとはどんなもので、どんな利用のされ方をしているかを紹介しているような、ちょっと雑誌的な構成になっている。
だから、毎回、異なるメンバーが、様々なトピックを紹介している。

でも、いきなりトピックを始めると難度が高くなり過ぎるので、最初に2,3本くらいの記事は、特集分野についての概説やら入門やらになっていて、この部分はかなり読みやすいことが多い。

執筆者は、最先端の現場で働いているデータサイエンティストが多く、実例の紹介が並んでいる。こまかい説明が無かったりして、この本だけで理解するのは困難なことが多かったり、統計学の基礎ができていないと落ちこぼれたりすることもあるが、さまざまな情報源の紹介などもあるので、目を通すだけでも相当有益ではないかと思う。

岩波データサイエンス刊行委員会があり、統計数理研究所をはじめとして、多くの研究機関、大学、企業の研究者などが協力して多様な分野をカバーしている。
さらに、毎回出版記念トークショーを行い、多数の来場者が参加している。参加者の中には、本物のデータサイエンティストも多く、トークショーに参加することで、データサイエンスの現状、雰囲気を味わうことができる。
トークショーはニコニコ動画で配信され、また過去の動画や、関連情報は「岩波データサイエンス・サポートページ」で見ることができる。

ということで、とても書評といえるような解説ではないが、内容が広範過ぎて、しっかり読んで書評を書くというのは最初からあきらめた。

関係者の末席に傍観者としてトークショーを聞きに行くくらいなのだ。
あ、忘れるところだった。弊社からも、毎回寄稿している。普段は2ページなのだが、第2巻では長いのを寄稿していた。

本シリーズの内容のレベルの高さ、質などを考えると、なぜ増刷を重ねるほど売れてしまったのか、これが一番の謎である。
たぶん、データサイエンティストを目指している人がとても多いのではないか推察している。
実際、データサイエンスがらみのショーに行くと、データサイエンティストという人がいて、いろいろコンサルしますという場面に去年くらいから出くわすことが多くなった。

次号、Vol.5 は、特集「スパースモデリングと多変量データ解析」で、2月中旬に発売のはずだ。
前回、Boardクラスの説明をしたが、実はそれでほんとんど準備は済んでいる。

前回のBoardクラスを利用することで、問題を解くのがSolverクラスで、初期化と解くクラスのたった2つのメソッドがあるだけ。とても簡単である。

まず、コンストラクタについて。

class Solver:
    def __init__(self,board):
        self.board = board
        self.searchorder = self.board.makeblanklist()
問題が入った状態のBoardオブジェクトを与えて初期化が行われる。
このとき、問題の空きマスのリストをsearchorderに入れる。
searchorderは、名前の通り、マスをどの順番で調べるか(埋めていくか)の情報が入っている。

で、次に、問題を実際に解くメソッド solveである。

    def solve(self,idx):
        if idx == len(self.searchorder):
            self.board.print()       # 解けた! 解のプリント
            return
        x,y = self.searchorder[idx]
        possibles = self.board.possibles(x,y)
        for c in possibles:          # 可能な数字を順番に試す
            self.board.setnum(x,y,c)
            self.solve(idx+1)
            self.board.rmnum(x,y,c)       
solveには引数idxがあるが、このidxは最初に作った空きマスリスト(searchorder)の何番目の要素(空きマス)を次に調べるかを伝えている。
メインからは、
    Solver(bd).solve(0)
と呼ばれていたが、solve(0)で、searchorderの最初のマスを試すことになる。
もし、searchorderを全部使いきっていたら全部埋まっているはずなので解が出来上がっているはずなのでプリントする。
そうでなければ、次に数字を試すマス(x,y)を求め、マス(x,y)に入れることができる数字のリストをpossiblesとし、可能な数字すべてについてforループで調べる。
forループの中は、ます(x,y)に調べている数字cを置いて、次の空きマスを指示するためにidx+1を引数にして再帰呼出しをする。
戻ってきたら、元の状態に戻すために、マス(x,y)からcを取り除く。

これだけで、ちゃんと動く。
再帰を使えば、簡単である。

次の盤面は途中の状態をプリントしたものである。
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 
9 5 2 6 3 1 _ 7 _ 
_ _ _ 7 _ _ _ 8 _ 
最初の空きマス(_)は、(7,6)のマスであるが、ここには1〜9のいずれも入れられないので、再帰はこの先に進まず、戻っていく。
ということで、ナンプレを解くプログラムの説明は終える。

なお、実際にナンプレを解くプログラムを作る場合、このような再帰呼出しで虱潰しはしない。
これでは難易度が分からないし、それに遅い。
また、各マス、各グループ(タテ列、ヨコ列、ブロック)に何が入っているかを集合で実現したが、もちろん集合は遅いので使わないのが普通だ。
実際のナンプレ関連のプログラムでは、ビット演算を多用し高速化を実現する。
また、使った数字を集合に入れていたが、実際は使える数字(まだ使っていない数字=候補)を管理することで解いていく。

9x9のナンプレを解くのはとても簡単で、プログラミング初歩の練習問題である。
もうちょっと頑張ってみたい場合は、16x16、25x25の問題を解くプログラムを作ってみよう。
あるいは、ナンプレを自動生成するプログラムを作ってみよう。

正月も終わったので、この正月特集もこれで終わる(完)
盤面をクラスとして書く部分を今日は紹介する。
 クラス名はわかりやすく、Boardとした。
そして、最初に5つのメンバー変数を用意した。
class Board():
    board = {}                             # ナンプレ問題盤面 (x,y):n
    hconst = [set() for i in range(9)]     # ヨコ制約
    vconst = [set() for i in range(9)]     # タテ制約
    bconst = [set() for i in range(9)]     # ブロック制約
    numbers = {1,2,3,4,5,6,7,8,9}          # 利用可能数字
boardは辞書で、(x,y)に数字nが入っていることを、(x,y):n で示す。
hconstのconstは定数ではなく制約constraintの省略形である。
ヨコの制約が9組、タテの制約が9組、ブロックの制約が9組あるのを、集合のリストで表現し、使われている数字を集合に入れる。
1から9までの数字の集合があった方が便利そうなので、numbers を作った。

あとは、メソッドを色々用意した。

Boardの初期化は、最初から数字のあるところをリストでもらい、setnumで順番にその数字を盤面にセットしていく。これで、初期化を終えることにする。

問題を解くために、数字の入っていないマスをリストで持っておき、そのリストを見ながら数字を埋めたり剥いだりするとよい。そのために数字の入っていないマスのリストを作るのがmakeblanklistメソッド。

xy2bは、(x,y)のマスが属するブロックの番号を返す。
 
isusedは、(x,y)に数字nを入れられるかどうかを調べる。

    def __init__(self,hint):
        for x,y,n in hint:
            self.setnum(x,y,n)

    def makeblanklist(self):
        return [(x,y) for y in range(9) for x in range(9) if (x,y) not in self.board]

    def xy2b(self,x,y):  return  x//3*3+y//3
        
    def isused(self,x,y,n):
        return (n in hconst[x]) or (n in vconst[y]) or (n in bconst[xy2b(x,y)])
setnumは、(x,y)に数字nをセットする。盤面boardの(x,y)にnを入れる。

さらに、タテ、ヨコ、ブロックの制約にもnを追加しておく。

 rmnumは、setnumの逆操作を行う。

    def setnum(self,x,y,n):
        self.board[(x,y)] = n
        self.vconst[x].add(n)
        self.hconst[y].add(n)
        self.bconst[self.xy2b(x,y)].add(n)

    def rmnum(self,x,y,n):
        self.board.pop((x,y))
        self.vconst[x].remove(n)
        self.hconst[y].remove(n)
        self.bconst[self.xy2b(x,y)].remove(n)
possiblesは、(x,y)に入れられる数字の集合を返す。

 getは、盤面のboard[(x,y)]に入っている数字を返すのだが、存在しないとエラーになるので、存在チェックが行われている。
    def possibles(self,x,y):
        return  self.numbers - (self.vconst[x]|self.hconst[y]|self.bconst[self.xy2b(x,y)])

    def get(self,x,y):  
        return self.board[(x,y)] if (x,y) in self.board else 0
盤面をプリントするメソッドがprintである。説明の必要はないであろう。
    def print(self):
        for y in range(9):
            print()
            for x in range(9):
                n = self.get(x,y) 
                print((str(n) if n!=0 else '_')+' ',end='')
        print()
これだけ道具を用意し、あとは次回、解くためのクラスSolverを説明する。
新年明けましておめでとうございます

本年も技術的に尖ったこと、変なこと、色々紹介できればと思っております。

DSCF5095 (300x400).jpg       DSCF5098 (300x400).jpg


VS人工知能難問ナンプレ.jpg正月休みということで、変なプログラミング三昧のエンジニアも多いかと思いますが、
ちょっとプログラミングの話はお休みにして、プログラムを使って作っているものを紹介します。

右の写真は、この12月16日に発売になったばかりの『VS人工知能難問ナンプレ』です。
このナンプレ問題集は、タイトルにもあるように実際に人工知能、要するにプログラムを使って自動生成して作りました。

というより、我々というか、パズルの問題の既に多くの問題が人工知能技術により自動生成されています。将棋、囲碁が人工知能の脅威にさらされている昨今ですから、パズルの問題が人工知能によって作られていることに何の不思議もないでしょう。

パズルの問題は人間が作るから良いという人も未だにいますが、もう遠い過去の思い出になってしまいました。人工知能が作った問題とパズル作家が頑張って作った問題の区別はできません。いや、凄い問題の方が人工知能で、普通のが作家という判断はかなり正しいのです。これは、囲碁や将棋で、人工知能が指す手が意味不明でプロ棋士も解説できないけれど、結局人工知能が勝ってしまうのと同様といえます。

とくに本書は、パズル作家と呼ばれる人々ではほとんど作るのが困難なような問題をできるだけ多く入れています。
問題の数字の個数(ヒント数)が少ないだけの問題集は他にもありますが、ヒント数が少ない状態で難易度をきちんと調整し、配置にも美を重視しています。

ヒント数が少ないと必ず難問になるという誤解も多いですが、そんなことはありません。難易度の調整が難しくなるだけで、本書でも、全部が難問ではなく、かなりやさしい中級レベルの問題から、本当に難しい問題まで、人工知能によりバランスよく作らせています。

今は、人工知能と言うと何でもディープラーニングという考えがありますが、パズル問題の自動生成は別のタイプの人工知能を使うのが一般的です。
人工知能は生物、人間をモデルにすることが多いのですが、超大雑把に言って、脳をモデルにしたのがディープラーニングで、生物の進化をモデルにしたのが進化的計算で、なかでも遺伝的アルゴリズムが有名です。遺伝的アルゴリズムはアルゴリズムや人工知能の授業でも普通に教えられることで、そのタイプの人工知能を利用してこの問題集も作られました。

Pythonでナンプレを解く方法を書いている最中ですが、ナンプレを作るにはナンプレを解くプログラム(ソルバー)が必要ですが、問題作成中にソルバーを延々と呼び出すので、ソルバーはできるだけ高速でないといけません。そのため、Pythonは使っておらず、JavaやC/C++を利用しています。まあ、1ミリ秒程度で問題を解けないと、良い問題集を作るのは無理でしょう。

まあ、そういう背景を知った上で、本書で正月休み、さらにはその後の暇つぶしに本書を利用していただければ嬉しいかぎりです。あるいは、お年寄りのボケ防止にもなるでしょう。とくに母親がパズル好きというパターンは非常に多くなっています。親孝行にぜひ1冊いかがでしょうか。

最初の2枚の写真は、本ができて送られてきた200冊の本をつかって、パズルタワーを作ったところです。
昔、大手書店のスーパー書店員が多数売りたい本をこんな風に積み上げていたのを思い出して、つい作ったものです。
本書を入手希望の方は、弊社入り口ロビーにこのタワーがありますので、タワーが倒れないように1冊持っていってください。
万一倒れた場合には、積み直しておいていただければ助かります。








そろそろ年末なので、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()とほぼ同じ時間かかることが分かった。

ということで、予想通り、集合でも内包を使った方が遥かに高速になるのであった。

最近のコメント