python/getting-the-top-k-sorted-elements-from-a-generator.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Getting the top K sorted elements\n",
    "## Time and space complexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext memory_profiler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generator of this size\n",
    "n = 20000000\n",
    "k = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_it():\n",
    "    return (-a for a in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.24 s, sys: 267 ms, total: 2.5 s\n",
      "Wall time: 2.5 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[-9999999,\n",
       " -9999998,\n",
       " -9999997,\n",
       " -9999996,\n",
       " -9999995,\n",
       " -9999994,\n",
       " -9999993,\n",
       " -9999992,\n",
       " -9999991,\n",
       " -9999990]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "sorted(get_it(), key=lambda x: x)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "peak memory: 964.60 MiB, increment: 846.59 MiB\n"
     ]
    }
   ],
   "source": [
    "%%memit\n",
    "sorted(get_it(), key=lambda x: x)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4.97 s, sys: 23.4 ms, total: 4.99 s\n",
      "Wall time: 5.01 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[-9999999,\n",
       " -9999998,\n",
       " -9999997,\n",
       " -9999996,\n",
       " -9999995,\n",
       " -9999994,\n",
       " -9999993,\n",
       " -9999992,\n",
       " -9999991,\n",
       " -9999990]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "heapq.nsmallest(k, get_it())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "peak memory: 118.01 MiB, increment: 0.00 MiB\n"
     ]
    }
   ],
   "source": [
    "%%memit\n",
    "heapq.nsmallest(k, get_it())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sorting tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_it_tuple():\n",
    "    return ((a, -a) for a in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 8.32 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "sorted(get_it_tuple(), key=lambda x: x[1])[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "peak memory: 2927.98 MiB, increment: 2884.93 MiB\n"
     ]
    }
   ],
   "source": [
    "%%memit\n",
    "sorted(get_it_tuple(), key=lambda x: x[1])[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 13.3 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "heapq.nsmallest(k, get_it_tuple(), key=lambda x: x[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "peak memory: 42.05 MiB, increment: 0.00 MiB\n"
     ]
    }
   ],
   "source": [
    "%%memit\n",
    "heapq.nsmallest(k, get_it_tuple(), key=lambda x: x[1])"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}