08_06_Pytorch_Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2e0034b0-668b-4d8c-a8c9-75202798d875",
   "metadata": {},
   "source": [
    "# Introduction to PyTorch Sorting by way of NumPy\n",
    "\n",
    "This module explores the reasons to abandon \"roll your own\" sorting algorithms in deferences to using either NumPy or PyTorch function equivalents.\n",
    "\n",
    "We took a stab at creating a table to compare sort related functions between NumPy and PyTorch:\n",
    "\n",
    "Hannesy & Patternson:\n",
    "\"A New Golden Age for Computer Architecture\"\n",
    "https://www.doc.ic.ac.uk/~wl/teachlocal/arch/papers/cacm19golden-age.pdf\n",
    "\n",
    "\n",
    "| Function | Description | NumPy | PyTorch|\n",
    "| ---| --- | --- | --- |\n",
    "| sort | Return a sorted copy of an array. | numpy.sort select kind = ‘quicksort’, ‘mergesort’, ‘heapsort’, ‘stable’ | Cannot specify algorithm |\n",
    "| argsort | Returns the indices that would sort an array. | numpy.argsort | torch.argsort |\n",
    "| lexsort | Perform an indirect sort on multiple keys. |  numpy.lexsort | torch.argsort |\n",
    "| partition | Partially sort an array in-place. | numpy.partition | torch.partition |\n",
    "| argpartition | Returns the indices that would partition an array. | numpy.argpartition | torch.topk |\n",
    "| msort | Merge sort an array.  |  numpy.msort | N/A |\n",
    "| sort_complex | Sort a complex array using the real part first. | numpy.sort_complex | N/A |\n",
    "| searchsorted | Find indices where elements should be inserted to maintain order. |  numpy.searchsorted | N/A |\n",
    "\n",
    "Here is a recent news story about Intel accelerating NumPy quicksort:\n",
    "\n",
    "**Intel Publishes Blazing Fast AVX-512 Sorting Library, Numpy Switching To It For 10~17x Faster Sorts**\n",
    "- https://www.phoronix.com/news/Intel-AVX-512-Quicksort-Numpy\n",
    "- Written by Michael Larabel in Intel on 15 February 2023 at 04:00 PM EST. 51 Comments\n",
    "\n",
    "\n",
    "We will only be investiagating sort in this module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae5e937f-2e0e-413c-ad26-8d04210f2f5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import torch\n",
    "import time\n",
    "BIG = 10_000_000\n",
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "orig = arr.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34dbff91-9b15-41f7-a74f-94777af61c86",
   "metadata": {},
   "outputs": [],
   "source": [
    "def heapify(arr, n, i):\n",
    "    largest = i \n",
    "    l = 2 * i + 1 \n",
    "    r = 2 * i + 2 \n",
    " \n",
    "    if l < n and arr[largest] < arr[l]:\n",
    "        largest = l\n",
    " \n",
    "    if r < n and arr[largest] < arr[r]:\n",
    "        largest = r\n",
    " \n",
    "    if largest != i:\n",
    "        arr[i],arr[largest] = arr[largest],arr[i]  \n",
    "        heapify(arr, n, largest)\n",
    "    return\n",
    "\n",
    "def heapSort(arr):\n",
    "    n = len(arr)\n",
    " \n",
    "    for i in range(n // 2 - 1, -1, -1):\n",
    "        heapify(arr, n, i)\n",
    " \n",
    "    for i in range(n-1, 0, -1):\n",
    "        arr[i], arr[0] = arr[0], arr[i] \n",
    "        heapify(arr, i, 0)\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f222785-06ba-42fb-b3e1-75fdc23c8fa6",
   "metadata": {},
   "source": [
    "# Heapsort\n",
    "\n",
    "### The loopy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e6fae24-e8c9-4a8e-96f0-018aa50ef9fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "timing = {}\n",
    "t1 = time.time()\n",
    "heapSort(arr)\n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "print(arr[:10] )\n",
    "timing['heapsort_bruteForce'] = time.time() - t1\n",
    "print('Elapsed time', timing['heapsort_bruteForce'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2525893e-31b4-436f-99fe-2ec8ee5beb95",
   "metadata": {},
   "source": [
    "### The NumPy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f529fb51-a150-4b36-af1b-fdc2b495f888",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "t1 = time.time()\n",
    "np.sort(arr, axis=None, kind='heapsort') \n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "print(arr[:10] )\n",
    "timing['heapsort_numpy'] = time.time() - t1\n",
    "print('Elapsed time', timing['heapsort_numpy'])\n",
    "print('Numpy Acceleration: {:4.1f} X faster'.format(timing['heapsort_bruteForce']/timing['heapsort_numpy']))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afd4d5aa-d8c2-4d34-9229-654b0498bc4f",
   "metadata": {},
   "source": [
    "### The PyTorch way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f41c4eb-c0c4-4318-85e6-7eab53809d8c",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "arr = torch.tensor(arr)\n",
    "t1 = time.time()\n",
    "torch.sort(arr) \n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "print(arr[:10] )\n",
    "timing['heapsort_pytorch'] = time.time() - t1\n",
    "print('Elapsed time', timing['heapsort_pytorch'])\n",
    "print('Numpy Acceleration: {:4.1f} X faster'.format(timing['heapsort_bruteForce']/timing['heapsort_pytorch']))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c0cccd1-8532-455c-908f-c0de7dbc2430",
   "metadata": {},
   "source": [
    "### Plot the times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2be82f0a-e664-4393-a802-f28cd3bc8d4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.figure(figsize=(10,6))\n",
    "plt.title(\"Measure acceleration of looping versus PyTorch/NumPy [Lower is better]\",fontsize=12)\n",
    "plt.ylabel(\"Time in seconds\",fontsize=12)\n",
    "plt.yscale('log')\n",
    "plt.xlabel(\"Various types of operations\",fontsize=14)\n",
    "plt.grid(True)\n",
    "plt.bar(x = list(timing.keys()), height= list(timing.values()), align='center',tick_label=list(timing.keys()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4a92e63-d28c-4e92-98c9-d19b7b1e70d5",
   "metadata": {},
   "source": [
    "# Quicksort\n",
    "\n",
    "### The loopy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a43bb20a-7f3e-45fe-8f31-1bc59e8bdca1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def quickSort(arr, low, high):\n",
    "    if low < high:\n",
    "        pivotIndex = partition(arr, low, high)\n",
    "        quickSort(arr, low, pivotIndex - 1)\n",
    "        quickSort(arr, pivotIndex + 1, high)\n",
    "\n",
    "def partition(arr, low, high):\n",
    "    pivot = arr[high]\n",
    "    i = low - 1  # Index of smaller element\n",
    "    for j in range(low, high):\n",
    "        # If current element is smaller than or equal to pivot\n",
    "        if arr[j] <= pivot:\n",
    "            i += 1\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "    arr[i+1], arr[high] = arr[high], arr[i+1]\n",
    "    return i + 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f44c1a6e-8770-44e1-9a05-08d216e75f39",
   "metadata": {},
   "source": [
    "### The Loopy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "54be80bc-36d7-472a-b59f-31343465ae02",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "timing = {}\n",
    "t1 = time.time()\n",
    "quickSort(arr, 0, len(arr)-1)\n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "timing['quicksort_bruteForce'] = time.time() - t1\n",
    "print('Elapsed time', timing['quicksort_bruteForce'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ec9a126-b0db-4a92-9a4d-1c169b4d158a",
   "metadata": {},
   "source": [
    "### The NumPy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7179a7ef-cb42-4064-bfd8-05756e56959f",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "t1 = time.time()\n",
    "np.sort(arr, axis=None, kind='quicksort') \n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "timing['quicksort_numpy'] = time.time() - t1\n",
    "print('Elapsed time', timing['quicksort_numpy'])\n",
    "print('Numpy Acceleration: {:4.1f} X faster'.format(timing['quicksort_bruteForce']/timing['quicksort_numpy']))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a690d426-87a2-434e-9a5c-a9bf12eb1a07",
   "metadata": {},
   "source": [
    "### The PyTorch way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41bc5784-5b40-48f1-b604-dccd84546051",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "arr = torch.tensor(arr)\n",
    "t1 = time.time()\n",
    "torch.sort(arr) \n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "print(arr[:10] )\n",
    "timing['sort_pytorch'] = time.time() - t1\n",
    "print('Elapsed time', timing['sort_pytorch'])\n",
    "print('Numpy Acceleration: {:4.1f} X faster'.format(timing['quicksort_bruteForce']/timing['sort_pytorch']))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "014690d1-39b9-42ee-9f20-99a4780c9bee",
   "metadata": {},
   "source": [
    "### Plot the times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "402ded87-4f41-442d-bb5c-c586a359a50e",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.figure(figsize=(10,6))\n",
    "plt.title(\"Measure acceleration of looping versus PyTorch/NumPy [Lower is better]\",fontsize=12)\n",
    "plt.ylabel(\"Time in seconds\",fontsize=12)\n",
    "plt.yscale('log')\n",
    "plt.xlabel(\"Various types of operations\",fontsize=14)\n",
    "plt.grid(True)\n",
    "plt.bar(x = list(timing.keys()), height= list(timing.values()), align='center',tick_label=list(timing.keys()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73b3ad9a-50dd-4aa1-908a-ebb083cd84d8",
   "metadata": {},
   "source": [
    "# Mergesort\n",
    "\n",
    "### The Loopy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59ce64dd-770f-4853-87f7-e69844870eb7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSort(arr):\n",
    "    if len(arr) > 1:\n",
    "        mid = len(arr) // 2\n",
    "        leftHalf = arr[:mid]\n",
    "        rightHalf = arr[mid:]\n",
    "        \n",
    "        mergeSort(leftHalf)\n",
    "        mergeSort(rightHalf)\n",
    "        \n",
    "        i = j = k = 0\n",
    "        \n",
    "        while i < len(leftHalf) and j < len(rightHalf):\n",
    "            if leftHalf[i] < rightHalf[j]:\n",
    "                arr[k] = leftHalf[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                arr[k] = rightHalf[j]\n",
    "                j += 1\n",
    "            k += 1\n",
    "        \n",
    "        while i < len(leftHalf):\n",
    "            arr[k] = leftHalf[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "        \n",
    "        while j < len(rightHalf):\n",
    "            arr[k] = rightHalf[j]\n",
    "            j += 1\n",
    "            k += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "393b20da-491d-42d3-bba0-cbc13d4d8db0",
   "metadata": {},
   "source": [
    "### The Loopy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3b0a50d-a3f1-4ea9-a80e-ed6bdf1d3669",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "timing = {}\n",
    "t1 = time.time()\n",
    "mergeSort(arr)\n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "timing['mergesort_bruteForce'] = time.time() - t1\n",
    "print('Elapsed time', timing['mergesort_bruteForce'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "679d425a-ac4a-4838-a55d-1bd85c51d0bd",
   "metadata": {},
   "source": [
    "### The NumPy way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c8563ba-5565-4c7f-ba03-18f21c8f6d36",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "t1 = time.time()\n",
    "np.sort(arr, axis=None, kind='mergesort') \n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "timing['mergesort_numpy'] = time.time() - t1\n",
    "print('Elapsed time', timing['mergesort_numpy'])\n",
    "print('Numpy Acceleration: {:4.1f} X faster'.format(timing['mergesort_bruteForce']/timing['mergesort_numpy']))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07017490-2086-479a-8757-95dbb703af7a",
   "metadata": {},
   "source": [
    "### The PyTorch way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a8cf1045-1953-4689-b155-d9b62abbfdfe",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(seed=12)\n",
    "arr = np.random.rand(BIG)\n",
    "arr = torch.tensor(arr)\n",
    "t1 = time.time()\n",
    "torch.sort(arr) \n",
    "t2 = time.time()\n",
    "print(\"Sorted array is:\")\n",
    "print(arr[:10] )\n",
    "timing['sort_pytorch'] = time.time() - t1\n",
    "print('Elapsed time', timing['sort_pytorch'])\n",
    "print('Numpy Acceleration: {:4.1f} X faster'.format(timing['mergesort_bruteForce']/timing['sort_pytorch']))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3943b0e-879b-4ce8-98eb-38e007c62106",
   "metadata": {},
   "source": [
    "### Plot the times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5dd7a242-6627-4d77-8da7-8c2d749d4e64",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.figure(figsize=(10,6))\n",
    "plt.title(\"Measure acceleration of looping versus PyTorch/NumPy [Lower is better]\",fontsize=12)\n",
    "plt.ylabel(\"Time in seconds\",fontsize=12)\n",
    "plt.yscale('log')\n",
    "\n",
    "plt.xlabel(\"Various types of operations\",fontsize=14)\n",
    "plt.grid(True)\n",
    "plt.bar(x = list(timing.keys()), height= list(timing.values()), align='center',tick_label=list(timing.keys()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6241907-d82c-46ba-9a0b-861459d96eb4",
   "metadata": {},
   "source": [
    "# Notices and Disclaimers\n",
    "\n",
    "Intel technologies may require enabled hardware, software or service activation.\n",
    "No product or component can be absolutely secure. \n",
    "\n",
    "Your costs and results may vary. \n",
    "\n",
    "© Intel Corporation. Intel, the Intel logo, and other Intel marks are trademarks of Intel Corporation or its subsidiaries. Other names and brands may be claimed as the property of others. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "PyTorch (AI kit)",
   "language": "python",
   "name": "c009-intel_distribution_of_python_3_oneapi-beta05-pytorch"
  },
  "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.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}