day 45 - binary search tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.linear_model import LinearRegression\n",
    "from bokeh.plotting import figure, show, output_notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def search(node, value):\n",
    "    if node:\n",
    "        x, left, right = node\n",
    "        this = value == x\n",
    "        lsearch = value < x and search(left, value)\n",
    "        rsearch = value > x and search(right, value)\n",
    "        return this or lsearch or rsearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def add(node, value):\n",
    "    if node:\n",
    "        x, left, right = node\n",
    "        this = value == x and node\n",
    "        ladd = value < x and (x, add(left, value), right)\n",
    "        radd = value > x and (x, left, add(right, value))\n",
    "        return this or ladd or radd\n",
    "    return value, None, None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def depth(node):\n",
    "    return node and max(depth(node[1]), depth(node[2])) + 1 or 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def iterate(node):\n",
    "    if node:\n",
    "        x, left, right = node\n",
    "        yield from iterate(left)\n",
    "        yield x\n",
    "        yield from iterate(right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "depth 7\n",
      "[0, 2, 3, 4, 6, 7, 9, 11, 12, 14, 16]\n",
      "10 False\n",
      "16 True\n"
     ]
    }
   ],
   "source": [
    "data = [2, 16, 4, 2, 2, 11, 9, 0, 14, 11, 11, 9, 12, 7, 2, 12, 3, 9, 6, 12]\n",
    "\n",
    "root = None\n",
    "for value in data:\n",
    "    root = add(root, value)\n",
    "    \n",
    "print('depth', depth(root))\n",
    "print(list(iterate(root)))\n",
    "print(10, search(root, 10))\n",
    "print(16, search(root, 16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## simulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tree_vs_depth = {\n",
    "    10: [], 20: [], 50: [], \n",
    "    100: [], 200: [], 500: [], \n",
    "    1000: [], 2000: []\n",
    "}\n",
    "\n",
    "for _ in range(1000):\n",
    "    root = None\n",
    "    for i, value in enumerate(np.random.randint(100000, size=2500)):\n",
    "        root = add(root, value)\n",
    "        if i + 1 in tree_vs_depth:\n",
    "            tree_vs_depth[i + 1].append(depth(root))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## statistics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  10 items: depth[mean,min,max,std]=[ 5.6  4.   9.   0.9]\n",
      "  20 items: depth[mean,min,max,std]=[  7.7   5.   13.    1.2]\n",
      "  50 items: depth[mean,min,max,std]=[ 10.8   8.   19.    1.5]\n",
      " 100 items: depth[mean,min,max,std]=[ 13.3  10.   22.    1.5]\n",
      " 200 items: depth[mean,min,max,std]=[ 15.8  12.   25.    1.7]\n",
      " 500 items: depth[mean,min,max,std]=[ 19.3  15.   28.    1.8]\n",
      "1000 items: depth[mean,min,max,std]=[ 22.   18.   30.    1.9]\n",
      "2000 items: depth[mean,min,max,std]=[ 24.7  21.   33.    1.9]\n"
     ]
    }
   ],
   "source": [
    "x, y = [], []\n",
    "\n",
    "for i, d in tree_vs_depth.items():\n",
    "    x.append([np.log(i)])\n",
    "    y.append([np.mean(d), np.min(d), np.max(d), np.std(d)])\n",
    "    print('{:4} items: depth[mean,min,max,std]={}'.format(i, np.round(y[-1], 1)))\n",
    "    \n",
    "x, y = np.array(x), np.array(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mean 3.62404195054 -3.14916237239\n",
      "min 3.21930613708 -4.4059750537\n",
      "max 4.4103123923 0.413246463845\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/tobbi/anaconda/lib/python3.6/site-packages/scipy/linalg/basic.py:1018: RuntimeWarning: internal gelsd driver lwork query error, required iwork dimension not returned. This is likely the result of LAPACK bug 0038, fixed in LAPACK 3.2.2 (released July 21, 2010). Falling back to 'gelss' driver.\n",
      "  warnings.warn(mesg, RuntimeWarning)\n"
     ]
    }
   ],
   "source": [
    "model_mean = LinearRegression().fit(x, y[:, 0])\n",
    "print('mean', model_mean.coef_[0], model_mean.intercept_)\n",
    "\n",
    "model_min = LinearRegression().fit(x, y[:, 1])\n",
    "print('min', model_min.coef_[0], model_min.intercept_)\n",
    "\n",
    "model_max = LinearRegression().fit(x, y[:, 2])\n",
    "print('max', model_max.coef_[0], model_max.intercept_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <a href=\"http://bokeh.pydata.org\" target=\"_blank\" class=\"bk-logo bk-logo-small bk-logo-notebook\"></a>\n",
       "        <span id=\"ac8820c8-0096-4d95-8516-cc729a1b0731\">Loading BokehJS ...</span>\n",
       "    </div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "\n",
       "(function(global) {\n",
       "  function now() {\n",
       "    return new Date();\n",
       "  }\n",
       "\n",
       "  var force = true;\n",
       "\n",
       "  if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "    window._bokeh_onload_callbacks = [];\n",
       "    window._bokeh_is_loading = undefined;\n",
       "  }\n",
       "\n",
       "\n",
       "  \n",
       "  if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "    window._bokeh_timeout = Date.now() + 5000;\n",
       "    window._bokeh_failed_load = false;\n",
       "  }\n",
       "\n",
       "  var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "     \"<div style='background-color: #fdd'>\\n\"+\n",
       "     \"<p>\\n\"+\n",
       "     \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "     \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "     \"</p>\\n\"+\n",
       "     \"<ul>\\n\"+\n",
       "     \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "     \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "     \"</ul>\\n\"+\n",
       "     \"<code>\\n\"+\n",
       "     \"from bokeh.resources import INLINE\\n\"+\n",
       "     \"output_notebook(resources=INLINE)\\n\"+\n",
       "     \"</code>\\n\"+\n",
       "     \"</div>\"}};\n",
       "\n",
       "  function display_loaded() {\n",
       "    if (window.Bokeh !== undefined) {\n",
       "      document.getElementById(\"ac8820c8-0096-4d95-8516-cc729a1b0731\").textContent = \"BokehJS successfully loaded.\";\n",
       "    } else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(display_loaded, 100)\n",
       "    }\n",
       "  }\n",
       "\n",
       "  function run_callbacks() {\n",
       "    window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "    delete window._bokeh_onload_callbacks\n",
       "    console.info(\"Bokeh: all callbacks have finished\");\n",
       "  }\n",
       "\n",
       "  function load_libs(js_urls, callback) {\n",
       "    window._bokeh_onload_callbacks.push(callback);\n",
       "    if (window._bokeh_is_loading > 0) {\n",
       "      console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "      return null;\n",
       "    }\n",
       "    if (js_urls == null || js_urls.length === 0) {\n",
       "      run_callbacks();\n",
       "      return null;\n",
       "    }\n",
       "    console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "    window._bokeh_is_loading = js_urls.length;\n",
       "    for (var i = 0; i < js_urls.length; i++) {\n",
       "      var url = js_urls[i];\n",
       "      var s = document.createElement('script');\n",
       "      s.src = url;\n",
       "      s.async = false;\n",
       "      s.onreadystatechange = s.onload = function() {\n",
       "        window._bokeh_is_loading--;\n",
       "        if (window._bokeh_is_loading === 0) {\n",
       "          console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "          run_callbacks()\n",
       "        }\n",
       "      };\n",
       "      s.onerror = function() {\n",
       "        console.warn(\"failed to load library \" + url);\n",
       "      };\n",
       "      console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "      document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "    }\n",
       "  };var element = document.getElementById(\"ac8820c8-0096-4d95-8516-cc729a1b0731\");\n",
       "  if (element == null) {\n",
       "    console.log(\"Bokeh: ERROR: autoload.js configured with elementid 'ac8820c8-0096-4d95-8516-cc729a1b0731' but no matching script tag was found. \")\n",
       "    return false;\n",
       "  }\n",
       "\n",
       "  var js_urls = [\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.4.min.js\"];\n",
       "\n",
       "  var inline_js = [\n",
       "    function(Bokeh) {\n",
       "      Bokeh.set_log_level(\"info\");\n",
       "    },\n",
       "    \n",
       "    function(Bokeh) {\n",
       "      \n",
       "      document.getElementById(\"ac8820c8-0096-4d95-8516-cc729a1b0731\").textContent = \"BokehJS is loading...\";\n",
       "    },\n",
       "    function(Bokeh) {\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-0.12.4.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.4.min.css\");\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.4.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.4.min.css\");\n",
       "    }\n",
       "  ];\n",
       "\n",
       "  function run_inline_js() {\n",
       "    \n",
       "    if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "      for (var i = 0; i < inline_js.length; i++) {\n",
       "        inline_js[i](window.Bokeh);\n",
       "      }if (force === true) {\n",
       "        display_loaded();\n",
       "      }} else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(run_inline_js, 100);\n",
       "    } else if (!window._bokeh_failed_load) {\n",
       "      console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "      window._bokeh_failed_load = true;\n",
       "    } else if (force !== true) {\n",
       "      var cell = $(document.getElementById(\"ac8820c8-0096-4d95-8516-cc729a1b0731\")).parents('.cell').data().cell;\n",
       "      cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "    }\n",
       "\n",
       "  }\n",
       "\n",
       "  if (window._bokeh_is_loading === 0) {\n",
       "    console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "    run_inline_js();\n",
       "  } else {\n",
       "    load_libs(js_urls, function() {\n",
       "      console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "      run_inline_js();\n",
       "    });\n",
       "  }\n",
       "}(this));"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <div class=\"bk-plotdiv\" id=\"ad46a499-4596-4a9c-9119-a493a44f32de\"></div>\n",
       "    </div>\n",
       "<script type=\"text/javascript\">\n",
       "  \n",
       "  (function(global) {\n",
       "    function now() {\n",
       "      return new Date();\n",
       "    }\n",
       "  \n",
       "    var force = false;\n",
       "  \n",
       "    if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "      window._bokeh_onload_callbacks = [];\n",
       "      window._bokeh_is_loading = undefined;\n",
       "    }\n",
       "  \n",
       "  \n",
       "    \n",
       "    if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "      window._bokeh_timeout = Date.now() + 0;\n",
       "      window._bokeh_failed_load = false;\n",
       "    }\n",
       "  \n",
       "    var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "       \"<div style='background-color: #fdd'>\\n\"+\n",
       "       \"<p>\\n\"+\n",
       "       \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "       \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "       \"</p>\\n\"+\n",
       "       \"<ul>\\n\"+\n",
       "       \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "       \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "       \"</ul>\\n\"+\n",
       "       \"<code>\\n\"+\n",
       "       \"from bokeh.resources import INLINE\\n\"+\n",
       "       \"output_notebook(resources=INLINE)\\n\"+\n",
       "       \"</code>\\n\"+\n",
       "       \"</div>\"}};\n",
       "  \n",
       "    function display_loaded() {\n",
       "      if (window.Bokeh !== undefined) {\n",
       "        document.getElementById(\"ad46a499-4596-4a9c-9119-a493a44f32de\").textContent = \"BokehJS successfully loaded.\";\n",
       "      } else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(display_loaded, 100)\n",
       "      }\n",
       "    }\n",
       "  \n",
       "    function run_callbacks() {\n",
       "      window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "      delete window._bokeh_onload_callbacks\n",
       "      console.info(\"Bokeh: all callbacks have finished\");\n",
       "    }\n",
       "  \n",
       "    function load_libs(js_urls, callback) {\n",
       "      window._bokeh_onload_callbacks.push(callback);\n",
       "      if (window._bokeh_is_loading > 0) {\n",
       "        console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "        return null;\n",
       "      }\n",
       "      if (js_urls == null || js_urls.length === 0) {\n",
       "        run_callbacks();\n",
       "        return null;\n",
       "      }\n",
       "      console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "      window._bokeh_is_loading = js_urls.length;\n",
       "      for (var i = 0; i < js_urls.length; i++) {\n",
       "        var url = js_urls[i];\n",
       "        var s = document.createElement('script');\n",
       "        s.src = url;\n",
       "        s.async = false;\n",
       "        s.onreadystatechange = s.onload = function() {\n",
       "          window._bokeh_is_loading--;\n",
       "          if (window._bokeh_is_loading === 0) {\n",
       "            console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "            run_callbacks()\n",
       "          }\n",
       "        };\n",
       "        s.onerror = function() {\n",
       "          console.warn(\"failed to load library \" + url);\n",
       "        };\n",
       "        console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      }\n",
       "    };var element = document.getElementById(\"ad46a499-4596-4a9c-9119-a493a44f32de\");\n",
       "    if (element == null) {\n",
       "      console.log(\"Bokeh: ERROR: autoload.js configured with elementid 'ad46a499-4596-4a9c-9119-a493a44f32de' but no matching script tag was found. \")\n",
       "      return false;\n",
       "    }\n",
       "  \n",
       "    var js_urls = [];\n",
       "  \n",
       "    var inline_js = [\n",
       "      function(Bokeh) {\n",
       "        (function() {\n",
       "          var fn = function() {\n",
       "            var docs_json = {\"1a125c96-f484-4c83-8080-40101816f7c1\":{\"roots\":{\"references\":[{\"attributes\":{},\"id\":\"69d31097-18b2-4c0d-8f52-92599b9cb9ba\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"data_source\":{\"id\":\"db5c6b6a-62ff-4400-a708-76e0f2c33492\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"a18b7326-b64c-4225-b0e9-b09302313c30\",\"type\":\"Circle\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"7b1e2bb0-c837-4357-9c32-9076899d36bf\",\"type\":\"Circle\"},\"selection_glyph\":null},\"id\":\"a0c2e1d8-f1ea-4dda-9ee7-97e2f4e622d7\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"plot\":null,\"text\":\"\"},\"id\":\"a4aa3b4a-e187-4856-8938-e8c1d7b68b9e\",\"type\":\"Title\"},{\"attributes\":{\"callback\":null},\"id\":\"9f04cf5c-8141-49f5-8fc5-6f07e2eb28bb\",\"type\":\"DataRange1d\"},{\"attributes\":{\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"9343c7bd-2075-4933-909c-b1566aad49e7\",\"type\":\"WheelZoomTool\"},{\"attributes\":{\"overlay\":{\"id\":\"13db7ccb-1b57-4994-8918-c86c60f6b949\",\"type\":\"BoxAnnotation\"},\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"722f1607-f7e4-41ca-ad2d-e69a92379ac6\",\"type\":\"BoxZoomTool\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":{\"__ndarray__\":\"FlW1u7FrAkCR43N7QvcHQK8brLfSSw9AFlW1u7FrEkBTnJQbejEVQGK4sDnC2xhAoP+PmYqhG0DeRm/5UmceQA==\",\"dtype\":\"float64\",\"shape\":[8]},\"y\":{\"__ndarray__\":\"AAAAAAAAEEAAAAAAAAAUQAAAAAAAACBAAAAAAAAAJEAAAAAAAAAoQAAAAAAAAC5AAAAAAAAAMkAAAAAAAAA1QA==\",\"dtype\":\"float64\",\"shape\":[8]}}},\"id\":\"6b8e273f-4905-4e68-a45d-4ccc26cf9755\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":[0,10],\"y\":[{\"__ndarray__\":\"dH+q7LefEcA=\",\"dtype\":\"float64\",\"shape\":[1]},{\"__ndarray__\":\"NfYmfX7JO0A=\",\"dtype\":\"float64\",\"shape\":[1]}]}},\"id\":\"a27b1a51-04c6-411a-af63-b1944951cfbc\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"7e6a4326-50f8-4eec-ba90-5811a638cff7\",\"type\":\"HelpTool\"},{\"attributes\":{\"data_source\":{\"id\":\"715301a3-e371-4dee-a08d-5a2e60941da2\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"536d5e34-3603-4d36-a987-0afac7389ecb\",\"type\":\"Line\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"fbcc7d6f-5e57-498e-8657-88b41bcd5e15\",\"type\":\"Line\"},\"selection_glyph\":null},\"id\":\"5b1bdb7c-fe7a-4b37-b5d2-4c058643648b\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"line_color\":{\"value\":\"red\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"64962fab-4a30-4244-a911-e53c1f6af126\",\"type\":\"Line\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":{\"__ndarray__\":\"FlW1u7FrAkCR43N7QvcHQK8brLfSSw9AFlW1u7FrEkBTnJQbejEVQGK4sDnC2xhAoP+PmYqhG0DeRm/5UmceQA==\",\"dtype\":\"float64\",\"shape\":[8]},\"y\":{\"__ndarray__\":\"AAAAAAAAIkAAAAAAAAAqQAAAAAAAADNAAAAAAAAANkAAAAAAAAA5QAAAAAAAADxAAAAAAAAAPkAAAAAAAIBAQA==\",\"dtype\":\"float64\",\"shape\":[8]}}},\"id\":\"411b85da-0a39-402d-b60c-90ac3febff8a\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"fill_alpha\":{\"value\":0.1},\"fill_color\":{\"value\":\"#1f77b4\"},\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"74b3a0d7-c957-413f-87f2-4be1b77e0211\",\"type\":\"Circle\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":[0,10],\"y\":[{\"__ndarray__\":\"YL25CnwxCcA=\",\"dtype\":\"float64\",\"shape\":[1]},{\"__ndarray__\":\"4OdQUK6LQEA=\",\"dtype\":\"float64\",\"shape\":[1]}]}},\"id\":\"715301a3-e371-4dee-a08d-5a2e60941da2\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"data_source\":{\"id\":\"411b85da-0a39-402d-b60c-90ac3febff8a\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"05483895-514e-49b8-b816-b3391e64afd6\",\"type\":\"Circle\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"d1722c43-06cc-47fb-bac1-1c9967af3f66\",\"type\":\"Circle\"},\"selection_glyph\":null},\"id\":\"0f0d1135-e5bc-4629-9bdf-2992df46b0f5\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"data_source\":{\"id\":\"6b8e273f-4905-4e68-a45d-4ccc26cf9755\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"d98add0b-3a0a-4d60-ad02-acf0f48373cf\",\"type\":\"Circle\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"74b3a0d7-c957-413f-87f2-4be1b77e0211\",\"type\":\"Circle\"},\"selection_glyph\":null},\"id\":\"f2989b80-c95f-4d7b-aeae-0974b5cd012d\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"line_color\":{\"value\":\"green\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"536d5e34-3603-4d36-a987-0afac7389ecb\",\"type\":\"Line\"},{\"attributes\":{\"fill_alpha\":{\"value\":0.1},\"fill_color\":{\"value\":\"#1f77b4\"},\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"d1722c43-06cc-47fb-bac1-1c9967af3f66\",\"type\":\"Circle\"},{\"attributes\":{\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"c63110dd-6744-4f98-9494-2b9e3ba03af5\",\"type\":\"Line\"},{\"attributes\":{\"data_source\":{\"id\":\"a27b1a51-04c6-411a-af63-b1944951cfbc\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"64962fab-4a30-4244-a911-e53c1f6af126\",\"type\":\"Line\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"c63110dd-6744-4f98-9494-2b9e3ba03af5\",\"type\":\"Line\"},\"selection_glyph\":null},\"id\":\"30d4a1d7-fb70-4c20-91eb-0ed792c6a43a\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"below\":[{\"id\":\"0c213af4-6c4c-4105-9f01-7cac7cb0d647\",\"type\":\"LinearAxis\"}],\"left\":[{\"id\":\"60236900-3ba0-4941-91d1-f24d3c370733\",\"type\":\"LinearAxis\"}],\"renderers\":[{\"id\":\"0c213af4-6c4c-4105-9f01-7cac7cb0d647\",\"type\":\"LinearAxis\"},{\"id\":\"e1abf2f1-7c75-4f8f-a606-b949f712f551\",\"type\":\"Grid\"},{\"id\":\"60236900-3ba0-4941-91d1-f24d3c370733\",\"type\":\"LinearAxis\"},{\"id\":\"6e64d836-4eaf-4280-834d-1b0f0502b3ea\",\"type\":\"Grid\"},{\"id\":\"13db7ccb-1b57-4994-8918-c86c60f6b949\",\"type\":\"BoxAnnotation\"},{\"id\":\"a0c2e1d8-f1ea-4dda-9ee7-97e2f4e622d7\",\"type\":\"GlyphRenderer\"},{\"id\":\"f2989b80-c95f-4d7b-aeae-0974b5cd012d\",\"type\":\"GlyphRenderer\"},{\"id\":\"0f0d1135-e5bc-4629-9bdf-2992df46b0f5\",\"type\":\"GlyphRenderer\"},{\"id\":\"5b1bdb7c-fe7a-4b37-b5d2-4c058643648b\",\"type\":\"GlyphRenderer\"},{\"id\":\"30d4a1d7-fb70-4c20-91eb-0ed792c6a43a\",\"type\":\"GlyphRenderer\"},{\"id\":\"37483b42-2fcf-40d9-aec1-6b639f571778\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"a4aa3b4a-e187-4856-8938-e8c1d7b68b9e\",\"type\":\"Title\"},\"tool_events\":{\"id\":\"86b78dca-e6fc-4220-aafa-69e628a4be8f\",\"type\":\"ToolEvents\"},\"toolbar\":{\"id\":\"0d69a7c4-8c6c-4328-ab3a-3c7778acd47f\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"9f04cf5c-8141-49f5-8fc5-6f07e2eb28bb\",\"type\":\"DataRange1d\"},\"y_range\":{\"id\":\"f27510f8-2b0a-4cb6-aed7-42265c7e6a99\",\"type\":\"DataRange1d\"}},\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"671ee947-f817-4efb-b3cf-b5b37133e408\",\"type\":\"Line\"},{\"attributes\":{\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"fbcc7d6f-5e57-498e-8657-88b41bcd5e15\",\"type\":\"Line\"},{\"attributes\":{\"fill_color\":{\"value\":\"#1f77b4\"},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"05483895-514e-49b8-b816-b3391e64afd6\",\"type\":\"Circle\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":[0,10],\"y\":[{\"__ndarray__\":\"wJrZS6Fy2j8=\",\"dtype\":\"float64\",\"shape\":[1]},{\"__ndarray__\":\"xvzBbBhCRkA=\",\"dtype\":\"float64\",\"shape\":[1]}]}},\"id\":\"1a8dd858-475b-4ef0-a6da-dc3aa30a7822\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"line_color\":{\"value\":\"red\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"de10ee00-114a-4356-b1f5-f7a429218e57\",\"type\":\"Line\"},{\"attributes\":{\"bottom_units\":\"screen\",\"fill_alpha\":{\"value\":0.5},\"fill_color\":{\"value\":\"lightgrey\"},\"left_units\":\"screen\",\"level\":\"overlay\",\"line_alpha\":{\"value\":1.0},\"line_color\":{\"value\":\"black\"},\"line_dash\":[4,4],\"line_width\":{\"value\":2},\"plot\":null,\"render_mode\":\"css\",\"right_units\":\"screen\",\"top_units\":\"screen\"},\"id\":\"13db7ccb-1b57-4994-8918-c86c60f6b949\",\"type\":\"BoxAnnotation\"},{\"attributes\":{},\"id\":\"86b78dca-e6fc-4220-aafa-69e628a4be8f\",\"type\":\"ToolEvents\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":{\"__ndarray__\":\"FlW1u7FrAkCR43N7QvcHQK8brLfSSw9AFlW1u7FrEkBTnJQbejEVQGK4sDnC2xhAoP+PmYqhG0DeRm/5UmceQA==\",\"dtype\":\"float64\",\"shape\":[8]},\"y\":{\"__ndarray__\":\"BoGVQ4tsFkAdWmQ7388eQB+F61G4niVAUI2XbhKDKkDJdr6fGq8vQHE9CtejUDNAexSuR+H6NUDRItv5fqo4QA==\",\"dtype\":\"float64\",\"shape\":[8]}}},\"id\":\"db5c6b6a-62ff-4400-a708-76e0f2c33492\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"629e37e1-be5b-452a-a2de-37c0a114b7d7\",\"type\":\"SaveTool\"},{\"attributes\":{\"dimension\":1,\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"b2f126ec-2478-4a00-85f3-82e7d46499a0\",\"type\":\"BasicTicker\"}},\"id\":\"6e64d836-4eaf-4280-834d-1b0f0502b3ea\",\"type\":\"Grid\"},{\"attributes\":{\"formatter\":{\"id\":\"0f6c61f8-9264-4a64-abde-e1220cc635f4\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"c5581975-3da0-43e1-b508-093dd97e1519\",\"type\":\"BasicTicker\"}},\"id\":\"0c213af4-6c4c-4105-9f01-7cac7cb0d647\",\"type\":\"LinearAxis\"},{\"attributes\":{\"formatter\":{\"id\":\"69d31097-18b2-4c0d-8f52-92599b9cb9ba\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"b2f126ec-2478-4a00-85f3-82e7d46499a0\",\"type\":\"BasicTicker\"}},\"id\":\"60236900-3ba0-4941-91d1-f24d3c370733\",\"type\":\"LinearAxis\"},{\"attributes\":{\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"510ed80b-b612-4eb8-936d-3f99725472ee\",\"type\":\"PanTool\"},{\"attributes\":{},\"id\":\"b2f126ec-2478-4a00-85f3-82e7d46499a0\",\"type\":\"BasicTicker\"},{\"attributes\":{\"callback\":null},\"id\":\"f27510f8-2b0a-4cb6-aed7-42265c7e6a99\",\"type\":\"DataRange1d\"},{\"attributes\":{\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"c5581975-3da0-43e1-b508-093dd97e1519\",\"type\":\"BasicTicker\"}},\"id\":\"e1abf2f1-7c75-4f8f-a606-b949f712f551\",\"type\":\"Grid\"},{\"attributes\":{},\"id\":\"0f6c61f8-9264-4a64-abde-e1220cc635f4\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"fill_color\":{\"value\":\"#1f77b4\"},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"a18b7326-b64c-4225-b0e9-b09302313c30\",\"type\":\"Circle\"},{\"attributes\":{\"fill_color\":{\"value\":\"#1f77b4\"},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"d98add0b-3a0a-4d60-ad02-acf0f48373cf\",\"type\":\"Circle\"},{\"attributes\":{},\"id\":\"c5581975-3da0-43e1-b508-093dd97e1519\",\"type\":\"BasicTicker\"},{\"attributes\":{\"fill_alpha\":{\"value\":0.1},\"fill_color\":{\"value\":\"#1f77b4\"},\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"7b1e2bb0-c837-4357-9c32-9076899d36bf\",\"type\":\"Circle\"},{\"attributes\":{\"plot\":{\"id\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"09770ccf-cd8d-421a-a044-1b7865ee98f4\",\"type\":\"ResetTool\"},{\"attributes\":{\"active_drag\":\"auto\",\"active_scroll\":\"auto\",\"active_tap\":\"auto\",\"tools\":[{\"id\":\"510ed80b-b612-4eb8-936d-3f99725472ee\",\"type\":\"PanTool\"},{\"id\":\"9343c7bd-2075-4933-909c-b1566aad49e7\",\"type\":\"WheelZoomTool\"},{\"id\":\"722f1607-f7e4-41ca-ad2d-e69a92379ac6\",\"type\":\"BoxZoomTool\"},{\"id\":\"629e37e1-be5b-452a-a2de-37c0a114b7d7\",\"type\":\"SaveTool\"},{\"id\":\"09770ccf-cd8d-421a-a044-1b7865ee98f4\",\"type\":\"ResetTool\"},{\"id\":\"7e6a4326-50f8-4eec-ba90-5811a638cff7\",\"type\":\"HelpTool\"}]},\"id\":\"0d69a7c4-8c6c-4328-ab3a-3c7778acd47f\",\"type\":\"Toolbar\"},{\"attributes\":{\"data_source\":{\"id\":\"1a8dd858-475b-4ef0-a6da-dc3aa30a7822\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"de10ee00-114a-4356-b1f5-f7a429218e57\",\"type\":\"Line\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"671ee947-f817-4efb-b3cf-b5b37133e408\",\"type\":\"Line\"},\"selection_glyph\":null},\"id\":\"37483b42-2fcf-40d9-aec1-6b639f571778\",\"type\":\"GlyphRenderer\"}],\"root_ids\":[\"90d89ffb-a5aa-425a-bc51-f425f56977a3\"]},\"title\":\"Bokeh Application\",\"version\":\"0.12.4\"}};\n",
       "            var render_items = [{\"docid\":\"1a125c96-f484-4c83-8080-40101816f7c1\",\"elementid\":\"ad46a499-4596-4a9c-9119-a493a44f32de\",\"modelid\":\"90d89ffb-a5aa-425a-bc51-f425f56977a3\"}];\n",
       "            \n",
       "            Bokeh.embed.embed_items(docs_json, render_items);\n",
       "          };\n",
       "          if (document.readyState != \"loading\") fn();\n",
       "          else document.addEventListener(\"DOMContentLoaded\", fn);\n",
       "        })();\n",
       "      },\n",
       "      function(Bokeh) {\n",
       "      }\n",
       "    ];\n",
       "  \n",
       "    function run_inline_js() {\n",
       "      \n",
       "      if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "        for (var i = 0; i < inline_js.length; i++) {\n",
       "          inline_js[i](window.Bokeh);\n",
       "        }if (force === true) {\n",
       "          display_loaded();\n",
       "        }} else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(run_inline_js, 100);\n",
       "      } else if (!window._bokeh_failed_load) {\n",
       "        console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "        window._bokeh_failed_load = true;\n",
       "      } else if (force !== true) {\n",
       "        var cell = $(document.getElementById(\"ad46a499-4596-4a9c-9119-a493a44f32de\")).parents('.cell').data().cell;\n",
       "        cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "      }\n",
       "  \n",
       "    }\n",
       "  \n",
       "    if (window._bokeh_is_loading === 0) {\n",
       "      console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "      run_inline_js();\n",
       "    } else {\n",
       "      load_libs(js_urls, function() {\n",
       "        console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "        run_inline_js();\n",
       "      });\n",
       "    }\n",
       "  }(this));\n",
       "</script>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "output_notebook()\n",
    "\n",
    "plot = figure()\n",
    "\n",
    "plot.scatter(x.ravel(), y[:, 0])\n",
    "plot.scatter(x.ravel(), y[:, 1])\n",
    "plot.scatter(x.ravel(), y[:, 2])\n",
    "\n",
    "plot.line([0, 10], [model_mean.predict(0), model_mean.predict(10)], color='green')\n",
    "plot.line([0, 10], [model_min.predict(0), model_min.predict(10)], color='red')\n",
    "plot.line([0, 10], [model_max.predict(0), model_max.predict(10)], color='red')\n",
    "\n",
    "show(plot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}