Spoetify.ipynb

{
 "metadata": {
  "name": "spoetify"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "raw",
     "metadata": {},
     "source": [
      "parallel query mech:\n",
      "* create a worker for every word local\n",
      "* parallel run each worker\n",
      "    page=1 round 1.1:  [do], [re], [mi], [fa], [sol]\n",
      "           round 1.2:  [do, re], [re, do], [mi, fa], [fa, sol]\n",
      "            ...\n",
      "    page=2 round 2.1:  ...\n",
      "    \n",
      "    each worker keeps track of its page and round\n",
      "* after each round check the graph for a path and decide whether to order another round or not\n",
      "    heuristic: if no path exists, order another round or page increase\n",
      "                if average edge (substring) length is smaller than 3-4, order another round but not a page increase\n",
      "                    else return the shortest path playlist\n",
      "* make sure to cache queries by term AND page"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from gevent import monkey; monkey.patch_socket()\n",
      "import spotimeta"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "raw",
     "metadata": {},
     "source": [
      "* cache only possibly useful stuff | if the track name is a substring of the poem\n",
      "* cache by term also - repeating substrings | \"take me far, take me away\"\n",
      "* there could be multiple matches - perhaps should make all available - maybe even tweak by mood or genre of something"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cache = {}\n",
      "\n",
      "def term_conditioner(term):\n",
      "    return term.lower()\n",
      "\n",
      "def query(term, s):\n",
      "    term = term_conditioner(term)\n",
      "    \n",
      "    has_results = False\n",
      "    if not cache.has_key(term):\n",
      "        response = spotimeta.search_track(term)\n",
      "        result = response['result']\n",
      "        if result:\n",
      "            has_results = True\n",
      "            for track in result:\n",
      "                name = track['name'].lower()\n",
      "                cache[name] = track\n",
      "    else:\n",
      "        print 'cache hit'\n",
      "    exact_match = cache.get(term)\n",
      "    return has_results, exact_match, s"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def slicer(iterable, start):\n",
      "    for stop in range(start, len(iterable)):\n",
      "        yield slice(start, stop + 1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import gevent\n",
      "import networkx as nx\n",
      "from itertools import izip_longest\n",
      "\n",
      "def investigate(words):\n",
      "    graph = nx.DiGraph()\n",
      "    \n",
      "    slicers = [slicer(words, i) for i in range(len(words))]\n",
      "    rounds = izip_longest(*slicers)\n",
      "    for r in rounds:\n",
      "        queries = []\n",
      "        for s in r:\n",
      "            if not s is None:\n",
      "                term = (' '.join(words[s]))\n",
      "                queries.append(gevent.spawn(query, term, s))\n",
      "        gevent.joinall(queries)\n",
      "        values = (query.value for query in queries)\n",
      "        for has_results, exact_match, s in values:\n",
      "            if not (has_results or exact_match):\n",
      "                break\n",
      "            elif exact_match:\n",
      "                graph.add_edge(s.start, s.stop + 1, track=exact_match)\n",
      "    return graph"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "words = \"If I can't let it go out of my mind\".split()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 27
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "graph = investigate(words)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "cache hit\n",
        "cache hit\n",
        "cache hit"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "cache hit\n",
        "cache hit"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "cache hit\n",
        "cache hit\n",
        "cache hit"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from itertools import tee, izip\n",
      "\n",
      "def pairwise(iterable):\n",
      "    \"s -> (s0,s1), (s1,s2), (s2, s3), ...\"\n",
      "    a, b = tee(iterable)\n",
      "    next(b, None)\n",
      "    return izip(a, b)\n",
      "\n",
      "if len(graph) > 0:\n",
      "    path = nx.shortest_path(graph, 0, len(words))\n",
      "    edges = pairwise(path)\n",
      "    print [graph.edge[start][stop]['track']['href'] for start, stop in edges]\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[u'spotify:track:7uKFB4W13N5WGZSmmr4bDl', u'spotify:track:5k7nFvA1srxjUfjo0zTxQC', u'spotify:track:2rilBmoyI8fqer3KTJnk9e']\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from collections import deque\n",
      "\n",
      "def bfs(graph, start, end):\n",
      "    parent = {}\n",
      "    queue = deque([start])\n",
      "    while queue:\n",
      "        node = queue.popleft()\n",
      "        # when we find the end node, backtrack\n",
      "        # to find the shortest path\n",
      "        if node == end:\n",
      "            path = [end]\n",
      "            while path[-1] != start:\n",
      "                path.append(parent[path[-1]])\n",
      "            path.reverse()\n",
      "            return path\n",
      "        for neighbor in graph[node]:\n",
      "            parent[neighbor] = node\n",
      "            queue.append(neighbor)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "path = bfs(graph, 0, len(words))\n",
      "path"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "[0, 3, 6, 10]"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit bfs(graph, 0, len(words))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100000 loops, best of 3: 15.4 us per loop\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit nx.shortest_path(graph, 0, len(words))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100000 loops, best of 3: 17.3 us per loop\n"
       ]
      }
     ],
     "prompt_number": 10
    }
   ],
   "metadata": {}
  }
 ]
}