Skip to content

Instantly share code, notes, and snippets.

@Cartman0

Cartman0/DiveIntoPython3_08.ipynb

Created April 2, 2016 16:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Cartman0/9ed3037cbdac59af53c20c125aed806e to your computer and use it in GitHub Desktop.
Save Cartman0/9ed3037cbdac59af53c20c125aed806e to your computer and use it in GitHub Desktop.
Download ZIP
Dive Into Python3 8章メモ（高度なイテレータ）
Display the source blob
Display the rendered blob
Raw
DiveIntoPython3_08.ipynb
{
"cells": [
{
"metadata": {
"toc": "true"
},
"cell_type": "markdown",
"source": "# Table of Contents\n <p><div class=\"lev1\"><a href=\"#8章-高度なイテレータ-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>8章 高度なイテレータ</a></div><div class=\"lev2\"><a href=\"#飛び込む-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>飛び込む</a></div><div class=\"lev2\"><a href=\"#パターンの出現をすべて見つける-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>パターンの出現をすべて見つける</a></div><div class=\"lev3\"><a href=\"#re.findall-のマッチ-1.2.1\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>re.findall のマッチ</a></div><div class=\"lev2\"><a href=\"#シーケンスから重複を取り除く-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>シーケンスから重複を取り除く</a></div><div class=\"lev2\"><a href=\"#表明する（assert）-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>表明する（assert）</a></div><div class=\"lev2\"><a href=\"#ジェネレータ式-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>ジェネレータ式</a></div><div class=\"lev2\"><a href=\"#順列を計算（怠惰なやり方）-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>順列を計算（怠惰なやり方）</a></div><div class=\"lev2\"><a href=\"#itertoolsモジュールにある他の愉快なもの-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>itertoolsモジュールにある他の愉快なもの</a></div><div class=\"lev3\"><a href=\"#イディオム：テキストファイルの行のリストを返す-1.7.1\"><span class=\"toc-item-num\">1.7.1&nbsp;&nbsp;</span>イディオム：テキストファイルの行のリストを返す</a></div><div class=\"lev2\"><a href=\"#新種の文字列操作-1.8\"><span class=\"toc-item-num\">1.8&nbsp;&nbsp;</span>新種の文字列操作</a></div><div class=\"lev2\"><a href=\"#任意の文字列をPythonの式として評価する-1.9\"><span class=\"toc-item-num\">1.9&nbsp;&nbsp;</span>任意の文字列をPythonの式として評価する</a></div><div class=\"lev2\"><a href=\"#まとめ-1.10\"><span class=\"toc-item-num\">1.10&nbsp;&nbsp;</span>まとめ</a></div><div class=\"lev2\"><a href=\"#参考リンク-1.11\"><span class=\"toc-item-num\">1.11&nbsp;&nbsp;</span>参考リンク</a></div>"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "- [Dive Into Python3 1章メモ](http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/Cartman0/d54093a99b9254c81bf1123adacbc48a/raw/eedc90bbbfc14e259854f2e739fffeec4cb4d8f7/DiveIntoPython3_01.ipynb)\n- [Dive Into Python3 2章メモ（ネイティブデータ型）](http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/Cartman0/988b51d8482ad9ade835bb07efdffb38/raw/784cf276b7cebe254e59f09dcea6f09eea760d38/DiveIntoPython3_02.ipynb)\n- [Dive Into Python3 3章メモ（内包表記）](http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/Cartman0/183ec6f6c835f621106f7c27d215290a/raw/bd7677946d6400bbe6acd257df7fb9c5976c3320/DiveIntoPython3_03.ipynb)\n- [Dive Into Python3 4章メモ（文字列）](http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/Cartman0/bb974f82e8a3fc74ac82c3c2a5b1a4f9/raw/63a80011c9391b451108c1a4dc804ec5ff125f34/DiveIntoPython3_04.ipynb)\n- [Dive Into Python3 5章メモ（正規表現）](http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/Cartman0/b834807a0dabb1c458b87be2f333a5ca/raw/37d6f25f67e017a569e1f0b60a9fcbe49d50515f/DiveIntoPython3_05.ipynb?flush_cache=true)\n- [Dive Into Python3 6章メモ（クロージャとジェネレータ）](http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/Cartman0/a8998f8f88c5578271495ada56cc4809/raw/4e9b8ef3543016a710f905215693694acd703549/DiveIntoPython3_06.ipynb?flush_cache=true)\n- [Dive Into Python3 7章メモ（高度なイテレータ）](http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/Cartman0/8eb511c3b2aa6cadad6f6d49666c9db2/raw/60863d1ce1c1e9e4cb336ad79a0e252807beb87c/DiveIntoPython3_07.ipynb?flush_cache=true)"
},
{
"metadata": {
"collapsed": true
},
"cell_type": "markdown",
"source": "# 8章 高度なイテレータ"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 飛び込む"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "以下のようなパズルは、「クリプト算術」や「覆面算」と呼ばれている。\nこれらの文字は実在の単語を綴っているが、各々の文字を0-9の数字で置き換えると、方程式を「綴る」ようにもなる。\nこのパズルのカギは、どの文字にどの数字が対応するのかを見つけ出すことだ。\nこの時、同じ文字には同じ数字を対応させなければならず、同じ数字を2つの文字に割り当てることもできず、さらにどの「単語」も0で始めてはならない。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "```\nHAWAII + IDAHO + IOWA + OHIO == STATES\n510199 + 98153 + 9301 + 3593 == 621246\n\nH = 5\nA = 1\nW = 0\nI = 9\nD = 8\nO = 3\nS = 6\nT = 2\nE = 4\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "以下のプログラムは覆面算のパズルをたった14行のコードで解く。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "import re\nimport itertools\n\ndef solve(puzzle):\n words = re.findall('[A-Z]+', puzzle.upper())\n unique_characters = set(''.join(words))\n assert len(unique_characters) <= 10, 'Too many letters'\n first_letters = {word[0] for word in words}\n n = len(first_letters)\n sorted_characters = ''.join(first_letters) + \\\n ''.join(unique_characters - first_letters)\n characters = tuple(ord(c) for c in sorted_characters)\n digits = tuple(ord(c) for c in '0123456789')\n zero = digits[0]\n for guess in itertools.permutations(digits, len(characters)):\n if zero not in guess[:n]:\n equation = puzzle.translate(dict(zip(characters, guess)))\n if eval(equation):\n return equation\n \n \n \n",
"execution_count": 1,
"outputs": []
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "solution = solve(\"HAWAII + IDAHO + IOWA + OHIO == STATES\")\nprint(solution)",
"execution_count": 2,
"outputs": [
{
"output_type": "stream",
"text": "510199 + 98153 + 9301 + 3593 == 621246\n",
"name": "stdout"
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "solve(\"I + LOVE + YOU == DORA\")",
"execution_count": 3,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'3 + 1458 + 946 == 2407'"
},
"metadata": {},
"execution_count": 3
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "solve('SEND + MORE == MONEY')",
"execution_count": 4,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'9567 + 1085 == 10652'"
},
"metadata": {},
"execution_count": 4
}
]
},
{
"metadata": {
"heading_collapsed": true
},
"cell_type": "markdown",
"source": "## パターンの出現をすべて見つける"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "覆面算ソルバが最初に行うのは、そのパズルに含まれるすべての文字 (A–Z) を見つけ出す。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`re`モジュールはPython の正規表現の実装。\nこのモジュールは`findall()`という関数を持っている。\nこの関数は、正規表現パターンと文字列を受け取り、\nその文字列の中にあるパターンの出現をすべて見つけ出す。\nこの場合は、パターンは数字の並びにマッチする。\n`findall()`関数は、パターンにマッチしたすべての部分文字列のリストを返す。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "import re\nre.findall('[0-9]+', '16 2-by-4s in rows of 8') ",
"execution_count": null,
"outputs": []
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "re.findall('[0-9]+', '16 2-by-4s in rows of 8 00') ",
"execution_count": null,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "この正規表現のパターンは、文字の並びにマッチする。\nここでも戻り値はリストであり、リストの各要素は正規表現パターンにマッチした文字列。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "re.findall('[A-Z]+', 'SEND + MORE == MONEY')",
"execution_count": null,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### re.findall のマッチ"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "re.findall(' s.*? s', \"The sixth sick sheikh's sixth sheep's sick.\")",
"execution_count": null,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "この正規表現が探すのは、空白、s、すべての文字のできるだけ短い繰り返し\n(`.*?`)、空白、そしてもうひとつのsだ。\n\n入力文字列を見ると、5つのマッチがわかる：\n\n1. The**( sixth s)**ick sheikh's sixth sheep's sick.\n2. The sixth**( sick s)**heikh's sixth sheep's sick.\n3. The sixth sick**( sheikh's s)**ixth sheep's sick.\n4. The sixth sick sheikh's**( sixth s)**heep's sick.\n5. The sixth sick sheikh's sixth **(sheep's s)**ick."
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`re.findall()`関数は3つのマッチしか返していない。\n具体的は1つ目と3つ目と5つ目。\n\n理由は、この関数は重なったマッチを返さない。\n- 1つ目のマッチは2つ目に重なり合っているので、1つ目は返されるが2つ目はスキップされる。\n- 3つ目のマッチは4つ目に重なり合っているので、3つ目は返されるが4つ目はスキップされる。\n- そして最後に5つ目が返される。\n\nマッチするのは5つではなく3つになる。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`' s.* s'` だと最長マッチで終わり。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "re.findall(' s.* s', \"The sixth sick sheikh's sixth sheep's sick.\")",
"execution_count": null,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## シーケンスから重複を取り除く"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "集合を使うと、シーケンスから重複を取り除く作業が取るに足らないものになる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "a_list = ['The', 'sixth', 'sick', \"sheik's\", 'sixth', \"sheep's\", 'sick']\na_list",
"execution_count": 5,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "['The', 'sixth', 'sick', \"sheik's\", 'sixth', \"sheep's\", 'sick']"
},
"metadata": {},
"execution_count": 5
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "いくつかの文字列を持ったリストが与えられると、set()関数はリストから重複する要素を取り除いた集合を返す。\nこれは、forループのように考えれば理解できる。リストから1つ目の要素を取って集合に入れる。2つ目を入れる。3つ目を入れる。4つ目を入れる。\n5つ目はすでに集合に含まれている。\n\nPythonの集合は重複を許さないので、これは一度しか追加されない。\n6つ目入れる。7つ目を……これも重複だ。よって、\nこれも一度しか追加されない。\n最終的な結果はどうなっただろうか？ 結果は元のリストから重複を取り除いたものとなる。あらかじめ元のリストをソートしておく必要すらない。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "set(a_list)",
"execution_count": 6,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "{'The', \"sheep's\", \"sheik's\", 'sick', 'sixth'}"
},
"metadata": {},
"execution_count": 6
}
]
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "a_string = 'EAST IS EAST'",
"execution_count": 7,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "文字列は文字のシーケンスなので、同様のテクニックは文字列でも機能する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "set(a_string)",
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "{' ', 'A', 'E', 'I', 'S', 'T'}"
},
"metadata": {},
"execution_count": 8
}
]
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "words = ['SEND', 'MORE', 'MONEY']",
"execution_count": 9,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "文字列のリストが与えられると、`.join(a_list)` はすべての文字列を1つに連結する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "''.join(words)",
"execution_count": 10,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'SENDMOREMONEY'"
},
"metadata": {},
"execution_count": 10
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "','.join(words)",
"execution_count": 11,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'SEND,MORE,MONEY'"
},
"metadata": {},
"execution_count": 11
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "つまりこの行のコードは、文字列のリストが与えられると、\n文字列にあるすべての文字から重複を取りのぞいたものを返す。\n\n（文字列リストを連結して1つの文字列にして、文字の集合をつくる）"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "set(''.join(words))",
"execution_count": 12,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "{'D', 'E', 'M', 'N', 'O', 'R', 'S', 'Y'}"
},
"metadata": {},
"execution_count": 12
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "覆面算ソルバはこのテクニックを使って、パズルに含まれるすべての文字を含んだ集合を構築する。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "このリストは、あとでソルバが解候補をイテレートする際に、数字を文字に割り当てるために使われる。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "unique_characters = set(''.join(words))",
"execution_count": 13,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 表明する（assert）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Pythonは `assert`文を持っている。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`assert`文には、正しいPythonの式であれば何でも置ける。\nこの場合、式`1 + 1 == 2` は`True` と評価されるので、`assert`文は何もしない。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "assert 1 + 1 == 2",
"execution_count": 14,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "しかし、もしPython の式が `False` と評価された場合、`assert`文は `AssertionError` を送出する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "assert 1 + 1 == 3",
"execution_count": 15,
"outputs": [
{
"output_type": "error",
"ename": "AssertionError",
"evalue": "",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[1;31mAssertionError\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-15-bbebc67e583c>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32massert\u001b[0m \u001b[1;36m1\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m1\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m3\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;31mAssertionError\u001b[0m: "
]
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`AssertionError` が起きた場合に表示するための、\n人間が読めるメッセージ含めておくこともできる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "assert (2 + 2 == 5), \"Only for very large values of 2\"",
"execution_count": 16,
"outputs": [
{
"output_type": "error",
"ename": "AssertionError",
"evalue": "Only for very large values of 2",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[1;31mAssertionError\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-16-0c1e852e77f5>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32massert\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m2\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m5\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"Only for very large values of 2\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;31mAssertionError\u001b[0m: Only for very large values of 2"
]
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "以下のコード\n\n```\nassert len(unique_characters) <= 10, 'Too many letters'\n```\n\nと\n\n```\nif len(unique_characters) > 10:\n raise AssertionError('Too many letters')\n```\nは等価。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "覆面算ソルバは、パズルが10種類以上の文字を含んでいるときの緊急脱出手段としてassert文を使っている。\n各々の文字は一意な数字に割り当てられるわけだが、「数字は10個」しかないので、\n10種類より多い文字を持つパズルは解を持ち得ない。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## ジェネレータ式"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "**ジェネレータ式** は、関数を使わずに作るジェネレータ関数、という感じのもの。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}",
"execution_count": 17,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "ジェネレータ式は、値を`yield` する匿名関数のようなものだと思えばいい。\nこの式はリスト内包表記に似ているが、角括弧の代わりに丸括弧に包まれている。\n\nタプル内包表記はなくジェネレータ式になる。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "gen = (ord(c) for c in unique_characters) ",
"execution_count": 18,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "ジェネレータ式はイテレータを返す。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "gen",
"execution_count": 19,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "<generator object <genexpr> at 0x000002571F24E468>"
},
"metadata": {},
"execution_count": 19
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`next(gen)` の呼び出しによって、イテレータから次の値が返される。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(gen)",
"execution_count": 20,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "77"
},
"metadata": {},
"execution_count": 20
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(gen)",
"execution_count": 21,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "89"
},
"metadata": {},
"execution_count": 21
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "ジェネレータ式をtuple()、list()、set()に渡せば、すべての値がイテレートされてタプル・リスト・集合として返すこともできる。\nこれらの場合、余分な括弧は必要ない。\nつまり、tuple()関数に「はだか」の式ord(c) for c in unique_charactersを渡すだけで、\nPythonがジェネレータ式だと識別してくれる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "tuple(ord(c) for c in unique_characters)",
"execution_count": 22,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(77, 89, 82, 83, 68, 79, 78, 69)"
},
"metadata": {},
"execution_count": 22
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`ord`関数は、文字(character) をユニコードのバイト（0-255の整数）に変える。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "ord.__doc__",
"execution_count": 23,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'Return the Unicode code point for a one-character string.'"
},
"metadata": {},
"execution_count": 23
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "リスト内包表記の代わりにジェネレータ式を使うことで、\n- cpu使用量\n- ram使用量\n\nの両方を削減できる。\n\nもし作ったリストをすぐ投げ捨てるのであれば（つまり、それをtuple()やset()に渡しているのなら）、代わりにジェネレータ式を使う。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "以下では、同じことを**ジェネレータ関数** を使ってやっている：\n\n```\ndef ord_map(a_string):\n for c in a_string:\n yield ord(c)\n\ngen = ord_map(unique_characters)`\n```\n\nジェネレータ式のほうがコンパクトだが、機能的には同等。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 順列を計算（怠惰なやり方）"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "順列というのは、\n1. 何か（数字とか、文字とか、踊っている熊さんとか）のリストを受け取る。\n2. そして、そのリストから取り出せる小さなリストをすべて見つけ出す。\n - この時、取り出すリストはすべて同じサイズにする。そのサイズは最小で1、最大で全要素の数にできる。\n - 加えて、リストを取り出す際には1つの要素を2回以上使ってはならない。\n\n数学者は、「3つの異なる要素から2つずつ取り出すときの順列を見つけましょう」というようなことを言うが、\nこれが意味することは、あなたは3つの要素からなるシーケンスを持っており、\nその要素から作り出せるすべての順序対を見つけ出したいということ。\n\n$$\n{}_3 P_2 = 3 * 2 = 6通り\n$$"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`itertools`モジュールの中には、\n順列を見つけるという面倒な仕事をすべてやってくれる\n`permutations()`関数も入っている。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "import itertools\nitertools",
"execution_count": 24,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "<module 'itertools' (built-in)>"
},
"metadata": {},
"execution_count": 24
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`permutations()`関数は、\n- シーケンス（ここでは3つの整数からなるリスト）\n- 数値（個々の小さなグループの要素の数）\n\nを受け取る。\n\nこの関数はイテレータを返すが、このイテレータはfor文のようなイテレートを行う場所でならどこでも使用できる。\nここでは手動でイテレータを動かして、すべての値を示している。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "perms = itertools.permutations([1, 2, 3], 2)",
"execution_count": 25,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`[1, 2, 3]` から一度に2つずつ取り出したときの最初の順列は`(1, 2)`。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 26,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(1, 2)"
},
"metadata": {},
"execution_count": 26
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 27,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(1, 3)"
},
"metadata": {},
"execution_count": 27
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 28,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(2, 1)"
},
"metadata": {},
"execution_count": 28
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "順列は順序付けされていることに注意。`(2, 1)` と`(1, 2)` は区別される。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 29,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(2, 3)"
},
"metadata": {},
"execution_count": 29
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 30,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(3, 1)"
},
"metadata": {},
"execution_count": 30
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 31,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(3, 2)"
},
"metadata": {},
"execution_count": 31
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "これで終わり.\n以上が[1, 2, 3]から一度に2つずつ取り出したときのすべての順列。\n(1, 1)や(2, 2)のようなペアは絶対に現れない。\nこれらは同じ要素が繰り返し使われているので、\n正しい順列ではないのだ。\n返す順列が無くなると、\nイテレータは`StopIteration例外` を送出する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 32,
"outputs": [
{
"output_type": "error",
"ename": "StopIteration",
"evalue": "",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[1;31mStopIteration\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-32-2f38aa3f83d9>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mperms\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;31mStopIteration\u001b[0m: "
]
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`permutations()` 関数はリストしか受け取れないわけではない。\nこれは任意のシーケンスを受けとれる.\n文字列も受け取れる。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "import itertools",
"execution_count": 33,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "文字列は単なる文字のシーケンス。\n順列を見つけるという目的からは、\n「文字列'ABC'はリスト['A', 'B', 'C']と等価」。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "perms = itertools.permutations('ABC', 3)",
"execution_count": 35,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "3つの要素['A'、'B'、'C'] から一度に3つずつ取るときの最初の順列は\n`('A', 'B', 'C')` 。\nこの他に5つの順列 — すなわち、この3文字の考えうる並べ方すべて — が存在する。\n\n$$\n{}_3 P_3 = 3 * 2 * 1 = 6通り\n$$\n"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "next(perms)",
"execution_count": 36,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "('A', 'B', 'C')"
},
"metadata": {},
"execution_count": 36
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`permutations()`関数は常にイテレータを返すので、\n順列をデバッグする簡易な方法として、\nイテレータを組み込みの`list()`関数に渡すことで、\n順列の全体を即座に見るというやり方がある。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(itertools.permutations('ABC', 3))",
"execution_count": 37,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[('A', 'B', 'C'),\n ('A', 'C', 'B'),\n ('B', 'A', 'C'),\n ('B', 'C', 'A'),\n ('C', 'A', 'B'),\n ('C', 'B', 'A')]"
},
"metadata": {},
"execution_count": 37
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## itertoolsモジュールにある他の愉快なもの"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "import itertools",
"execution_count": 38,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`itertools.product()`関数は、\n2つのシーケンスの直積からなるイテレータを返す。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(itertools.product('ABC', '123'))",
"execution_count": 39,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[('A', '1'),\n ('A', '2'),\n ('A', '3'),\n ('B', '1'),\n ('B', '2'),\n ('B', '3'),\n ('C', '1'),\n ('C', '2'),\n ('C', '3')]"
},
"metadata": {},
"execution_count": 39
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`itertools.combinations()`関数は、与えられたシーケンスについて、\n指定された要素の数からなる**組み合わせ**全部を取り出して、\nイテレーターとして返す。\n\nこれは`itertools.permutations()`関数に似ているが、順序違いのものは含まないということが異なる。\nすなわち、`itertools.permutations('ABC', 2)`は、('A', 'B')と('B', 'A')の両方を返すが、`itertools.combinations('ABC', 2)` は、('B', 'A')を返さない。\n\n$$\n{}_3 C_2 = \\frac{3*2}{2*1} = 3通り\n$$"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(itertools.combinations('ABC', 2))",
"execution_count": 40,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[('A', 'B'), ('A', 'C'), ('B', 'C')]"
},
"metadata": {},
"execution_count": 40
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### イディオム：テキストファイルの行のリストを返す"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "```\nfavorite-people.txt >\nDora\nEthan\nWesley\nJohn\nAnne\nMike\nChris\nSarah\nAlex\nLizzie\n\n\n```"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "names = list(open('favorite-people.txt', encoding='utf-8'))\nnames",
"execution_count": 41,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "['Dora\\n',\n 'Ethan\\n',\n 'Wesley\\n',\n 'John\\n',\n 'Anne\\n',\n 'Mike\\n',\n 'Chris\\n',\n 'Sarah\\n',\n 'Alex\\n',\n 'Lizzie\\n']"
},
"metadata": {},
"execution_count": 41
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "（この例にとっては）都合が悪いことに、\n`list(open(filename))` というイディオムで処理すると、\n各行の末尾にある改行文字( `\\n` )が残ってしまう。\n\nこのリスト内包表記は、\n- 文字列メソッドの`rstrip()` を使って、\n文字列の後ろに付いている空白文字を各行から取り除いている\n\n文字列は、他に、\n- 先頭にある空白文字を取り除くための `lstrip()` メソッドや、\n- 先頭と末尾の両方の空白文字を取り除く `strip()` メソッドも持っている）"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "names = [name.rstrip() for name in names]",
"execution_count": 42,
"outputs": []
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "names",
"execution_count": 43,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "['Dora',\n 'Ethan',\n 'Wesley',\n 'John',\n 'Anne',\n 'Mike',\n 'Chris',\n 'Sarah',\n 'Alex',\n 'Lizzie']"
},
"metadata": {},
"execution_count": 43
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`sorted()`関数はリストを受け取って、\nそのリストをソートしたものを返す。\n\nデフォルトではアルファベット順にソートする。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "names = sorted(names)\nnames",
"execution_count": 44,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "['Alex',\n 'Anne',\n 'Chris',\n 'Dora',\n 'Ethan',\n 'John',\n 'Lizzie',\n 'Mike',\n 'Sarah',\n 'Wesley']"
},
"metadata": {},
"execution_count": 44
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "さらに、\n`sorted()`関数は、`key`引数として関数を受け取り、\nそのキーに基づいてソートを行うこともできる。\n\nこの例では、ソート関数は`len()`なので、\nこれは`len`(各要素)に基づいてソートを行う。\n短い名前が先に来て、次に長い名前がくる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "names = sorted(names, key=len)\nnames",
"execution_count": 45,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "['Alex',\n 'Anne',\n 'Dora',\n 'John',\n 'Mike',\n 'Chris',\n 'Ethan',\n 'Sarah',\n 'Lizzie',\n 'Wesley']"
},
"metadata": {},
"execution_count": 45
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`itertools.groupby()`関数は、\nシーケンスとキー関数を受け取り、\nペアを生成するイテレータを返す。\n\n各々のペアには、`key_function(each item)` の値と、\nキー関数に渡したときにその値を返すような要素を集めたイテレータが入っている。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "import itertools\ngroups = itertools.groupby(names, len)\ngroups",
"execution_count": 46,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "<itertools.groupby at 0x2571f25b728>"
},
"metadata": {},
"execution_count": 46
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "list(groups)",
"execution_count": 47,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[(4, <itertools._grouper at 0x2571f25d048>),\n (5, <itertools._grouper at 0x2571f25d438>),\n (6, <itertools._grouper at 0x2571f25d780>)]"
},
"metadata": {},
"execution_count": 47
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`list()`関数を呼び出したことでイテレータは「使い果たされた」。\nつまり、リストを作るために、イテレータの要素をすべて生成しつくした。\nイテレータに「リセット」ボタンは無いので、一度使い果たしたら最初からやり直させることはできない。\n\nもう一度（例えば、次のforループで）イテレートしたいのであれば、\n再び`itertools.groupby()` を呼び出して新しいイテレータを作る必要がある。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "groups = itertools.groupby(names, len)",
"execution_count": 48,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "この例では、すでに長さでソートしてある名前のリストが与えられたので、`itertools.groupby(names, len)` は、\n- 4文字の名前をすべて1つのイテレータに入れ、\n- 5文字の名前をすべてもう1つのイテレータに入れ……\n\nというように同じ長さの名前を同じ1つのイテレータに入れてくれた。\n\n`groupby()`関数は完全に汎用的なので、\n文字列を最初の1文字でグループ分けすることもできるし、\n数字を因数の数で分類することもできる。\n思いつくキー関数ならどんなものでも使える。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "for name_length, name_iter in groups: \n print('Names with {0:d} letters:'.format(name_length))\n \n for name in name_iter:\n print(name)\n \n print('\\n')\n",
"execution_count": 49,
"outputs": [
{
"output_type": "stream",
"text": "Names with 4 letters:\nAlex\nAnne\nDora\nJohn\nMike\n\n\nNames with 5 letters:\nChris\nEthan\nSarah\n\n\nNames with 6 letters:\nLizzie\nWesley\n\n\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`itertools.groupby()`関数は、\n入力されたシーケンスがグループ関数ですでにソートされているときにだけ機能する。\n\n上の例では、名前のリストを`len()`関数でグループ分けしたが、\nこれが上手くいったのは、あらかじめ入力リストを名前でソートしておいたから。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(range(0, 3))",
"execution_count": 50,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[0, 1, 2]"
},
"metadata": {},
"execution_count": 50
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(range(10, 13))",
"execution_count": 51,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[10, 11, 12]"
},
"metadata": {},
"execution_count": 51
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`itertools.chain()`関数は、\n2つのイテレータを受け取って、\n1つ目のイテレータのすべての要素と、\nそれに続いて2つ目のイテレータのすべての要素を含んだ1つのイテレータを返す.\n\n（実は、任意数のイテレータを受け取ることができ、それらを関数に渡された順序で連結する）。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "list(itertools.chain(range(0, 3), range(10, 13)))",
"execution_count": 52,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[0, 1, 2, 10, 11, 12]"
},
"metadata": {},
"execution_count": 52
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`zip()`関数は、任意の数のシーケンスを受け取り、各シーケンスの1つ目の要素からなるタプル、各シーケンスの2つ目の要素からなるタプル、3つ目の要素からなるタプル……を生成するイテレータを返す。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "zip(range(0, 3), range(10, 13))",
"execution_count": 53,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "<zip at 0x2571f25ecc8>"
},
"metadata": {},
"execution_count": 53
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(zip(range(0, 3), range(10, 13)))",
"execution_count": null,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`zip()`関数は、最も短いシーケンスの終わりで停止する。\n`range(10, 14)` は4つの要素 `(10, 11, 12, 13)` を持つが、\n`range(0, 3)` は3つしか持たないので、この`zip()`関数は3つの要素を持つイテレータを返す。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(zip(range(0, 5), range(10, 14))) ",
"execution_count": 54,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[(0, 10), (1, 11), (2, 12), (3, 13)]"
},
"metadata": {},
"execution_count": 54
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(zip(range(0, 7), range(10, 14))) ",
"execution_count": 55,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[(0, 10), (1, 11), (2, 12), (3, 13)]"
},
"metadata": {},
"execution_count": 55
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "その一方で、`itertools.zip_longest()`関数は最も長いシーケンスの終わりで停止する。\n短いシーケンスが尽きた後についてはNoneを挿入する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(itertools.zip_longest(range(0, 3), range(10, 14)))",
"execution_count": 56,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[(0, 10), (1, 11), (2, 12), (None, 13)]"
},
"metadata": {},
"execution_count": 56
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "list(itertools.zip_longest(range(0, 7), range(10, 14)))",
"execution_count": 57,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "[(0, 10), (1, 11), (2, 12), (3, 13), (4, None), (5, None), (6, None)]"
},
"metadata": {},
"execution_count": 57
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "覆面算ソルバにはどんな関係があるのだろうか？"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y')\nguess = ('1', '2', '0', '3', '4', '5', '6', '7')",
"execution_count": 58,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "文字のリストと数字（ここではそれぞれが1文字の文字列として表されている）のリストを与えると、`zip`関数は文字と数字のペアを順番通りに作成する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "tuple(zip(characters, guess))",
"execution_count": 59,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(('S', '1'),\n ('M', '2'),\n ('E', '0'),\n ('D', '3'),\n ('O', '4'),\n ('N', '5'),\n ('R', '6'),\n ('Y', '7'))"
},
"metadata": {},
"execution_count": 59
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "このタプルは、`dict()`関数に渡すことで、\n「文字をキー、対応する数字を値とした辞書」を構築できる構造になっている\n（辞書内包表記を使って、この辞書を直接構築することだってできる）。\n\n表示された辞書の表現ではペアの順序が変わっているが（辞書は本質的に「順序」を持たない）、元の`characters` と`guess` のシーケンス内の順序に基づいて、各文字に数字が対応付けられていることが見て取れるだろう。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "dict(zip(characters, guess))",
"execution_count": 60,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "{'D': '3',\n 'E': '0',\n 'M': '2',\n 'N': '5',\n 'O': '4',\n 'R': '6',\n 'S': '1',\n 'Y': '7'}"
},
"metadata": {},
"execution_count": 60
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "覆面算ソルバは、パズルの文字を解の数字に対応させる辞書を作るために、\n各々の解候補に対してこのテクニックを使っている。\n\n```\nequation = puzzle.translate(dict(zip(characters, guess)))\n```\n"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 新種の文字列操作"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "文字列操作のテクニックである`translate()`メソッドについて。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "文字列の変換は変換表の用意から始まる。\nこれは、文字を他の文字に対応付けた単なる辞書だ。\n実際には、変換表はバイトを他のバイトに対応させるのだ。"
},
{
"metadata": {
"collapsed": true,
"trusted": true
},
"cell_type": "code",
"source": "translation_table = {ord('A'): ord('O')}",
"execution_count": 61,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Python 3のバイトは整数。\n`ord()`関数は文字のascii値を返し、\nこれはA–Zの場合、常に65から90までの1バイトになる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "translation_table ",
"execution_count": 62,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "{65: 79}"
},
"metadata": {},
"execution_count": 62
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "文字列の`translate()` メソッドは変換表を受け取り、\n文字列をその変換表に通す。\nつまり、変換表のキーに一致する部分をすべて対応する文字に変換するのだ。\nこの例では、MARKをMORKに「変換 (translate)」している。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "'MARK'.translate(translation_table)",
"execution_count": 63,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'MORK'"
},
"metadata": {},
"execution_count": 63
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "ジェネレータ式を使い、\nこの文字列にある各々の文字のバイト値を素早く計算する。\n\"SMEDONRY\"は、`alphametics.solve()`関数におけるsorted_charactersの値の例だ。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "characters = tuple(ord(c) for c in 'SMEDONRY')\ncharacters",
"execution_count": 64,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(83, 77, 69, 68, 79, 78, 82, 89)"
},
"metadata": {},
"execution_count": 64
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "別のジェネレータ式を使い、\nこの文字列にある各々の数字のバイト値を素早く計算する。\n戻り値のguessは、`alphametics.solve()`関数において\n`itertools.permutations()`関数によって返されるものと同じ形をしている。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "guess = tuple(ord(c) for c in '91570682')\nguess",
"execution_count": 65,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "(57, 49, 53, 55, 48, 54, 56, 50)"
},
"metadata": {},
"execution_count": 65
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`characters` と`guess` を`zip` して、\nその戻り値のペアのシーケンスから辞書を構築することによって、この変換表は生成される。\nこれは、`alphametics.solve()`関数がforループの中でやっていること。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "translation_table = dict(zip(characters, guess))\ntranslation_table",
"execution_count": 66,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "{68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50}"
},
"metadata": {},
"execution_count": 66
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "オリジナルのパズル文字列の`translate()`メソッドに変換表を渡す。\nこれは、文字列の各文字を（charactersの文字とguessの数字にもとづいて）対応する数字に変換する。その結果は、有効なPythonの式を文字列として表したものになる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "'SEND + MORE == MONEY'.translate(translation_table) ",
"execution_count": 67,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'9567 + 1085 == 10652'"
},
"metadata": {},
"execution_count": 67
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 任意の文字列をPythonの式として評価する"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "手の込んだ文字列操作の末に、'9567 + 1085 == 10652'というような文字列が手に入った。\nしかし、これは文字列であって、文字列で何ができるというのだ？\n`eval()` の話に入ろう。これは、Pythonの式を評価するための万能ツールだ。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval('1 + 1 == 2')",
"execution_count": 68,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "True"
},
"metadata": {},
"execution_count": 68
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval('1 + 1 == 3')",
"execution_count": 69,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "False"
},
"metadata": {},
"execution_count": 69
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval('9567 + 1085 == 10652')",
"execution_count": 70,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "True"
},
"metadata": {},
"execution_count": 70
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`eval()`関数が扱えるものはブール式だけではなく、\nどんなPythonの式でも扱えるし、どんなデータ型でも返せる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval('\"A\" + \"B\"')",
"execution_count": 71,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'AB'"
},
"metadata": {},
"execution_count": 71
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval('\"MARK\".translate({65: 79})')",
"execution_count": 72,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "'MORK'"
},
"metadata": {},
"execution_count": 72
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval('\"AAAAA\".count(\"A\")')",
"execution_count": 73,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "5"
},
"metadata": {},
"execution_count": 73
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "[\"*\"] * 5",
"execution_count": 74,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "['*', '*', '*', '*', '*']"
},
"metadata": {},
"execution_count": 74
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval('[\"*\"] * 5')",
"execution_count": 75,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "['*', '*', '*', '*', '*']"
},
"metadata": {},
"execution_count": 75
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`eval()` が受け取る式は、`eval()` の外側で定義されたグローバル変数を参照できる。\n関数の中で呼び出されたときはローカル変数も参照できる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "x = 5\neval(\"x * 5\")",
"execution_count": 76,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "25"
},
"metadata": {},
"execution_count": 76
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "eval(\"pow(x, 2)\")",
"execution_count": 77,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "25"
},
"metadata": {},
"execution_count": 77
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "モジュールも参照できる。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "import math\neval(\"math.sqrt(x)\")",
"execution_count": 78,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "2.23606797749979"
},
"metadata": {},
"execution_count": 78
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`subprocess`モジュールは、\n任意のシェルコマンドを実行し、その結果をPythonの文字列として受け取る機能を提供する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "markdown",
"source": "```\nimport subprocess\neval(\"subprocess.getoutput('dir ~')\") \n\n> dirコマンドの返り値が使える\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "```\neval(\"subprocess.getoutput('rm /some/random/file')\")\n```\n\nシェルコマンドの無制限な実行を許すと、とりかえしのつかない結果を招く可能性がある。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "というのは、グローバルの `__import__()`関数が存在する。\nこの関数はモジュール名を文字列として受け取り、\nそのモジュールをインポートしてそれへの参照を返す。この関数とeval()の力を組み合わせれば、すべてのファイルを消し飛ばす式を作れる\n\n```\neval(\"__import__('subprocess').getoutput('rm /some/random/file')\")\n```\n\n'rm -rf ~'の実行結果を想像してみよう。実際には一切何も出力されないのだが、あなたのファイルは全て消え去ってしまう。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "邪悪というのは、信頼できないところから入力された任意の式を評価してしまうことだ。\n`eval()`を使うのは、信頼している入力に対してだけにすべきだ。もちろん重要なのは「信頼している」とは何かを理解することであるが、確実に言えることがある： この覆面算ソルバを小さなおもしろWebサービスとしてインターネットに公開すべきではない。「え？ この関数は文字列を評価する前に沢山の文字列操作をしてるんだから、これのセキュリティホールを突く方法を誰かが見つけ出すなんて想像できないや」という誤った考えをしてはいけない。きっと何者かが、すべての文字列操作を通過する気色悪い実行可能コードを忍び込ませる方法を見いだすだろう（奇妙なことは実際に起きている）。\n\nでも、式を安全に評価する何らかの方法は本当に無いの？"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`eval()`関数に渡された2つ目と3つ目のパラメータは、\n式を評価するときの\nグローバル名前空間とローカル名前空間として機能する。\n\nこの場合は、両方が空になっている。このことは、\n`\"x * 5\"` という文字列が評価されるときに、\nグローバルとローカル名前空間のどちらにもxへの参照が存在しないということを意味するので、この`eval()`は例外を送出する。"
},
{
"metadata": {
"collapsed": false,
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "x = 5\neval(\"x * 5\", {}, {}) ",
"execution_count": 80,
"outputs": [
{
"output_type": "error",
"ename": "NameError",
"evalue": "name 'x' is not defined",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[1;31mNameError\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-80-ed0dd49f6458>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m 1\u001b[0m \u001b[0mx\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m5\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0meval\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"x * 5\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;32m<string>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n",
"\u001b[1;31mNameError\u001b[0m: name 'x' is not defined"
]
}
]
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval(\"x * 5\", {\"x\": x}, {}) ",
"execution_count": 81,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "25"
},
"metadata": {},
"execution_count": 81
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`math`モジュールをインポートしているが、`eval()`関数に渡す名前空間にこれを含めていないので、この評価は失敗する"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "import math\neval(\"math.sqrt(x)\", {\"x\": x}, {})",
"execution_count": 82,
"outputs": [
{
"output_type": "error",
"ename": "NameError",
"evalue": "name 'math' is not defined",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[1;31mNameError\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-82-a32a42b5c316>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m 1\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mmath\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0meval\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"math.sqrt(x)\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;34m\"x\"\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;32m<string>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n",
"\u001b[1;31mNameError\u001b[0m: name 'math' is not defined"
]
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "空の辞書をグローバル・ローカル名前空間に渡した場合でも、\nPythonの組み込み関数ならどれでも評価の際に利用できる。\nつまり `pow(5, 2)` は問題なく評価される。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval(\"pow(5, 2)\", {}, {}) ",
"execution_count": 83,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "25"
},
"metadata": {},
"execution_count": 83
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "`__import__()`関数も組み込み関数なので、これも使えてしまう。"
},
{
"metadata": {
"collapsed": false,
"trusted": true
},
"cell_type": "code",
"source": "eval(\"__import__('math').sqrt(5)\", {}, {})",
"execution_count": 84,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": "2.23606797749979"
},
"metadata": {},
"execution_count": 84
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "これが意味するのは、たとえeval()を呼び出すときにグローバル・ローカル名前空間に空の辞書を明示的に設定したとしても、悪事を働けるということだ：\n\n```\neval(\"__import__('subprocess').getoutput('rm /some/random/file')\", {}, {})\n```"
},
{
"metadata": {},
"cell_type": "markdown",
"source": " ```\n eval(\"2 ** 2147483647\", {\"__builtins__\":None}, {})\n```\n\n`__builtins__` にアクセスできなかったとしても、なおDOS攻撃を仕掛けることはできる。\n\n例えば、2の2147483647乗は、長時間にわたってサーバのcpu使用率を100%に跳ね上げるだろう（これを対話シェルで試すときは、Ctrl-Cを何回か押して脱出しよう）。\n厳密にいえば、最終的にはこの式は実際に値を返すのだが、その間、サーバは無意味な処理に全力を注ぎ込むことになる。"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## まとめ"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "このプログラムは、ブルートフォースによって（つまり、すべての解候補を総当り的に検索することによって）覆面算パズルを解く。\n\n```\ndef solve(puzzle):\n # 1.`re.findall()`関数を使って、パズルに含まれる文字をすべて見つける\n words = re.findall('[A-Z]+', puzzle.upper())\n # 2. 集合と`set()`関数を使って、パズルに含まれるすべてのユニークな文字を見つける\n unique_characters = set(''.join(words))\n # 3.`assert`文を使って、10個以上のユニークな文字があるかチェックする（その場合、パズルは絶対に解けない）\n assert len(unique_characters) <= 10, 'Too many letters'\n \n first_letters = {word[0] for word in words}\n n = len(first_letters)\n \n # first_lettersを最初に、そのあとに残り\n sorted_characters = ''.join(first_letters) + ''.join(unique_characters - first_letters)\n # 4. ジェネレータオブジェクトを使って、文字を対応するASCIIコードに変換する\n characters = tuple(ord(c) for c in sorted_characters)\n digits = tuple(ord(c) for c in '0123456789')\n zero = digits[0]\n # 5. itertools.permutations()関数を使って、すべての解候補を求める\n for guess in itertools.permutations(digits, len(characters)):\n if zero not in guess[:n]:\n # 6.文字列メソッドのtranslate()を使って、すべての解候補をPythonの式に変換する\n equation = puzzle.translate(dict(zip(characters, guess)))\n # 7.eval()関数を使い、Pythonの式を評価することによってそれぞれの解候補をテストする\n if eval(equation):\n # 8. Trueと評価された最初の解を返す\n return equation\n \n```\n\n1. `re.findall()`関数を使って、パズルに含まれる文字をすべて見つける\n2. 集合と`set()`関数を使って、パズルに含まれるすべてのユニークな文字を見つける\n3. `assert`文を使って、10個以上のユニークな文字があるかチェックする（その場合、パズルは絶対に解けない）\n4. ジェネレータオブジェクトを使って、文字を対応するASCIIコードに変換する\n5. itertools.permutations()関数を使って、すべての解候補を求める\n6. 文字列メソッドのtranslate()を使って、すべての解候補をPythonの式に変換する\n7. eval()関数を使い、Pythonの式を評価することによってそれぞれの解候補をテストする\n8. Trueと評価された最初の解を返す"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## 参考リンク"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "- [Dive Into Python3 8章 高度なイテレータ](http://diveintopython3-ja.rdy.jp/advanced-iterators.html)\n- [itertools — 効率的なループ実行のためのイテレータ生成関数](http://docs.python.jp/3.3/library/itertools.html)\n- [組み込み関数 eval](http://docs.python.jp/3.5/library/functions.html#eval)"
}
],
"metadata": {
"language_info": {
"file_extension": ".py",
"pygments_lexer": "ipython3",
"codemirror_mode": {
"version": 3,
"name": "ipython"
},
"nbconvert_exporter": "python",
"mimetype": "text/x-python",
"name": "python",
"version": "3.5.1"
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3",
"language": "python"
},
"toc": {
"toc_number_sections": true,
"toc_cell": true,
"toc_window_display": false,
"toc_threshold": "6"
},
"gist": {
"id": "",
"data": {
"description": "Dive Into Python3 8章メモ（高度なイテレータ）",
"public": true
}
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment