<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This short post details an easy way to speed up array comparison. My problem was that I had to compare two 3D arrays, A and B, These arrays are different only in their first dimension, and have equal $2^{nd}$ and $3^{rd}$ dimensions. I needed to find out whether any of the 2D arrays contained along the first dimension of, say, A were also present along the first dimension of B. The first approach one might try is based on nested for-loops. This becomes quickly unwieldy with even moderate-sized arrays. The faster alternative is to hash the 2D data in one of the arrays and store the hash table; I prefer to do that with the smaller array for space use efficiency. The next step is to go along the first dimension of the other array, hash the data and compare. This ends up requiring only serial for-loops. Note here that the Python version is 3.6, which implements numpy ndarray hashing differently than 2.x. Note also the use of [f-strings; a nifty new feature of python 3.6.](https://cito.github.io/blog/f-strings/)\n",
    "<!--TEASER-->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Python: 3.6.2 \n",
      "Numpy: 1.13.1\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "import numpy as np\n",
    "import time\n",
    "print(f\"Python: {sys.version.rsplit('|')[0]}\")\n",
    "print(f\"Numpy: {np.__version__}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First create the arrays..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = np.random.randint(0, 10, size=270).reshape((30, 3, 3))\n",
    "B = np.random.randint(0, 10, size=450000).reshape((50000, 3, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then spread the 2D arrays in A along B's first dimension..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "dupIdx = np.random.choice(B.shape[0], size=A.shape[0], replace=False)\n",
    "B[dupIdx] = A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next is to implement, execute, and time the nested for-loops one would need to compare both arrays:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "duplicates: 30 -- time taken: 5.183124\n"
     ]
    }
   ],
   "source": [
    "start = time.clock()\n",
    "count = 0\n",
    "for bi in B:\n",
    "    for ai in A:\n",
    "        if np.array_equal(ai, bi):\n",
    "            count += 1\n",
    "tot1 = time.clock() - start\n",
    "print(f\"duplicates: {count} -- time taken: {tot1}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's pretty long for such small arrays. Now to implement, execute, and time the hasing-based approach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "duplicates: 30 -- time taken: 0.06364500000000017\n"
     ]
    }
   ],
   "source": [
    "start = time.clock()\n",
    "hshTbl = {}\n",
    "count = 0\n",
    "for idx, ai in enumerate(A):\n",
    "    hsh = hash(bytes(ai))\n",
    "    hshTbl[hsh] = idx\n",
    "for bi in B:\n",
    "    hsh = hash(bytes(bi))\n",
    "    if hsh in hshTbl and np.array_equal(A[hshTbl[hsh]], bi):\n",
    "        count += 1\n",
    "tot2 = time.clock() - start\n",
    "print(f\"duplicates: {count} -- time taken: {tot2}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.012279274043993578"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tot2 / tot1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that took about 1.2% of the time! Happy coding!"
   ]
  }
 ],
 "metadata": {
  "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"
  },
  "nikola": {
   "category": "",
   "date": "2017-09-25 10:52:36 UTC-04:00",
   "description": "",
   "link": "",
   "slug": "speeding-up-numpy-array-comparison",
   "tags": "Numpy, array hashing",
   "title": "Faster comparison of two Numpy arrays",
   "type": "text"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
<commit_msg>corrected teaser syntax<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This short post details an easy way to speed up array comparison. My problem was that I had to compare two 3D arrays, A and B, These arrays are different only in their first dimension, and have equal $2^{nd}$ and $3^{rd}$ dimensions. I needed to find out whether any of the 2D arrays contained along the first dimension of, say, A were also present along the first dimension of B. The first approach one might try is based on nested for-loops. This becomes quickly unwieldy with even moderate-sized arrays. The faster alternative is to hash the 2D data in one of the arrays and store the hash table; I prefer to do that with the smaller array for space use efficiency. The next step is to go along the first dimension of the other array, hash the data and compare. This ends up requiring only serial for-loops. Note here that the Python version is 3.6, which implements numpy ndarray hashing differently than 2.x. Note also the use of [f-strings; a nifty new feature of python 3.6.](https://cito.github.io/blog/f-strings/)\n",
    "<!--TEASER_END-->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Python: 3.6.2 \n",
      "Numpy: 1.13.1\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "import numpy as np\n",
    "import time\n",
    "print(f\"Python: {sys.version.rsplit('|')[0]}\")\n",
    "print(f\"Numpy: {np.__version__}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First create the arrays..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = np.random.randint(0, 10, size=270).reshape((30, 3, 3))\n",
    "B = np.random.randint(0, 10, size=450000).reshape((50000, 3, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then spread the 2D arrays in A along B's first dimension..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "dupIdx = np.random.choice(B.shape[0], size=A.shape[0], replace=False)\n",
    "B[dupIdx] = A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next is to implement, execute, and time the nested for-loops one would need to compare both arrays:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "duplicates: 30 -- time taken: 5.183124\n"
     ]
    }
   ],
   "source": [
    "start = time.clock()\n",
    "count = 0\n",
    "for bi in B:\n",
    "    for ai in A:\n",
    "        if np.array_equal(ai, bi):\n",
    "            count += 1\n",
    "tot1 = time.clock() - start\n",
    "print(f\"duplicates: {count} -- time taken: {tot1}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's pretty long for such small arrays. Now to implement, execute, and time the hasing-based approach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "duplicates: 30 -- time taken: 0.06364500000000017\n"
     ]
    }
   ],
   "source": [
    "start = time.clock()\n",
    "hshTbl = {}\n",
    "count = 0\n",
    "for idx, ai in enumerate(A):\n",
    "    hsh = hash(bytes(ai))\n",
    "    hshTbl[hsh] = idx\n",
    "for bi in B:\n",
    "    hsh = hash(bytes(bi))\n",
    "    if hsh in hshTbl and np.array_equal(A[hshTbl[hsh]], bi):\n",
    "        count += 1\n",
    "tot2 = time.clock() - start\n",
    "print(f\"duplicates: {count} -- time taken: {tot2}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.012279274043993578"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tot2 / tot1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that took about 1.2% of the time! Happy coding!"
   ]
  }
 ],
 "metadata": {
  "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"
  },
  "nikola": {
   "category": "",
   "date": "2017-09-25 10:52:36 UTC-04:00",
   "description": "",
   "link": "",
   "slug": "speeding-up-numpy-array-comparison",
   "tags": "Numpy, array hashing",
   "title": "Faster comparison of two Numpy arrays",
   "type": "text"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

{'fraction_non_alphanumeric': 0.18819620871604456, 'fraction_numerical': 0.027359781121751026, 'mean_word_length': 2.542748355832468, 'pattern_counts': {'":': 182, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6029925', 'n_tokens_mistral': 3958, 'n_tokens_neox': 3731, 'n_words': 990}