Tweetそろそろ年末なので、Pythonの内容も正月らしいというか、遊びを取り上げよう。ナンプレ(数独)のブームが来てから約10年が経過し、問題を人工知能を使って自動生成するのが普通になった。そのあたりを説明しだすと長くなるので、AIを使った自動生成の話は止める。Pythonで、リストではなく、集合や辞書を多用して問題を解くことをやってみようと思う。要するに、世の中であまりやっていないと思われる方法で解いてみよう。実はこの方法の方が汎用性があり、抽象度を高くすることで、多種多様なナンプレのバラエティにも対応できる。以前学研の『IQナンプレ300vol.2』の表紙になった問題である。この問題を、以下のようにして解こうと思う。問題の数字(ヒントという)は、数字の入っているマスを[x,y,n]の形の長さ3のリストで表す。すると、問題全体は、このリストが数字の個数あれば表現できる。以下のプログラムでは、リストhintに問題データを与えている。便利なインターフェイスを作るべきだが、問題を解くことと本質的に関係ないので、とりあえずこの形にしておく。問題をあれこれ調べるために問題盤面が欲しいので、問題を示すhintを与えてBoardオブジェクトを作ると、Boardオブジェクトは初期化された状態になっている。bd.print()により、現状の盤面が表示されるので、以下では問題そのものが表示されるはず。次に、初期化状態のBoardオブジェクトを与えてSolverオブジェクトを作り、solve()メソッドで問題を実際に解く。こんな感じになるといいな。次回は、Boardクラスを作ろう。TweetPythonには、数学の集合と同様の動きをする集合(set)が用意されている。要素の個数に特に制限はなく、要素に順序もない。要素の個数が増えれば、そのぶん集合のサイズが増加するはずだが、サイズを調べるとなかなか不思議な増え方をする。sys.getsizeof(a)736空集合でも224バイトもある。要素をいくつか追加しても、サイズは変化しない。あるとき、急にサイズが増えるようなのだ。集合のサイズの増え方を調べるために、以下の実験をした。sizeofset(n)は、最初に空集合をつくり、その後集合に数字を1つずつn個になるまで追加する。そのとき、直前のバイトサイズよりも大きくなったときに、集合の要素数とバイト数を表示するようにした。268435680これを見ると、サイズが6,22,86,342,...になったy瞬間に集合のバイトサイズが増えている。87382個までは、大きくなるときには約4倍ずつ大きくなり、それ以上では約2倍ずつ大きくなっている。大きくなった集合の要素を消していくと、集合のバイトサイズはどうなるだろうか。実験ではこんな結果になった。sys.getsizeof(a)268435680要素数1000万個の集合を作ってサイズを求め、次に要素を全部消した。集合はset()と表示されたので空集合になっている。サイズは要素数1000万個のときと同じであり、巨大な空集合ができてしまった(トホホ)。一度大きくなった集合は、要素がいくら少なくなっても小さくならない。TweetPythonには複数のデータを扱うのに、リストだけでなく集合(set)もある。今回は、集合にいっぱい要素を突っ込んだり消したりしたときの速度を調べてみる。空集合を作り、自然数を1から10,000,000まで1000万個を突っ込んでみた。592703488)2.3秒/1000万個=0.23マイクロ秒/個のペースで追加できている。メモリは592MB消費したようだ。同じことを内包を使って実行してみる。592707584)0.60秒/1000万個=0.06マイクロ秒/個で、4倍近く高速になっている。1000万個追加するのに、前回のリストのときには0.36秒だったので、集合への追加はリストのアペンドに比べて倍近く時間が掛かっていることが分かる。集合は、もし同じものがあったら追加されないので、そのあたりの判定も必要になる。追加だけでなく、削除もやっておこう。集合の削除メソッドには、remove(x)とdiscard(x)がある。discardは要素xが存在しなくてもエラーにはならず無視されるだけだが、removeではKeyErrorが発生してしまうので気をつけよう。bset()消すのは、内包を使わないadd()とほぼ同じ時間かかることが分かった。いうことで、予想通り、集合でも内包を使った方が遥かに高速になるのであった。Pythonではなく、数学的にはどう表現するであろうか。{2,4,6,8,...100}これでも良いのだが、ちょっと...という部分が気になる。