1_Basics_V.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(chap:5-module)=\n",
    "# モジュール、エラーとアルゴリズム"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div name=\"html-admonition\" style=\"font-size: 0.8em\">\n",
    "<input type=\"button\" onclick=\"location.href='https://translate.google.com/translate?hl=&sl=ja&tl=en&u='+window.location;\" value=\"Google translation\" style=\"color:#ffffff;background-color:#008080; height:25px\" onmouseover=\"this.style.background='#99ccff'\" onmouseout=\"this.style.background='#008080'\"/> in English or the language of your choice.\n",
    "</div><br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 警告メッセージを非表示\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## モジュール、パッケージ、そしてライブラリー"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "### 説明"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Pythonには組み込み関数が多く用意されているが，Jupyter Notebookで`Python`のセッションを開始しても全ての関数が使える状態になっていない。使えるようにするためには，モジュール（modules）、パッケージ（package）、ライブラリー（library）と呼ばれるものを読み込む必要がある。違いを簡単に説明すると次のようになる。\n",
    "* モジュール（module）は**１つ**のファイル（拡張子が`.py`）にまとめられた関数群\n",
    "* パッケージは（package）**複数**つのファイル（拡張子が`.py`）で構成（フォルダーにまとめられている）\n",
    "* ライブラリー（library）は**複数**のパッケージをまとめたもの"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "従って，モジュール全体を読み込んだり，あるパッケージの１つのモジュールだけを読み込むということも可能である。ここでは例として高速計算用の`numpy`モジュールとランダム変数生成用の`random`モジュールを取り上げる。\n",
    "\n",
    "含まれる関数を使うためには`import`を使って読み込む必要がある。モジュールの全てを読み込むとモジュール内の全ての関数が使用可能となる。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true,
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "### `numpy`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "(sec:V-solow)=\n",
    "### `numpy`ライブラリー"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`numpy`はnumerical pythonの略称であり、高速計算や数学に関する関数が多く含まれ、データサイエンスには欠かせないライブラリーである（[詳細はこのリンクを参照](https://numpy.org/doc/stable/user/whatisnumpy.html)）。`numpy`は次のコードで読み込むことができる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "import numpy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "最初の例として平方根を計算してみよう。使う関数名は，square rootの略となる`sqrt()`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "numpy.sqrt(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`numpy.sqrt`とは「`numpy`モジュールの`sqrt`」という意味であり，`numpy`をつけるのは他のモジュールの関数`sqrt`とバッティングしないようにするためである。\n",
    "\n",
    "モジュール名が長い場合は，`as`（「〜として」の意味）を使い短い名前で読み込むことも可能である。`numpy`の場合は`np`としてインポートするのが慣例である。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "np.sqrt(9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "特定の関数だけを読み込むことも可能である。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "from numpy import sqrt, log   # logは自然対数で, sqrtの両方を読み込む"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "このコードは「`numpy`から`sqrt`と`log`を読み込む」と読むことができる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "sqrt(10), log(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "ただ、この場合は他のモジュール、パッケージやライブラリー、もしくは自分が定義した関数とバッティングする可能性があるため注意が必要だ。よく使われる関数名をインポートする場合は、避けた方が良いだろう。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "### `random`モジュール"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`random`モジュールを使うことにより乱数を発生させることができる（[詳細はこのリンクを参照](https://docs.python.org/ja/3/library/random.html)）。まず`random`をインポートしよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "様々な関数が用意されているが，その中の`randint()`関数は，引数で指定するランダムな整数を返す。\n",
    "* 第１引数：最小値（整数型）\n",
    "* 第２引数：最大値（整数型）\n",
    "\n",
    "次のコードは$[1,10]$の間の整数を返す。`1`と`10`は戻り値に含まれることに注意しよう。\n",
    "```\n",
    "random.randint(1, 10)\n",
    "```\n",
    "\n",
    "では実際にコードを実行してみよう。次のコードはサイコロの目（1~6）を１つを返す。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "random.randint(1,6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "内包表記を使って10回サイコロを振った結果を表示してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "[random.randint(1,6) for _ in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "````{note}\n",
    "内包表記に`_`（アンダースコア）を使っている。`i`や`j`を使っても良いが，回数を数える以外に役目はない。その様な場合に良く使われるのが`_`である。`for`ループでも同じことが言える。次のコードが例として挙げられる。\n",
    "```\n",
    "for _ in range(5):\n",
    "    print('hello')\n",
    "```\n",
    "２行目に`_`は入っていないので，ループの回数を数える以外の役割はない。\n",
    "````"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次に，`gauss()`を紹介する。この関数は，正規分布から生成されたランダム変数を１つ返す。引数は次の様になっている。\n",
    "* 第１引数：平均値\n",
    "* 第２引数：標準偏差\n",
    "\n",
    "従って，次のコードは標準正規分布からのランダム変数を生成する。\n",
    "\n",
    "```\n",
    "random.gauss(0, 1)\n",
    "```\n",
    "関数名が`gauss`なのは，正規分布はガウス分布とも呼ばれるためである。\n",
    "\n",
    "\n",
    "次のコードは，平均`10`，標準偏差`2`からランダム変数を生成している。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "random.gauss(10,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "内包表記を使って，標準正規分布から生成された`10`のランダム変数からなるリストを作成しよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "[random.gauss(0,1) for _ in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## エラー"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "エラー（Errors）は次の２つに分けられる。\n",
    "1. 構文エラー（Syntax Errors）\n",
    "    * 構文自体が間違っている場合に発生するエラー（例えば，スペル間違い）。\n",
    "1. 例外（Exceptoins）\n",
    "    * 構文は間違っていなくてもコードの実行中に発生するエラー（例えば，数字を`0`で割る）\n",
    "\n",
    "```{hint}\n",
    "* エラー・メッセージにエラーの理由のヒントがある。はじめは意味が分からないかも知れないが，パターンがあるので慣れると直ぐに理解できるケースも多くあるだろう。\n",
    "* 例外の場合，最初にエラーが発生するとそれに付随して他の場所でもエラーが誘発される場合がある。`Python`はエラーを追跡し，最後に確認したエラーをメッセージの一番最後に表示する。最初は、一番最後のエラー・メッセージを確認しよう！\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "\n",
    "### 構文エラー"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "#### 例１"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "（正）`sum`<br>\n",
    "（誤）`sun`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true,
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "sun([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "* 矢印（---->）でエラー箇所が示されている。\n",
    "* `NameError`として最終行にスペル間違いである`sun`が示されている。\n",
    "* `name 'sun' is not defined`とは「`sun`という名前（変数のこと）は上で定義されていない」という意味。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "#### 例２"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`if`文の最初の行の終わりに`:`が抜けている。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true,
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "a = 3\n",
    "\n",
    "if a > 0\n",
    "\n",
    "    print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "* `line 3`はセル内の３行目（`if`の行）を示している。\n",
    "* `SyntaxError`として３行目の最後で`:`が足りない箇所を`^`で指し示している。\n",
    "* `expected ':'`とは「`:`があるはず」という意味。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "#### 例３"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "括弧を閉じていない。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true,
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "2 / (10.1 + 3.2 + 1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`Python`はプログラマーがどこに`)`を入れようとしたかは分からない。従って，最後に`)`が入ると想定して`^`を文末に置いている。\n",
    "* `incomplete input`とは「不完全なインプット（コード）」という意味。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "### 例外"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "#### 例１"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`0`が分母にある。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true,
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "3 + 1 / 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `division by zero`とは「`0`で除している」という意味。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "#### 例２"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "定義されていない変数`yy`が使われている。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true,
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "1.5 + yy * 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `name 'yy' is not defined`とは「`yy`という名前（変数）は定義されていない」という意味。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "#### 例３"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "整数型と文字列を足している。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true,
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "10 + '3'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `unsupported operand type(s) for +: 'int' and 'str'`とは「`+`に使用不可のデータ型が使われている：整数型と文字列型」という意味。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## アルゴリズム"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "コンピューターは`0`と`1`で書かれている機械語しか理解できないが，プログラマーにとって機械語は非常に難解である。つまりプログラマーとコンピューターは直接「会話」ができない。この問題を解決するために，プログラミング言語が開発され「通訳・翻訳」の役割を担っている。`Python`を使う場合は，`Python`コードを書き，それを`Python`が機械語に「通訳」し，コンピューターが命令を実行することになる。結果が表示されると，プログラマーは内容を確認し，コードを追加・修正などをおこない開発が進んでいく。Jupyter Notebookでコードを書く場合でも同じである。\n",
    "<pre>\n",
    "+--------------+　　Pythonが「通訳」 　+-------+\n",
    "|　Pythonコード　| ▷ ▷ ▷ ▷ ▷ ▷ ▷ ▷ ▷　| 機械語　|\n",
    "+--------------+   　　　　　　　 　   +-------+\n",
    "       ▲                          　  　 ▽\n",
    "       ▲                          　　   ▽\n",
    "       ▲ アルゴリズム       　　　　　　   　▽ 実  \n",
    "       ▲ 疑似コード　　        　      　  ▽ 行  \n",
    "       ▲                          　  　 ▽\n",
    "       ▲                          　　   ▽\n",
    "+-------------+　　　　内容を確認　  　  +-----+\n",
    "|　プログラマー　| ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎　| 結果 |\n",
    "+-------------+     　　　　  　　 　 　+-----+\n",
    "\n",
    "▶︎：プログラマーがおこなう\n",
    "▷：コンピューターがおこなう\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "このサイクルの中で**アルゴリズム**は，プログラマーが`Python`コードを書く際に重要な役割を果たす。日本産業規格（JIS X0001）は次のように定義している。\n",
    "\n",
    "> 問題を解くためのものであって，明確に定義され，順序付けられた有限個の規則からなる集合\n",
    "\n",
    "平たく言えば，コンピューターが実行すると正しい結果が保証された計算手続である。更に，その計算手続きはどのプログラミング言語でも使える問題解決の明確な考え方である。\n",
    "\n",
    "例えば，カレーを作るとしよう。アルゴリズムはその場合のレシピである。ある程度料理ができる人であれば，書かれている手順に沿って作れば美味しいカレーが出来上がるレシピがアルゴリズムである。様々な問題には異なるアルゴリズムがある。また１つの問題には複数のアルゴリズムが存在する。カレーでも色々なレシピがあるのと同じである。\n",
    "\n",
    "以下では，比較的に簡単であり，且つ代表的な４つのアルゴリズムについて解説する。また，アルゴリズムによって計算速度が異なり，その理由についても考えることにする。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "### 例１：合計"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次のコードは標準正規分布から抽出した100万個のランダム変数から構成されるリストを作成する。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "lst1 = [random.gauss(0,1) for _ in range(10**6)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "このリストの値を合計するためのアルゴリズムを考える。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### `for`ループ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "まず`for`ループを使うアルゴリズムを考えてみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def sum_for_loop(lst):  #1\n",
    "    \n",
    "    x = 0               #2\n",
    "    \n",
    "    for i in lst:       #3\n",
    "        x += i          #4\n",
    "    \n",
    "    return x            #5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数はイタラブルであるリストを想定している。\n",
    "* `#2`: `for`ループでは`lst`の要素を１つずつ`x`に加算することになるが，その初期値を`0`とする。\n",
    "* `#3`: `for`ループの開始\n",
    "* `#4`: 累積加算演算子`+=`を使い要素を`x`に加算する。\n",
    "* `#5`: `for`ループ終了後に`lst`の要素の合計である`x`を返す。\n",
    "\n",
    "実際に計算してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "sum_for_loop(lst1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### `while`ループ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次に`while`ループを使う場合のコードを考えてみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def sum_while_loop(lst):     #1\n",
    "    \n",
    "    x = 0                    #2\n",
    "    idx = 0                  #2a\n",
    "    \n",
    "    while idx < len(lst):    #3\n",
    "        \n",
    "        x += lst[idx]        #4\n",
    "        idx += 1             #4a\n",
    "    \n",
    "    return x                 #5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数はイタラブルであるリストを想定している。\n",
    "* `#2`: `for`ループの`x`と同じ役目をする。\n",
    "* `#2a`: `while`ループでは，`lst`の要素を抽出する際にインデックス番号を使うことになるが，`idx`（indexの略）はインデックス番号を捉えている。`lst`の最初の項から抽出するために初期値を`0`としている。\n",
    "* `#3`: `while`ループが開始され，`idx<len(lst)`が`False`となる時点でループは終了する。例として，`lst=[0,10,20]`としてみよう。`len(lst)`は`3`を返すことになり，`idx`が`3`になると`idx<len(lst)`が`False`となるため，その時点で（`#5`以下は実行されずに）`while`ループは終了する。\n",
    "* `#4`: `lst[idx]`では`lst`の`idx`番目の要素を抽出し，それを`+=`を使い`x`に加算する。\n",
    "* `#4a`: 次のループで`lst`の次の要素を抽出できるように`idx`を`1`増やし`while`ループを継続する。\n",
    "* `#5`: `for`ループ終了後に`lst`の要素の合計である`x`を返す。\n",
    "\n",
    "実際に計算してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "sum_while_loop(lst1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`for`ループと同じ値となっていることが確認できる。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### 実行スピード比較"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次に２つのコードの終了までの時間を比較してみよう。ここでは[マジック・コマンド](https://ipython.readthedocs.io/en/stable/interactive/magics.html)と呼ばれる`%timeit`を使うが，使い方は簡単で行頭に`%timeit`と半角スペースを置いて実行コードを書くだけである。まず`sum_for_loop()`関数を実行してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit sum_for_loop(lst1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "表示される結果は，使うPCのスペックなどによって若干異なることになる。\n",
    "結果の解釈方法を説明するため，次のような結果になったとしよう。\n",
    "\n",
    "```\n",
    "MMM ms ± NNN µs per loop (mean ± std. dev. of YYY runs, XXX loops each)\n",
    "```\n",
    "\n",
    "次のように解釈する。\n",
    "* コードを`XXX`回実行する試行を`YYY`回おこない（合計で`XXX`$\\times$`YYY`回），その結果の平均である`mean`は`MMM ms`であり，標準偏差である`std. dev.`は`NNN µs`である。ここで\n",
    "    * `ms`：ミリ秒（1/1000秒）\n",
    "    * `µs`：マイクロ秒（1/1,000,000秒）\n",
    "    * `ns`：ナノ秒（1/1,000,000,000秒; 10億分の１秒）\n",
    "    \n",
    "* 試行する度に結果が異り，その変動を標準偏差で捉えている。結果は正規分布に従うと仮定すると，約68％の結果が平均$\\pm$標準偏差の範囲内に収まることになる。\n",
    "\n",
    "次に`sum_while_loop()`の速度を計測してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit sum_while_loop(lst1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`while`ループに比べて`for`ループが約4倍速いことが確認できる。リストから要素を一つずつ抽出し合計するというアルゴリズムでも，コードにどのように表現するかによって速度に大きな違いが発生している。\n",
    "\n",
    "では，なぜそのような大きな違いがあるのだろうか。それは次の２つの違いに起因する。\n",
    "* `sum_for_loop()`と`sum_while_loop()`の`#3`を考えてみよう。前者の場合，ループ毎に`lst`の要素を`i`に割り当てることを行なっている。一方，後者では，ループ毎に`idx<len(lst)`の条件が満たされているかどうかを確認する必要がある。\n",
    "* `sum_while_loop()`では`#2a`と`#4a`が追加されており，「割り当て」と言う意味では`sum_for_loop()`の`#3`と同じである。\n",
    "\n",
    "従って，`while`ループには`idx<len(lst)`が`True`なのか`False`なのかの確認が追加作業となり，それが時間が掛かる要因となっている。\n",
    "\n",
    "最後に，組み込み関数である`sum()`の速度を計測してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit sum(lst1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`sum_while_loop()`関数よりも6倍以上も速いことが分かる。組み込み関数は様々なトリックを使い最適化されていることが伺える。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "````{hint}\n",
    "複数行にまたがるコードの実行スピードを計測する場合は，下の例のように`%%timeit`を１行目に置き，2行目以降にコードを書くと良いだろう。\n",
    "```\n",
    "%%timeit\n",
    "sum_while_loop(lst1)\n",
    "print('Pythonは楽しいね(^o^)/')\n",
    "```\n",
    "````"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "### 例２：値の探索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次のコードは`0`から`999,999`までの整数が並ぶリストを作成する。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "lst2 = list(range(1_000_000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "ここで考えるのは，`999,000`が`lst2`にあるかどうかを確かめることである。具体的には，`lst2`の最初の要素から一つずつ確認し\n",
    "* 見つかれば`1`を返す（探索は途中で終了）\n",
    "* 見つからなければ`-1`を返す（最後の要素まで確認する）\n",
    "\n",
    "関数を考える。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "#### `for`ループ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "(sec:5-for-loop)=\n",
    "#### `for`ループ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`for`ループを使うコードを考えよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def search_for_loop(target, lst): #1\n",
    "\n",
    "    for i in lst:                 #2\n",
    "\n",
    "        if i == target:           #3\n",
    "            return 1              #4\n",
    "    \n",
    "    return -1                     #5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数の`target`は探索する数字であり，`lst`はイタラブルであるリストを想定している。\n",
    "* `#2`: `for`ループの開始\n",
    "* `#3`〜`#4`: `i`が`target`と等しければ`1`を返し，`for`ループは終了する。\n",
    "    * `#4`が実行されると，関数の実行は終わる。これは`return`には，「関数の実行を終了させる」役割があるため。\n",
    "* `#5`: `#4`の実行されずに`for`ループ終了した場合にのみ実行され`-1`が返される。即ち，`lst`の最後まで探索し，`target`がない場合に実行される行である。\n",
    "\n",
    "実際に計算してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "search_for_loop(999_000, lst2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true,
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "#### `while`ループ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "(sec:5-while-loop)=\n",
    "#### `while`ループ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次に`while`ループを使う場合を考えてみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def search_while_loop(target, lst): #1\n",
    "    \n",
    "    idx = 0                         #2\n",
    "\n",
    "    while True:                     #3\n",
    "        \n",
    "        if idx == len(lst):         #4\n",
    "            return -1               #5\n",
    "        \n",
    "        elif lst[idx] == target:    #6\n",
    "            return 1                #7\n",
    "        \n",
    "        idx += 1                    #8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数の`target`は探索する数字であり，`lst`はイタラブルであるリストを想定している。\n",
    "* `#2`: `while`ループでは，`lst`の要素を抽出する際にインデックス番号を使うことになるが，`idx`（indexの略）はインデックス番号を捉えている。`#4`と`#6`で使う。`lst`の最初の項から抽出するために初期値を`0`としている。\n",
    "* `#3`: `while`ループの開始。`#5`もしくは`#7`が実行されるまで`while`ループは継続する。\n",
    "* `#4`〜`#5`: `#4`の条件は`lst`の最後の要素まで確認した場合にのみ満たされる。その場合，`-1`が返される。\n",
    "    * `#5`が実行されると，関数の実行は終わる。これは`return`には，「関数の実行を終了させる」役割があるため。\n",
    "* `#6`〜`#7`: `lst`の`idx`番目の要素と`target`が等しい場合に`1`が返される。その時点で関数の実行（`while`ループも含めて）は終了する。\n",
    "    * `#7`が実行されると，関数の実行は終わる。これは`return`には，「関数の実行を終了させる」役割があるため。\n",
    "* `#8`: `#4`と`#5`の条件が`False`であれば，`idx`を`1`増加させて`while`ループを継続する。\n",
    "\n",
    "実際に計算してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "search_while_loop(999_000, lst2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`search_for_loop()`関数と`search_while_loop()`関数の実行スピードを比較してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit search_for_loop(999_000, lst2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit search_while_loop(999_000, lst2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`for`ループより`while`ループは4倍以上遅いことがわかる。もう理由は明らかであろう。`search_linear_for()`関数ではループ一回毎に１つの`if`文の条件`#3`を確認する必要があるが，`search_linear_while()`では条件が`#4`と`#6`の２つがある。この確認作業の回数の差が数字として現れている。このことから分かることは，`while`ループであっても条件を１つにすれば速度が倍になると言うことである。それを実現するのが次に考える**番兵法**と呼ばれるアルゴリズムである。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### 番兵法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "番兵法は`while`ループを使うが，次の手続きが必要となる。\n",
    "* リストの最後に探索する値を追加する\n",
    "\n",
    "`search_while_loop()`関数との違いはこの点だけである。これにより，実質的には`search_linear_while()`の条件`#4`が不要になり実行スピードの高速化される。コードを確認してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def search_sentinel(target, lst): #1\n",
    "    \n",
    "    size = len(lst)               #2\n",
    "\n",
    "    lst.append(target)            #3\n",
    "    \n",
    "    idx = 0                       #4\n",
    "\n",
    "    while True:                   #5\n",
    "        \n",
    "        if lst[idx] == target:    #6\n",
    "            break                 #7\n",
    "            \n",
    "        idx += 1                  #8\n",
    "\n",
    "    if idx < size:                #9\n",
    "        return 1                  #10\n",
    "    \n",
    "    else:                         #11\n",
    "        return -1                 #12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数の`target`は探索する数字であり，`lst`はイタラブルであるリストを想定している。\n",
    "* `#2`: `lst`の要素数を`size`に割り当てる。`size`は`#9`で使うことになる。\n",
    "* `#3`: `lst`の最後に`target`を追加する。これが「番兵」である。\n",
    "* `#4`: `lst`の要素を抽出する際にインデックス番号を使うことになるが，`idx`（indexの略）はインデックス番号を捉えている。`#6`，`#8`，`#9`で使う。`lst`の最初の項から抽出するために初期値を`0`としている。\n",
    "* `#5`: `while`ループの開始。\n",
    "* `#6`〜`#7`: `lst`の`idx`番目の要素と`target`が等しい場合は`break`を発動させ`while`を中断する。等しくない場合は`#7`を実行せずに`#8`で`idx`を`1`増加さる。`#3`で`target`（番兵）が`lst`に追加されたので，`lst`に`target`がなくても`#6`は必ず満たされて`break`が発動される。これが番兵の役割であり，高速化のための仕込みとなる。\n",
    "* `#9`〜`#12`: `while`ループが中断された後に実行される。`#9`の条件が`True`の場合は`lst`に`target`が含まれたと言う意味になるため`1`を返す。一方，`#9`の条件が`False`の場合（即ち，`idx`と`size`は等しい場合），`idx`は番兵のインデックスとなるため`-1`を返す。\n",
    "\n",
    "＜`break`と`return`の違い＞<br>\n",
    "* `break`はループを終わらせるだけであり，関数の実行は続くことになる。\n",
    "* 既出の`search_for_loop()`関数や`search_while_loop()`関数で明らか様に，`return`は関数の評価を終了させる役割がある。従って，ループ計算が最後まで終わっていなくても，`return`が実行されると関数の実行が終わることにより，その時点でループ計算は終了することになる。\n",
    "\n",
    "実際に計算してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "search_sentinel(999_000, lst2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "実行スピードを計測してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit search_sentinel(999_000, lst2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`search_while_loop()`関数と比べると約2倍高速化できた。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### 組み込み関数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "組み込み関数に`1`もしくは`-1`を返す関数は見当たらないため，類似するメソッドを考えてみよう。リストには`.index()`というメソッドが用意されており，引数に要素を指定すると，その要素のインデックス番号を返す。試してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "lst2.index(999_000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`999_000`は`lst2`の`999000`番目の要素だという意味。実行速度を計測してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit lst2.index(999_000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "`search_for_loop()`関数よりも約2倍速い。最適化されていることが伺える。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "### 例３：最小値の探索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次のコードは標準正規分布から抽出した100万個のランダム変数から構成されるリストを作成する。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "lst3 = [random.gauss(0,1) for _ in range(1_000_000)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "この中から最小値を探索するアルゴリズムを考えてみよう。`lst3`の全ての要素を確認する必要があるので`for`ループを使おう。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### 直接的な探索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "まず，リストの最小値を直接探索するコードを考えてみる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def search_min(lst):  #1\n",
    "    \n",
    "    min_ = lst[0]     #2\n",
    "    \n",
    "    for v in lst[1:]: #3\n",
    "        \n",
    "        if v < min_:  #4            \n",
    "            min_ = v  #5\n",
    "    \n",
    "    return min_       #6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数`lst`はイタラブルであるリストを想定している。\n",
    "* `#2`: `lst`の`0`番目の値を`min_`に割り当てる。`#3`の`for`ループで更に小さな値が発見されれば，`min_`の値と入れ替えることにする。\n",
    "* `#3`: `lst`に対する`for`ループの開始。\n",
    "    * `#2`で`0`番目の要素が`min_`に割り当てられているので，`for`ループは`1`番目の要素から始める。\n",
    "* `#4`〜`#5`: `v`が`min_`より小さければ`min_`に割り当てる。そうでなければ，`min_`の値は変えない。\n",
    "* `#6`: `for`ループが終わった後（即ち，`lst`の値を全て確認した後），`min_`の値を返す。\n",
    "\n",
    "実際に計算してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "search_min(lst3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### 間接的な探索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "リストの要素はインデックス番号を使ってアクセスすることができる。それを利用して，上のコードをインデックス番号を使って間接的に要素にアクセスする場合を考える。即ち，最小値のインデックスを探し，最終的に最小値を返す関数となる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def search_min_idx(lst):            #1\n",
    "    \n",
    "    n_lst = len(lst)                #2\n",
    "    \n",
    "    idx_min = 0                     #3\n",
    "    \n",
    "    for idx in range(1,n_lst):      #4\n",
    "        \n",
    "        if lst[idx] < lst[idx_min]: #5\n",
    "            idx_min = idx           #6\n",
    "    \n",
    "    return lst[idx_min]             #7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数`lst`はイタラブルであるリストを想定している。\n",
    "* `#2`: `lst`の要素数を`n_lst`に割り当てる。`n_lst`は`#4`で使うことになる。\n",
    "* `#3`: `idx_min`は最小値の要素のインデックス番号を割り当てる変数として使う。`0`番目の要素から考えるので，初期値として`0`を設定している。\n",
    "* `#4`: `range(1,n_lst)`に対する`for`ループの開始。\n",
    "    * `#3`でインデック`0`が`idx_min`に割り当てられているので，`for`ループはインデックス`1`から始める。\n",
    "* `#5`〜`#6`: `lst[idx_min]`は，その時点で最小値となる値である。その値より`lst[idx]`が小さい場合，`idx`を`idx_min`に割り当てることにより`idx_min`のインデックス番号を更新する。そうでない場合は`idx_min`の値は変更しない。\n",
    "が`min_`より小さければ`min_`に割り当てる。そうでなければ，`min_`の値は変えない。\n",
    "* `#7`: `for`ループが終わった後（即ち，`lst`の値を全て確認した後），`idx_min`に対応する要素を返す。\n",
    "\n",
    "実際に計算してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "search_min_idx(lst3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### 実行スピード比較"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "それぞれのコードの実行速度を比べてみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit search_min(lst3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit search_min_idx(lst3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "間接的にインデックス番号を使うと実行速度を減速させることになる。\n",
    "\n",
    "次に組み込み関数である`min()`と比べてみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "min(lst3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit min(lst3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "直接的な方法より2倍以上高速実行されている。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "### 例４：ソート"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次のコードは`0`から`999`までの整数をランダムに並べたリストを作成する。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "lst4 = [random.randint(0,1000) for _ in range(1_000)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "このリストを昇順に並び替えるコードを考える。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### 単純選択ソート"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "最初に考えるアルゴリズムである単純選択ソートは次のような考え方に基づいている。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "リストには`0`番目から`n-1`番目の要素があるとしよう。\n",
    "* 要素の数は`n`\n",
    "* `n>1`とする。\n",
    "\n",
    "アルゴリズム（説明をより明確になるようにループを`0`回目から数える。）\n",
    "* `0`回目のループ（外側ループ）\n",
    "    * `0`番目から最後までの要素の最小値を見つける（内側ループ）\n",
    "    * 最小値を`0`番目の要素と入れ替える（値の入れ替え）\n",
    "* `1`回目のループ（外側ループ）\n",
    "    * `1`番目から最後までの要素の最小値を見つける（内側ループ）\n",
    "    * 最小値を`1`番目の要素と入れ替える（値の入れ替え）\n",
    "* `2`回目のループ（外側ループ）\n",
    "    * `2`番目から最後までの要素の最小値を見つける（内側ループ）\n",
    "    * 最小値を`2`番目の要素と入れ替える（値の入れ替え）\n",
    "* ......\n",
    "* `n-2`回目のループ（外側ループ）\n",
    "    * `n-2`番目から最後までの要素の最小値を見つける（内側ループ）\n",
    "    * 最小値を`n-2`番目の要素と入れ替える（値の入れ替え）\n",
    "    \n",
    "（注意）`n-1`回目のループは必要ない。\n",
    "    \n",
    "この手順に基づくコードを確認しよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def insertion_sort(lst):       #1\n",
    "    \n",
    "    n = len(lst)               #2\n",
    "    \n",
    "    for i in range(n-1):       #3\n",
    "        \n",
    "        i_min = i              #4\n",
    "        \n",
    "        for j in range(i+1,n): #5\n",
    "            \n",
    "            if lst[j] < lst[i_min]:  #6  \n",
    "                i_min = j            #7\n",
    "        \n",
    "        lst[i], lst[i_min] = lst[i_min], lst[i]  #8\n",
    "    \n",
    "    return lst                 #9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数`lst`はイタラブルであるリストを想定している。\n",
    "* `#2`: `lst`の要素数を`n`に割り当てる。`n`は`#3`と`#5`で使うことになる。\n",
    "* `#3`: 上の説明にある「外側ループ」に対応している。合計で`n-2`回のループ計算をおこなう（最後のインデックス番号である`n-1`を使ったループを考える必要はないため）。\n",
    "* `#4`: `i_min`は`#5`の`for`ループ（上の説明にある「内側ループ」）で見つかる最小値を割り当てる変数のインデックス番号として使う。\n",
    "* `#5`: 上の説明にある「内側ループ」に対応している。`i`を所与として，`i+1`から`n-1`番目までのループとなる（最小値を探索するためには最後まで確認する必要があるため）。\n",
    "* `#6`〜`#7`: `lst[j]`が`lst[i_min]`より小さければ`j`を`i_min`に割り当てる。そうでなければ，`i_min`の値は変えない。\n",
    "* `#8`: 上の説明にある「値を入れ替え」に対応している。`#5`の内側ループが終わった後（即ち，`i+1`から`lst`の全ての値を確認した後），`lst[i]`と`lst[i_min]`入れ替えている。\n",
    "* `#9`: 外側ループが終わった後，`lst`を返す。\n",
    "\n",
    "コードを実行し，最初の`10`の要素を表示してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "res = insertion_sort(lst4)\n",
    "res[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "最後の`10`の要素を表示してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "res[990:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "昇順に並んでいることが確認できる。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### バブル・ソート"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "次にバブル・ソートと呼ばれるアルゴリズムを考えてみよう。手順は次の内容となる。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "リストには`0`番目から`n-1`番目の要素があるとしよう。\n",
    "* 要素の数は`n`\n",
    "* `n>1`とする。\n",
    "\n",
    "アルゴリズム（ここではループを`1`回目から数える。）\n",
    "* `1`回目のループ（外側ループ）\n",
    "    * （以下の手順が内側ループ）\n",
    "    * `n-2`番目と`n-1`番目（最後）の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * `n-3`番目と`n-2`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * ......\n",
    "    * `1`番目と`2`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * `0`番目と`1`番目の要素を比べる\n",
    "    * 小さい方を左に，大きい方を右に入れ替える\n",
    "    * 同じであれば何もしない\n",
    "    * これで`0`番目の要素は`0`番目から`n-1`番目の要素の最小値となる。\n",
    "* `2`回目のループ（外側ループ）\n",
    "    * 以下の手順が内側ループ\n",
    "    * `n-2`番目と`n-1`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * `n-3`番目と`n-2`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * ......\n",
    "    * `2`番目と`3`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * `1`番目と`2`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * これで`1`番目の要素は`1`番目から`n-1`番目の要素の最小値となる。\n",
    "* ......\n",
    "* `n-2`回目のループ（外側ループ）\n",
    "    * 以下の手順が内側ループ\n",
    "    * `n-2`番目と`n-1`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * `n-3`番目と`n-2`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * これで`n-3`番目の要素は`n-3`番目から`n-1`番目の要素の最小値となる。\n",
    "* `n-1`回目のループ（外側ループ）\n",
    "    * 以下の手順が内側ループ\n",
    "    * `n-2`番目と`n-1`番目の要素を比べる\n",
    "        * 小さい方を左に，大きい方を右に入れ替える\n",
    "        * 同じであれば何もしない\n",
    "    * これで`n-2`番目の要素は`n-2`番目から`n-1`番目の要素の最小値となる。\n",
    "* 完成！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def bubble_sort(lst):    #1\n",
    "    \n",
    "    n = len(lst)         #2\n",
    "    \n",
    "    for i in range(n-1): #3\n",
    "        \n",
    "        for j in range(n-1, i, -1): #4\n",
    "            \n",
    "            if lst[j-1] > lst[j]:   #5                \n",
    "                lst[j-1], lst[j] = lst[j], lst[j-1] #6\n",
    "    \n",
    "    return lst           #7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "＜コードの説明＞<br>\n",
    "* `#1`: 引数`lst`はイタラブルであるリストを想定している。\n",
    "* `#2`: `lst`の要素数を`n`に割り当てる。`n`は`#3`と`#4`で使うことになる。\n",
    "* `#3`: 上の説明にある「外側ループ」に対応している。合計で`n-1`回のループ計算をおこない，`lst`の全ての要素インデックスに対応している。\n",
    "* `#4`: 上の説明にある「内側ループ」に対応している。`range(n-1, i, -1)`は`i+1`から`n-1`までの番号を逆順に並べている。例えば，`list(range(10, 5, -1))`は`[10,9,8,7,6]`を返す。これは`#5`と`#6`に置いて最後の要素から始まってから`i+1`番目の要素までを順に考える必要があるため。\n",
    "* `#5`〜`#6`: `lst[j-1]>lst[j]`とは左の要素が右の要素より大きい場合に`True`を返し，その場合，`#6`では左右の要素を入れ替えている。`#6`は上の説明の２つの要素の入れ替えに対応している。\n",
    "* `#7`: 外側ループが終わった後，`lst`を返す。\n",
    "\n",
    "コードを実行し，最初の`10`の要素を表示してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "res = bubble_sort(lst4)\n",
    "res[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "最後の`10`の要素を表示してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "res[990:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "#### 実行スピード比較"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "それぞれの実行スピードを比較してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit insertion_sort(lst4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit bubble_sort(lst4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "スピードの違いの一つの要因は「値の入れ替え」の回数の差である。\n",
    "`insertion_sort()`の場合，`#8`で値の入れ替えがおこなわれており，最大で$n-1$回となる。\n",
    "一方，`bubble_sort()`の値の入れ替えは`#6`でおこなわれており，最大で$n^2/2$回となる。\n",
    "$n>2$の場合，$n^2/2>n-1$となるため，実行時間の差に現れていると考えられる。\n",
    "\n",
    "最後に組み込み関数`sorted()`と比較してみよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "%timeit sorted(lst4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "平均の単位は`ms`ではなく`µs`となっている。やはり組み込み関数は速い！"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}