testin-anagram-generators.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1: verify correctness, or at least that the two generators yield identical results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "\n",
    "from pagan_army.anagram_handler import AnagramHandler\n",
    "from pagan_army.hash_anagram_generator import HashAnagramGenerator\n",
    "from pagan_army.unsorted_trie_anagram_generator import UnsortedTrieAnagramGenerator\n",
    "\n",
    "\n",
    "TestDeets = namedtuple('TestDeets', ['word_length', 'anagramee', 'expected_count'])\n",
    "\n",
    "tests = [ \n",
    "    TestDeets(word_length=2, anagramee='my game', expected_count=7),\n",
    "    TestDeets(word_length=2, anagramee='is like the', expected_count=81),\n",
    "    TestDeets(word_length=6, anagramee='pythagorean theorem', expected_count=54),\n",
    "    TestDeets(word_length=5, anagramee='there is no answer', expected_count=1177)\n",
    "]\n",
    "\n",
    "\n",
    "for test_deets in tests:\n",
    "    hash_gen = HashAnagramGenerator(minimum_word_length=test_deets.word_length)\n",
    "    hash_handler = AnagramHandler(test_deets.anagramee, anagram_generator=hash_gen)\n",
    "    all_from_hash = list(hash_handler)\n",
    "    \n",
    "    trie_gen = UnsortedTrieAnagramGenerator(minimum_word_length=test_deets.word_length)\n",
    "    trie_handler = AnagramHandler(test_deets.anagramee, anagram_generator=trie_gen)\n",
    "    all_from_trie = list(trie_handler)\n",
    "\n",
    "    assert len(all_from_hash) == len(all_from_trie) == test_deets.expected_count\n",
    "    assert sorted(all_from_hash) == sorted(all_from_trie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2: simple performance test in a realword-ish scenario to compare hash_anagram_generator and unsorted_trie_anagram_generator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST RESULTS\n",
      "------------\n",
      "anagramming 'alex gessner' 30 times...\n",
      "for 5 iterations of 25 executions\n",
      "the hash anagram generator times: [3.206, 3.182, 3.154, 3.182, 3.224]\n",
      "the trie anagram generator times: [37.018, 37.001, 36.801, 37.343, 36.843]\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "\n",
    "iterations = 5\n",
    "executions = 25\n",
    "anagramee = 'alex gessner'\n",
    "word_length = 3\n",
    "number_of_grams = 30\n",
    "\n",
    "\n",
    "global_shared_setup = '''\n",
    "import timeit\n",
    "from pagan_army.anagram_handler import AnagramHandler\n",
    "from pagan_army.hash_anagram_generator import HashAnagramGenerator\n",
    "from pagan_army.unsorted_trie_anagram_generator import UnsortedTrieAnagramGenerator\n",
    "'''\n",
    "\n",
    "easy_test_setup = '''\n",
    "ANAGRAMEE = '{anagramee}'\n",
    "WORD_LENGTH = {word_length}\n",
    "'''.format(anagramee=anagramee, word_length=word_length)\n",
    "\n",
    "hashed_setup = '''\n",
    "GENERATOR = HashAnagramGenerator()\n",
    "'''\n",
    "trie_setup = '''\n",
    "GENERATOR = UnsortedTrieAnagramGenerator()\n",
    "'''\n",
    "run_it = '''\n",
    "handler = AnagramHandler(ANAGRAMEE, anagram_generator=GENERATOR, minimum_word_length=WORD_LENGTH)\n",
    "handler.get_n({})\n",
    "'''.format(number_of_grams)\n",
    "\n",
    "print('TEST RESULTS\\n------------')\n",
    "print(\"anagramming '{anagramee}' {count} times...\".format(anagramee=anagramee, count=number_of_grams))\n",
    "print(\"for {} iterations of {} executions\".format(iterations, executions))\n",
    "hashed_times = timeit.Timer(hashed_setup + run_it, setup=global_shared_setup + easy_test_setup).repeat(iterations, executions)\n",
    "hashed_times = [round(time, 3) for time in hashed_times]\n",
    "print(\"the hash anagram generator times:\", hashed_times)\n",
    "trie_times = timeit.Timer(trie_setup + run_it, setup=global_shared_setup + easy_test_setup).repeat(iterations, executions)\n",
    "trie_times = [round(time, 3) for time in trie_times]\n",
    "print(\"the trie anagram generator times:\", trie_times)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Thoughts\n",
    "## tl;dr the hash_anagram_generator is an order of magnitude faster than an unsorted trie.\n",
    "### wowza. so i'm not so surprised that the dictionary was faster than the unsorted trie. there's so much i could do to optimize the trie. the biggest one i'm thinking right now is sorting the letters by order of frequency in the overall list of words and then having the leaves be a list of all words with those letters. maybe i'll do that and revisit. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}