Python Standard Library.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 用Python标准库写出高效的代码\n",
    "作者: tushushu  \n",
    "项目地址: https://github.com/tushushu/flying-python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. bisect - 二分查找\n",
    "给定一个列表对象，我们要对目标元素进行查找，返回其在列表中的下标。  \n",
    "* 首先想到的是Python列表的index方法。建立一个长度为10000的升序列表，编写search函数使用index方式把里面的每一个元素查找一遍，平均运行时间437毫秒。\n",
    "* 使用bisect模块的bisect_left，也就是我们熟知的二分查找。编写fast_search函数，平均运行时间3.94毫秒，性能提升了110倍！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import bisect"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(nums):\n",
    "    for x in nums:\n",
    "        nums.index(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fast_search(nums):\n",
    "    for x in nums:\n",
    "        bisect.bisect_left(nums, x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = list(range(10000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "437 ms ± 12.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 1 search(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.94 ms ± 407 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 1 fast_search(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Counter - 高效计数\n",
    "给定一个列表对象，我们要统计其中的每个不重复的元素出现了多少次，返回一个字典对象。  \n",
    "* 创建一个长度为10000，元素为1-3之间的随机数的列表。编写count函数，创建一个空字典，用for循环遍历该列表，将计数结果写入字典。平均运行时间937微秒。\n",
    "* 使用collections模块的Counter，编写fast_count函数，一行代码搞定。平均运行时间494微秒，性能几乎是原来的2倍。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from random import randint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count(nums):\n",
    "    res = dict()\n",
    "    for x in nums:\n",
    "        if x in res:\n",
    "            res[x] += 1\n",
    "        else:\n",
    "            res[x] = 0\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fast_count(nums):\n",
    "    return Counter(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [randint(1, 3) for _ in range(10000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "937 µs ± 153 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 1 count(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "494 µs ± 240 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 1 fast_count(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. heapq - 堆\n",
    "给定一个列表对象，返回该列表中最小的3个元素。\n",
    "* 创建一个长度为10000的列表，对元素进行随机打乱。编写top_3函数，对列表进行排序，返回前3个元素。平均运行时间2.03毫秒。\n",
    "* 使用heapq模块，也就是我们熟悉的堆，编写fast_top_3函数。平均运行时间296微秒，性能提升了6.8倍。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "from random import shuffle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def top_3(nums):\n",
    "    return sorted(nums)[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fast_top_3(nums):\n",
    "    return heapq.nsmallest(3, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = list(range(10000))\n",
    "shuffle(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.03 ms ± 236 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 1 top_3(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "296 µs ± 56.2 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 1 fast_top_3(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. itemgetter - 批量get元素\n",
    "给定一个字典和一个列表，列表中包含一个或多个字典中的key，返回对应的values。\n",
    "* 创建一个元素数量为10万的字典，从字典的key中随机抽样10万，形成一个长度为1万的列表。编写get_items函数，平均运行时间1.12毫秒\n",
    "* 使用itemgetter批量读取这些元素，编写fast_get_items函数，平均运行时间836微秒，性能是原来的1.3倍。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import itemgetter\n",
    "from random import choices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_items(data, keys):\n",
    "    return [data[x] for x in keys]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fast_get_items(data, keys):\n",
    "    return itemgetter(*keys)(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "data= dict(enumerate(range(100000)))\n",
    "keys = choices(list(data.keys()), k=10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.12 ms ± 354 µs per loop (mean ± std. dev. of 7 runs, 5 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 5 get_items(data, keys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "836 µs ± 287 µs per loop (mean ± std. dev. of 7 runs, 5 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 5 fast_get_items(data, keys)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. lru_cache - 空间换时间\n",
    "给定数字n，返回长度为n的斐波那且数列\n",
    "* 使用递归方式，编写fib函数，并用fib_seq函数对其进行循环调用。令n等于20，平均运行时间3.28ms。\n",
    "* 使用@lru_cache语法糖，将已经计算出来的结果缓存起来，比如fib(4)，计算fib(5)的时候可以直接调用缓存的fib(4)。平均运行时间144微秒，性能提升了22倍。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n < 2:\n",
    "        return n\n",
    "    return fib(n-1) + fib(n-2)\n",
    "\n",
    "def fib_seq(n):\n",
    "    return [fib(x) for x in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def fast_fib(n):\n",
    "    if n < 2:\n",
    "        return n\n",
    "    return fib(n-1) + fib(n-2)\n",
    "\n",
    "def fast_fib_seq(n):\n",
    "    return [fast_fib(x) for x in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.28 ms ± 220 µs per loop (mean ± std. dev. of 7 runs, 3 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 5 fib_seq(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 524.07 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "144 µs ± 347 µs per loop (mean ± std. dev. of 7 runs, 3 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 5 fast_fib_seq(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}