Prepending with List vs Deque

deque.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "from collections import deque\n",
    "\n",
    "def list_insert_0():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l.insert(0, i)\n",
    "\n",
    "def list_slice_insert():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l[:0] = [i]      # semantically same as list.insert(0, i)\n",
    "\n",
    "def list_add():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l = [i] + l      # caveat: new list each time\n",
    "\n",
    "def deque_appendleft():\n",
    "    d = deque()\n",
    "    for i in range(10000):\n",
    "        d.appendleft(i)  # semantically same as list.insert(0, i)\n",
    "\n",
    "def deque_extendleft():\n",
    "    d = deque()\n",
    "    d.extendleft(range(10000))\n",
    "    \n",
    "def deque_appendleft_back_list():\n",
    "    d = deque()\n",
    "    for i in range(10000):\n",
    "        d.appendleft(i)\n",
    "    return list(d) # Returns back a list\n",
    "\n",
    "def append_reverse():\n",
    "    l = []\n",
    "    for i in range(10000):\n",
    "        l.append(i)\n",
    "    l.reverse() # append and reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18.4 ms ± 441 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "list_insert_0()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.86 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "list_slice_insert()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "105 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "list_add()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "838 µs ± 4.72 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "deque_appendleft()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "328 µs ± 19.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "deque_extendleft()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "914 µs ± 22.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "deque_appendleft_back_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "841 µs ± 53.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "append_reverse()"
   ]
  },
  {
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}

referenced from https://stackoverflow.com/questions/8537916/whats-the-idiomatic-syntax-for-prepending-to-a-short-python-list

Small overhead of converting from deque to list but still much faster

append_reverse is almost identical to deque_appendleft