Practice extra - Cython for KNN similarity.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recommender Systems 2018/19\n",
    "\n",
    "### Practice 4 - Similarity with Cython\n",
    "\n",
    "\n",
    "### Cython is a superset of Python, allowing you to use C-like operations and import C code. Cython files (.pyx) are compiled and support static typing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's implement something simple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPrime(n):\n",
    "    \n",
    "    i = 2\n",
    "    \n",
    "    # Usually you loop up to sqrt(n)\n",
    "    while i < n:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        \n",
    "        i += 1\n",
    "        \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is prime 2? True\n",
      "Is prime 3? True\n",
      "Is prime 5? True\n",
      "Is prime 15? False\n",
      "Is prime 20? False\n"
     ]
    }
   ],
   "source": [
    "print(\"Is prime 2? {}\".format(isPrime(2)))\n",
    "print(\"Is prime 3? {}\".format(isPrime(3)))\n",
    "print(\"Is prime 5? {}\".format(isPrime(5)))\n",
    "print(\"Is prime 15? {}\".format(isPrime(15)))\n",
    "print(\"Is prime 20? {}\".format(isPrime(20)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is Prime 80000023? True, time required 8.17 sec\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "result = isPrime(80000023)\n",
    "\n",
    "print(\"Is Prime 80000023? {}, time required {:.2f} sec\".format(result, time.time()-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Load Cython magic command, this takes care of the compilation step. If you are writing code outside Jupyter you'll have to compile using other tools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext Cython"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Declare Cython function, paste the same code as before. The function will be compiled and then executed with a Python interface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "def isPrime(n):\n",
    "    \n",
    "    i = 2\n",
    "    \n",
    "    # Usually you loop up to sqrt(n)\n",
    "    while i < n:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        \n",
    "        i += 1\n",
    "        \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is Prime 80000023? True, time required 3.97 sec\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "result = isPrime(80000023)\n",
    "\n",
    "print(\"Is Prime 80000023? {}, time required {:.2f} sec\".format(result, time.time()-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### As you can see by just compiling the same code we got some improvement.\n",
    "#### To go seriously higher, we have to use some static tiping"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "# Declare the tipe of the arguments\n",
    "def isPrime(long n):\n",
    "    \n",
    "    # Declare index of for loop\n",
    "    cdef long i\n",
    "    \n",
    "    i = 2\n",
    "    \n",
    "    # Usually you loop up to sqrt(n)\n",
    "    while i < n:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        \n",
    "        i += 1\n",
    "        \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is Prime 80000023? True, time required 0.25 sec\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "result = isPrime(80000023)\n",
    "\n",
    "print(\"Is Prime 80000023? {}, time required {:.2f} sec\".format(result, time.time()-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Cython code with two tipe declaration, for n and i, runs 50x faster than Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Main benefits of Cython:\n",
    "* Compiled, no interpreter\n",
    "* Static typing, no overhead\n",
    "* Fast loops, no need to vectorize. Vectorization sometimes performes lots of useless operations\n",
    "* Numpy, which is fast in python, becomes often slooooow compared to a carefully written Cython code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Similarity with Cython\n",
    "\n",
    "#### Load the usual data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DataReader: Preloaded data not found, reading from original files...\n",
      "Movielens10MReader: Unable to fild data zip file. Downloading...\n",
      "Downloading: http://files.grouplens.org/datasets/movielens/ml-10m.zip\n",
      "In folder: Data_manager_split_datasets/Movielens10M/ml-10m.zip\n",
      "DataReader: Downloaded 100.00%, 62.53 MB, 1685 KB/s, 38 seconds passed\n",
      "Movielens10MReader: loading genres\n",
      "Movielens10MReader: loading tags\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package stopwords to\n",
      "[nltk_data]     C:\\Users\\ferra\\AppData\\Roaming\\nltk_data...\n",
      "[nltk_data]   Unzipping corpora\\stopwords.zip.\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Movielens10MReader: loading URM\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\ferra\\PycharmProjects\\RecSys_Course_2018\\Data_manager\\Movielens20M\\Movielens20MReader.py:43: ParserWarning: Falling back to the 'python' engine because the 'c' engine does not support regex separators (separators > 1 char and different from '\\s+' are interpreted as regex); you can avoid this warning by specifying engine='python'.\n",
      "  dtype={0:str, 1:str, 2:float, 3:float})\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Movielens10MReader: cleaning temporary files\n",
      "Movielens10MReader: loading complete\n",
      "DataReader: Verifying data consistency...\n",
      "DataReader: Verifying data consistency... Passed!\n",
      "DataReader: Creating folder 'Data_manager_split_datasets/Movielens10M/original/'\n",
      "DataReader: Saving complete!\n",
      "DataReader: current dataset is: <class 'Data_manager.Movielens10M.Movielens10MReader.Movielens10MReader'>\n",
      "\tNumber of items: 10680\n",
      "\tNumber of users: 69878\n",
      "\tNumber of interactions in URM_all: 9973605\n",
      "\tInteraction density: 1.34E-02\n",
      "\tInteractions per user:\n",
      "\t\t Min: 1.90E+01\n",
      "\t\t Avg: 1.43E+02\n",
      "\t\t Max: 7.36E+03\n",
      "\tInteractions per item:\n",
      "\t\t Min: 0.00E+00\n",
      "\t\t Avg: 9.34E+02\n",
      "\t\t Max: 3.49E+04\n",
      "\tGini Index: 0.57\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from Data_manager.split_functions.split_train_validation_random_holdout import split_train_in_two_percentage_global_sample\n",
    "from Data_manager.Movielens10M.Movielens10MReader import Movielens10MReader\n",
    "\n",
    "data_reader = Movielens10MReader()\n",
    "data_reader.load_data()\n",
    "\n",
    "URM_all = data_reader.get_URM_all()\n",
    "\n",
    "URM_train, URM_test = split_train_in_two_percentage_global_sample(URM_all, train_percentage = 0.8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<69878x10680 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 7979148 stored elements in Compressed Sparse Row format>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "URM_train"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Since we cannot store in memory the whole similarity, we compute it one row at a time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(69878,)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "itemIndex=1\n",
    "item_ratings = URM_train[:,itemIndex]\n",
    "item_ratings = item_ratings.toarray().squeeze()\n",
    "\n",
    "item_ratings.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10680,)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "this_item_weights = URM_train.T.dot(item_ratings)\n",
    "this_item_weights.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Once we have the scores for that row, we get the TopK"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  30,   60, 1051,  720,  723,  639,  351,  256,  766,    1],\n",
       "      dtype=int64)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k=10\n",
    "\n",
    "top_k_idx = np.argsort(this_item_weights) [-k:]\n",
    "top_k_idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "import scipy.sparse as sps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function hiding some conversion checks\n",
    "def check_matrix(X, format='csc', dtype=np.float32):\n",
    "    if format == 'csc' and not isinstance(X, sps.csc_matrix):\n",
    "        return X.tocsc().astype(dtype)\n",
    "    elif format == 'csr' and not isinstance(X, sps.csr_matrix):\n",
    "        return X.tocsr().astype(dtype)\n",
    "    elif format == 'coo' and not isinstance(X, sps.coo_matrix):\n",
    "        return X.tocoo().astype(dtype)\n",
    "    elif format == 'dok' and not isinstance(X, sps.dok_matrix):\n",
    "        return X.todok().astype(dtype)\n",
    "    elif format == 'bsr' and not isinstance(X, sps.bsr_matrix):\n",
    "        return X.tobsr().astype(dtype)\n",
    "    elif format == 'dia' and not isinstance(X, sps.dia_matrix):\n",
    "        return X.todia().astype(dtype)\n",
    "    elif format == 'lil' and not isinstance(X, sps.lil_matrix):\n",
    "        return X.tolil().astype(dtype)\n",
    "    else:\n",
    "        return X.astype(dtype)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Create a Basic Collaborative filtering recommender using only cosine similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BasicItemKNN_CF_Recommender(object):\n",
    "    \"\"\" ItemKNN recommender with cosine similarity and no shrinkage\"\"\"\n",
    "\n",
    "    def __init__(self, URM):\n",
    "        self.dataset = URM\n",
    "        \n",
    "        \n",
    "    def compute_similarity(self, URM):\n",
    "        \n",
    "        # We explore the matrix column-wise\n",
    "        URM = check_matrix(URM, 'csc')     \n",
    "                    \n",
    "        values = []\n",
    "        rows = []\n",
    "        cols = []\n",
    "        \n",
    "        start_time = time.time()\n",
    "        processedItems = 0\n",
    "        \n",
    "        # Compute all similarities for each item using vectorization\n",
    "        for itemIndex in range(URM.shape[1]):\n",
    "            \n",
    "            processedItems += 1\n",
    "            \n",
    "            if processedItems % 100==0:\n",
    "                \n",
    "                itemPerSec = processedItems/(time.time()-start_time)\n",
    "                \n",
    "                print(\"Similarity item {}, {:.2f} item/sec, required time {:.2f} min\".format(\n",
    "                    processedItems, itemPerSec, URM.shape[1]/itemPerSec/60))\n",
    "            \n",
    "            # All ratings for a given item\n",
    "            item_ratings = URM[:,itemIndex]\n",
    "            item_ratings = item_ratings.toarray().squeeze()\n",
    "            \n",
    "            # Compute item similarities\n",
    "            this_item_weights = URM_train.T.dot(item_ratings)\n",
    "            \n",
    "            # Sort indices and select TopK\n",
    "            top_k_idx = np.argsort(this_item_weights) [-self.k:]\n",
    "            \n",
    "            # Incrementally build sparse matrix\n",
    "            values.extend(this_item_weights[top_k_idx])\n",
    "            rows.extend(np.arange(URM.shape[1])[top_k_idx])\n",
    "            cols.extend(np.ones(self.k) * itemIndex)\n",
    "            \n",
    "        self.W_sparse = sps.csc_matrix((values, (rows, cols)),\n",
    "                                       shape=(URM.shape[1], URM.shape[1]),\n",
    "                                       dtype=np.float32)\n",
    "\n",
    "        \n",
    "\n",
    "    def fit(self, k=50, shrinkage=100):\n",
    "\n",
    "        self.k = k\n",
    "        self.shrinkage = shrinkage\n",
    "        \n",
    "        item_weights = self.compute_similarity(self.dataset)\n",
    "        \n",
    "        item_weights = check_matrix(item_weights, 'csr')\n",
    "        \n",
    "        \n",
    "    def recommend(self, user_id, at=None, exclude_seen=True):\n",
    "        # compute the scores using the dot product\n",
    "        user_profile = self.URM[user_id]\n",
    "        scores = user_profile.dot(self.W_sparse).toarray().ravel()\n",
    "\n",
    "        if exclude_seen:\n",
    "            scores = self.filter_seen(user_id, scores)\n",
    "\n",
    "        # rank items\n",
    "        ranking = scores.argsort()[::-1]\n",
    "            \n",
    "        return ranking[:at]\n",
    "    \n",
    "    \n",
    "    def filter_seen(self, user_id, scores):\n",
    "\n",
    "        start_pos = self.URM.indptr[user_id]\n",
    "        end_pos = self.URM.indptr[user_id+1]\n",
    "\n",
    "        user_profile = self.URM.indices[start_pos:end_pos]\n",
    "        \n",
    "        scores[user_profile] = -np.inf\n",
    "\n",
    "        return scores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's isolate the compute_similarity function "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_similarity(URM, k=100):\n",
    "\n",
    "    # We explore the matrix column-wise\n",
    "    URM = check_matrix(URM, 'csc')\n",
    "    \n",
    "    n_items = URM.shape[1]\n",
    "\n",
    "    values = []\n",
    "    rows = []\n",
    "    cols = []\n",
    "\n",
    "    start_time = time.time()\n",
    "    processedItems = 0\n",
    "\n",
    "    # Compute all similarities for each item using vectorization\n",
    "    # for itemIndex in range(n_items):\n",
    "    for itemIndex in range(1000):\n",
    "\n",
    "        processedItems += 1\n",
    "\n",
    "        if processedItems % 100==0:\n",
    "\n",
    "            itemPerSec = processedItems/(time.time()-start_time)\n",
    "\n",
    "            print(\"Similarity item {}, {:.2f} item/sec, required time {:.2f} min\".format(\n",
    "                processedItems, itemPerSec, n_items/itemPerSec/60))\n",
    "\n",
    "        # All ratings for a given item\n",
    "        item_ratings = URM[:,itemIndex]\n",
    "        item_ratings = item_ratings.toarray().squeeze()\n",
    "\n",
    "        # Compute item similarities\n",
    "        this_item_weights = URM.T.dot(item_ratings)\n",
    "\n",
    "        # Sort indices and select TopK\n",
    "        top_k_idx = np.argsort(this_item_weights) [-k:]\n",
    "\n",
    "        # Incrementally build sparse matrix\n",
    "        values.extend(this_item_weights[top_k_idx])\n",
    "        rows.extend(np.arange(URM.shape[1])[top_k_idx])\n",
    "        cols.extend(np.ones(k) * itemIndex)\n",
    "\n",
    "    W_sparse = sps.csc_matrix((values, (rows, cols)),\n",
    "                            shape=(n_items, n_items),\n",
    "                            dtype=np.float32)\n",
    "\n",
    "    return W_sparse\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Similarity item 100, 86.50 item/sec, required time 2.06 min\n",
      "Similarity item 200, 86.39 item/sec, required time 2.06 min\n",
      "Similarity item 300, 86.53 item/sec, required time 2.06 min\n",
      "Similarity item 400, 86.48 item/sec, required time 2.06 min\n",
      "Similarity item 500, 86.37 item/sec, required time 2.06 min\n",
      "Similarity item 600, 86.36 item/sec, required time 2.06 min\n",
      "Similarity item 700, 86.30 item/sec, required time 2.06 min\n",
      "Similarity item 800, 86.30 item/sec, required time 2.06 min\n",
      "Similarity item 900, 86.40 item/sec, required time 2.06 min\n",
      "Similarity item 1000, 86.53 item/sec, required time 2.06 min\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<10680x10680 sparse matrix of type '<class 'numpy.float32'>'\n",
       "\twith 100000 stored elements in Compressed Sparse Column format>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_similarity(URM_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### We see that computing the similarity takes more or less 2 minutes\n",
    "### Now we use the same identical code, but we compile it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import time\n",
    "import numpy as np\n",
    "import scipy.sparse as sps\n",
    "\n",
    "def compute_similarity_compiled(URM, k=100):\n",
    "\n",
    "    # We explore the matrix column-wise\n",
    "    URM = URM.tocsc()\n",
    "    \n",
    "    n_items = URM.shape[1]\n",
    "\n",
    "    values = []\n",
    "    rows = []\n",
    "    cols = []\n",
    "\n",
    "    start_time = time.time()\n",
    "    processedItems = 0\n",
    "\n",
    "    # Compute all similarities for each item using vectorization\n",
    "    # for itemIndex in range(n_items):\n",
    "    for itemIndex in range(1000):\n",
    "\n",
    "        processedItems += 1\n",
    "\n",
    "        if processedItems % 100==0:\n",
    "\n",
    "            itemPerSec = processedItems/(time.time()-start_time)\n",
    "\n",
    "            print(\"Similarity item {}, {:.2f} item/sec, required time {:.2f} min\".format(\n",
    "                processedItems, itemPerSec, n_items/itemPerSec/60))\n",
    "\n",
    "        # All ratings for a given item\n",
    "        item_ratings = URM[:,itemIndex]\n",
    "        item_ratings = item_ratings.toarray().squeeze()\n",
    "\n",
    "        # Compute item similarities\n",
    "        this_item_weights = URM.T.dot(item_ratings)\n",
    "\n",
    "        # Sort indices and select TopK\n",
    "        top_k_idx = np.argsort(this_item_weights) [-k:]\n",
    "\n",
    "        # Incrementally build sparse matrix\n",
    "        values.extend(this_item_weights[top_k_idx])\n",
    "        rows.extend(np.arange(URM.shape[1])[top_k_idx])\n",
    "        cols.extend(np.ones(k) * itemIndex)\n",
    "\n",
    "    W_sparse = sps.csc_matrix((values, (rows, cols)),\n",
    "                            shape=(n_items, n_items),\n",
    "                            dtype=np.float32)\n",
    "\n",
    "    return W_sparse\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Similarity item 100, 59.41 item/sec, required time 3.00 min\n",
      "Similarity item 200, 58.89 item/sec, required time 3.02 min\n",
      "Similarity item 300, 58.62 item/sec, required time 3.04 min\n",
      "Similarity item 400, 58.72 item/sec, required time 3.03 min\n",
      "Similarity item 500, 58.69 item/sec, required time 3.03 min\n",
      "Similarity item 600, 58.57 item/sec, required time 3.04 min\n",
      "Similarity item 700, 58.59 item/sec, required time 3.04 min\n",
      "Similarity item 800, 58.51 item/sec, required time 3.04 min\n",
      "Similarity item 900, 58.52 item/sec, required time 3.04 min\n",
      "Similarity item 1000, 58.63 item/sec, required time 3.04 min\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<10680x10680 sparse matrix of type '<class 'numpy.float32'>'\n",
       "\twith 100000 stored elements in Compressed Sparse Column format>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_similarity_compiled(URM_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### As opposed to the previous example, compilation by itself is not very helpful. Why?\n",
    "#### Because the compiler is just porting in C all operations that the python interpreter would have to perform, dynamic tiping included\n",
    "\n",
    "### Now try to add some tipes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import time\n",
    "import numpy as np\n",
    "import scipy.sparse as sps\n",
    "\n",
    "cimport numpy as np\n",
    "\n",
    "\"\"\"\n",
    "Determine the operative system. The interface of numpy returns a different type for argsort under windows and linux\n",
    "\n",
    "http://docs.cython.org/en/latest/src/userguide/language_basics.html#conditional-compilation\n",
    "\"\"\"\n",
    "IF UNAME_SYSNAME == \"linux\":\n",
    "    DEF LONG_t = \"long\"\n",
    "ELIF  UNAME_SYSNAME == \"Windows\":\n",
    "    DEF LONG_t = \"long long\"\n",
    "ELSE:\n",
    "    DEF LONG_t = \"long long\"\n",
    "    \n",
    "def compute_similarity_compiled(URM, int k=100):\n",
    "    \n",
    "    cdef int itemIndex, processedItems\n",
    "    \n",
    "    # We use the numpy syntax, allowing us to perform vectorized operations\n",
    "    cdef np.ndarray[double, ndim=1] item_ratings, this_item_weights\n",
    "    cdef np.ndarray[LONG_t, ndim=1] top_k_idx\n",
    "\n",
    "    # We explore the matrix column-wise\n",
    "    URM = URM.tocsc()\n",
    "    \n",
    "    n_items = URM.shape[1]\n",
    "\n",
    "    values = []\n",
    "    rows = []\n",
    "    cols = []\n",
    "\n",
    "    start_time = time.time()\n",
    "    processedItems = 0\n",
    "\n",
    "    # Compute all similarities for each item using vectorization\n",
    "    # for itemIndex in range(n_items):\n",
    "    for itemIndex in range(1000):\n",
    "\n",
    "        processedItems += 1\n",
    "\n",
    "        if processedItems % 100==0:\n",
    "\n",
    "            itemPerSec = processedItems/(time.time()-start_time)\n",
    "\n",
    "            print(\"Similarity item {}, {:.2f} item/sec, required time {:.2f} min\".format(\n",
    "                processedItems, itemPerSec, n_items/itemPerSec/60))\n",
    "\n",
    "        # All ratings for a given item\n",
    "        item_ratings = URM[:,itemIndex].toarray().squeeze()\n",
    "\n",
    "        # Compute item similarities\n",
    "        this_item_weights = URM.T.dot(item_ratings)\n",
    "\n",
    "        # Sort indices and select TopK\n",
    "        top_k_idx = np.argsort(this_item_weights) [-k:]\n",
    "\n",
    "        # Incrementally build sparse matrix\n",
    "        values.extend(this_item_weights[top_k_idx])\n",
    "        rows.extend(np.arange(URM.shape[1])[top_k_idx])\n",
    "        cols.extend(np.ones(k) * itemIndex)\n",
    "\n",
    "    W_sparse = sps.csc_matrix((values, (rows, cols)),\n",
    "                            shape=(n_items, n_items),\n",
    "                            dtype=np.float32)\n",
    "\n",
    "    return W_sparse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Similarity item 100, 58.10 item/sec, required time 3.06 min\n",
      "Similarity item 200, 57.39 item/sec, required time 3.10 min\n",
      "Similarity item 300, 57.14 item/sec, required time 3.12 min\n",
      "Similarity item 400, 57.03 item/sec, required time 3.12 min\n",
      "Similarity item 500, 57.07 item/sec, required time 3.12 min\n",
      "Similarity item 600, 57.11 item/sec, required time 3.12 min\n",
      "Similarity item 700, 57.12 item/sec, required time 3.12 min\n",
      "Similarity item 800, 56.94 item/sec, required time 3.13 min\n",
      "Similarity item 900, 57.01 item/sec, required time 3.12 min\n",
      "Similarity item 1000, 57.11 item/sec, required time 3.12 min\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<10680x10680 sparse matrix of type '<class 'numpy.float32'>'\n",
       "\twith 100000 stored elements in Compressed Sparse Column format>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_similarity_compiled(URM_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Still no luck! Why?\n",
    "### There are a few reasons:\n",
    "* We are getting the data from the sparse matrix using its interface, which is SLOW\n",
    "* We are transforming sparse data into a dense array, which is SLOW\n",
    "* We are performing a dot product against a dense vector\n",
    "\n",
    "#### You colud find a workaround... here we do something different"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Proposed solution\n",
    "### Change the algorithm!\n",
    "\n",
    "### Instead of performing the dot product, let's implement somenting that computes the similarity using sparse data directly\n",
    "\n",
    "### We loop through the data and update selectively the similarity matrix cells. \n",
    "### Underlying idea:\n",
    "* When I select an item I can know which users rated it\n",
    "* Instead of looping through the other items trying to find common users, I use the URM to find which other items that user rated\n",
    "* The user I am considering will be common between the two, so I increment the similarity of the two items\n",
    "* Instead of following the path item1 -> loop item2 -> find user, i go item1 -> loop user -> loop item2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 1, 0, 1],\n",
       "        [0, 1, 1, 1],\n",
       "        [1, 0, 1, 0]], dtype=int32)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data_matrix = np.array([[1,1,0,1],[0,1,1,1],[1,0,1,0]])\n",
    "data_matrix = sps.csc_matrix(data_matrix)\n",
    "data_matrix.todense()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: Compute the similarities for item 1\n",
    "\n",
    "#### Step 1: get users that rated item 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 1])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "users_rated_item = data_matrix[:,1]\n",
    "users_rated_item.indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 2: count how many times those users rated other items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 1, 2])"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_similarity = data_matrix[users_rated_item.indices].sum(axis = 0)\n",
    "np.array(item_similarity).squeeze()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Verify our result against the common method. We can see that the similarity values for col 1 are identical"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 2, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "similarity_matrix_product = data_matrix.T.dot(data_matrix)\n",
    "similarity_matrix_product.toarray()[:,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The following code works for implicit feedback only\n",
    "def compute_similarity_new_algorithm(URM, k=100):\n",
    "\n",
    "    # We explore the matrix column-wise\n",
    "    URM = check_matrix(URM, 'csc')\n",
    "    URM.data = np.ones_like(URM.data)\n",
    "    \n",
    "    n_items = URM.shape[1]\n",
    "\n",
    "    values = []\n",
    "    rows = []\n",
    "    cols = []\n",
    "\n",
    "    start_time = time.time()\n",
    "    processedItems = 0\n",
    "\n",
    "    # Compute all similarities for each item using vectorization\n",
    "    # for itemIndex in range(n_items):\n",
    "    for itemIndex in range(1000):\n",
    "\n",
    "        processedItems += 1\n",
    "\n",
    "        if processedItems % 100==0:\n",
    "\n",
    "            itemPerSec = processedItems/(time.time()-start_time)\n",
    "\n",
    "            print(\"Similarity item {}, {:.2f} item/sec, required time {:.2f} min\".format(\n",
    "                processedItems, itemPerSec, n_items/itemPerSec/60))\n",
    "\n",
    "        # All ratings for a given item\n",
    "        users_rated_item = URM.indices[URM.indptr[itemIndex]:URM.indptr[itemIndex+1]]\n",
    "\n",
    "        # Compute item similarities\n",
    "        this_item_weights = URM[users_rated_item].sum(axis = 0)\n",
    "        this_item_weights = np.array(this_item_weights).squeeze()\n",
    "\n",
    "        # Sort indices and select TopK\n",
    "        top_k_idx = np.argsort(this_item_weights) [-k:]\n",
    "\n",
    "        # Incrementally build sparse matrix\n",
    "        values.extend(this_item_weights[top_k_idx])\n",
    "        rows.extend(np.arange(URM.shape[1])[top_k_idx])\n",
    "        cols.extend(np.ones(k) * itemIndex)\n",
    "\n",
    "    W_sparse = sps.csc_matrix((values, (rows, cols)),\n",
    "                            shape=(n_items, n_items),\n",
    "                            dtype=np.float32)\n",
    "\n",
    "    return W_sparse\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Similarity item 100, 21.28 item/sec, required time 8.36 min\n",
      "Similarity item 200, 22.35 item/sec, required time 7.96 min\n",
      "Similarity item 300, 22.52 item/sec, required time 7.91 min\n",
      "Similarity item 400, 22.19 item/sec, required time 8.02 min\n",
      "Similarity item 500, 22.45 item/sec, required time 7.93 min\n",
      "Similarity item 600, 22.12 item/sec, required time 8.05 min\n",
      "Similarity item 700, 23.05 item/sec, required time 7.72 min\n",
      "Similarity item 800, 23.51 item/sec, required time 7.57 min\n",
      "Similarity item 900, 23.94 item/sec, required time 7.43 min\n",
      "Similarity item 1000, 24.27 item/sec, required time 7.33 min\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<10680x10680 sparse matrix of type '<class 'numpy.float32'>'\n",
       "\twith 100000 stored elements in Compressed Sparse Column format>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_similarity_new_algorithm(URM_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Slower but expected, dot product operations are implemented in an efficient way and here we are using an indirect approach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Now let's write this algorithm in Cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "\n",
    "import time\n",
    "\n",
    "import numpy as np\n",
    "cimport numpy as np\n",
    "from cpython.array cimport array, clone\n",
    "\n",
    "import scipy.sparse as sps\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "Determine the operative system. The interface of numpy returns a different type for argsort under windows and linux\n",
    "\n",
    "http://docs.cython.org/en/latest/src/userguide/language_basics.html#conditional-compilation\n",
    "\"\"\"\n",
    "IF UNAME_SYSNAME == \"linux\":\n",
    "    DEF LONG_t = \"long\"\n",
    "ELIF  UNAME_SYSNAME == \"Windows\":\n",
    "    DEF LONG_t = \"long long\"\n",
    "ELSE:\n",
    "    DEF LONG_t = \"long long\"\n",
    "\n",
    "\n",
    "\n",
    "cdef class Cosine_Similarity:\n",
    "\n",
    "    cdef int TopK\n",
    "    cdef long n_items\n",
    "\n",
    "    # Arrays containing the sparse data\n",
    "    cdef int[:] user_to_item_row_ptr, user_to_item_cols\n",
    "    cdef int[:] item_to_user_rows, item_to_user_col_ptr\n",
    "    cdef double[:] user_to_item_data, item_to_user_data\n",
    "\n",
    "    # In case you select no TopK\n",
    "    cdef double[:,:] W_dense\n",
    "\n",
    "    \n",
    "    def __init__(self, URM, TopK = 100):\n",
    "        \"\"\"\n",
    "        Dataset must be a matrix with items as columns\n",
    "        :param dataset:\n",
    "        :param TopK:\n",
    "        \"\"\"\n",
    "\n",
    "        super(Cosine_Similarity, self).__init__()\n",
    "\n",
    "        self.n_items = URM.shape[1]\n",
    "\n",
    "        self.TopK = min(TopK, self.n_items)\n",
    "\n",
    "        URM = URM.tocsr()\n",
    "        self.user_to_item_row_ptr = URM.indptr\n",
    "        self.user_to_item_cols = URM.indices\n",
    "        self.user_to_item_data = np.array(URM.data, dtype=np.float64)\n",
    "\n",
    "        URM = URM.tocsc()\n",
    "        self.item_to_user_rows = URM.indices\n",
    "        self.item_to_user_col_ptr = URM.indptr\n",
    "        self.item_to_user_data = np.array(URM.data, dtype=np.float64)\n",
    "\n",
    "        if self.TopK == 0:\n",
    "            self.W_dense = np.zeros((self.n_items,self.n_items))\n",
    "\n",
    "\n",
    "\n",
    "    cdef int[:] getUsersThatRatedItem(self, long item_id):\n",
    "        return self.item_to_user_rows[self.item_to_user_col_ptr[item_id]:self.item_to_user_col_ptr[item_id+1]]\n",
    "\n",
    "    cdef int[:] getItemsRatedByUser(self, long user_id):\n",
    "        return self.user_to_item_cols[self.user_to_item_row_ptr[user_id]:self.user_to_item_row_ptr[user_id+1]]\n",
    "\n",
    "    \n",
    "    \n",
    "    cdef double[:] computeItemSimilarities(self, long item_id_input):\n",
    "        \"\"\"\n",
    "        For every item the cosine similarity against other items depends on whether they have users in common. \n",
    "        The more common users the higher the similarity.\n",
    "        \n",
    "        The basic implementation is:\n",
    "        - Select the first item\n",
    "        - Loop through all other items\n",
    "        -- Given the two items, get the users they have in common\n",
    "        -- Update the similarity considering all common users\n",
    "        \n",
    "        That is VERY slow due to the common user part, in which a long data structure is looped multiple times.\n",
    "        \n",
    "        A better way is to use the data structure in a different way skipping the search part, getting directly\n",
    "        the information we need.\n",
    "        \n",
    "        The implementation here used is:\n",
    "        - Select the first item\n",
    "        - Initialize a zero valued array for the similarities\n",
    "        - Get the users who rated the first item\n",
    "        - Loop through the users\n",
    "        -- Given a user, get the items he rated (second item)\n",
    "        -- Update the similarity of the items he rated\n",
    "        \n",
    "        \n",
    "        \"\"\"\n",
    "\n",
    "        # Create template used to initialize an array with zeros\n",
    "        # Much faster than np.zeros(self.n_items)\n",
    "        cdef array[double] template_zero = array('d')\n",
    "        cdef array[double] result = clone(template_zero, self.n_items, zero=True)\n",
    "\n",
    "\n",
    "        cdef long user_index, user_id, item_index, item_id_second\n",
    "\n",
    "        cdef int[:] users_that_rated_item = self.getUsersThatRatedItem(item_id_input)\n",
    "        cdef int[:] items_rated_by_user\n",
    "\n",
    "        cdef double rating_item_input, rating_item_second\n",
    "\n",
    "        # Get users that rated the items\n",
    "        for user_index in range(len(users_that_rated_item)):\n",
    "\n",
    "            user_id = users_that_rated_item[user_index]\n",
    "            rating_item_input = self.item_to_user_data[self.item_to_user_col_ptr[item_id_input]+user_index]\n",
    "\n",
    "            # Get all items rated by that user\n",
    "            items_rated_by_user = self.getItemsRatedByUser(user_id)\n",
    "\n",
    "            for item_index in range(len(items_rated_by_user)):\n",
    "\n",
    "                item_id_second = items_rated_by_user[item_index]\n",
    "\n",
    "                # Do not compute the similarity on the diagonal\n",
    "                if item_id_second != item_id_input:\n",
    "                    # Increment similairty\n",
    "                    rating_item_second = self.user_to_item_data[self.user_to_item_row_ptr[user_id]+item_index]\n",
    "\n",
    "                    result[item_id_second] += rating_item_input*rating_item_second\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "    def compute_similarity(self):\n",
    "\n",
    "        cdef int itemIndex, innerItemIndex\n",
    "        cdef long long topKItemIndex\n",
    "\n",
    "        cdef long long[:] top_k_idx\n",
    "\n",
    "        # Declare numpy data type to use vetor indexing and simplify the topK selection code\n",
    "        cdef np.ndarray[LONG_t, ndim=1] top_k_partition, top_k_partition_sorting\n",
    "        cdef np.ndarray[np.float64_t, ndim=1] this_item_weights_np\n",
    "\n",
    "        cdef double[:] this_item_weights\n",
    "\n",
    "        cdef long processedItems = 0\n",
    "\n",
    "        # Data structure to incrementally build sparse matrix\n",
    "        # Preinitialize max possible length\n",
    "        cdef double[:] values = np.zeros((self.n_items*self.TopK))\n",
    "        cdef int[:] rows = np.zeros((self.n_items*self.TopK,), dtype=np.int32)\n",
    "        cdef int[:] cols = np.zeros((self.n_items*self.TopK,), dtype=np.int32)\n",
    "        cdef long sparse_data_pointer = 0\n",
    "\n",
    "\n",
    "        start_time = time.time()\n",
    "\n",
    "        # Compute all similarities for each item\n",
    "        for itemIndex in range(self.n_items):\n",
    "\n",
    "            processedItems += 1\n",
    "\n",
    "            if processedItems % 10000==0 or processedItems==self.n_items:\n",
    "\n",
    "                itemPerSec = processedItems/(time.time()-start_time)\n",
    "\n",
    "                print(\"Similarity item {} ( {:2.0f} % ), {:.2f} item/sec, required time {:.2f} min\".format(\n",
    "                    processedItems, processedItems*1.0/self.n_items*100, itemPerSec, (self.n_items-processedItems) / itemPerSec / 60))\n",
    "\n",
    "            this_item_weights = self.computeItemSimilarities(itemIndex)\n",
    "\n",
    "            if self.TopK == 0:\n",
    "\n",
    "                for innerItemIndex in range(self.n_items):\n",
    "                    self.W_dense[innerItemIndex,itemIndex] = this_item_weights[innerItemIndex]\n",
    "\n",
    "            else:\n",
    "\n",
    "                # Sort indices and select TopK\n",
    "                # Using numpy implies some overhead, unfortunately the plain C qsort function is even slower\n",
    "                # top_k_idx = np.argsort(this_item_weights) [-self.TopK:]\n",
    "\n",
    "                # Sorting is done in three steps. Faster then plain np.argsort for higher number of items\n",
    "                # because we avoid sorting elements we already know we don't care about\n",
    "                # - Partition the data to extract the set of TopK items, this set is unsorted\n",
    "                # - Sort only the TopK items, discarding the rest\n",
    "                # - Get the original item index\n",
    "\n",
    "                this_item_weights_np = - np.array(this_item_weights)\n",
    "                \n",
    "                # Get the unordered set of topK items\n",
    "                top_k_partition = np.argpartition(this_item_weights_np, self.TopK-1)[0:self.TopK]\n",
    "                # Sort only the elements in the partition\n",
    "                top_k_partition_sorting = np.argsort(this_item_weights_np[top_k_partition])\n",
    "                # Get original index\n",
    "                top_k_idx = top_k_partition[top_k_partition_sorting]\n",
    "\n",
    "\n",
    "\n",
    "                # Incrementally build sparse matrix\n",
    "                for innerItemIndex in range(len(top_k_idx)):\n",
    "\n",
    "                    topKItemIndex = top_k_idx[innerItemIndex]\n",
    "\n",
    "                    values[sparse_data_pointer] = this_item_weights[topKItemIndex]\n",
    "                    rows[sparse_data_pointer] = topKItemIndex\n",
    "                    cols[sparse_data_pointer] = itemIndex\n",
    "\n",
    "                    sparse_data_pointer += 1\n",
    "\n",
    "\n",
    "        if self.TopK == 0:\n",
    "\n",
    "            return np.array(self.W_dense)\n",
    "\n",
    "        else:\n",
    "\n",
    "            values = np.array(values[0:sparse_data_pointer])\n",
    "            rows = np.array(rows[0:sparse_data_pointer])\n",
    "            cols = np.array(cols[0:sparse_data_pointer])\n",
    "\n",
    "            W_sparse = sps.csr_matrix((values, (rows, cols)),\n",
    "                                    shape=(self.n_items, self.n_items),\n",
    "                                    dtype=np.float32)\n",
    "\n",
    "            return W_sparse\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Similarity item 10000 ( 94 % ), 741.80 item/sec, required time 0.02 min\n",
      "Similarity item 10680 ( 100 % ), 781.29 item/sec, required time 0.00 min\n",
      "Similarity computed in 13.71 seconds\n"
     ]
    }
   ],
   "source": [
    "cosine_cython = Cosine_Similarity(URM_train, TopK=100)\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "cosine_cython.compute_similarity()\n",
    "\n",
    "print(\"Similarity computed in {:.2f} seconds\".format(time.time()-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Better... much better. There are a few other things you could do, but at this point it is not worth the effort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## How to use Cython outside a notebook\n",
    "\n",
    "### Step1: Create a .pyx file and write your code\n",
    "\n",
    "### Step2: Create a compilation script \"compileCython.py\" with the following content"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This code will not run in a notebook cell\n",
    "\n",
    "try:\n",
    "    from setuptools import setup\n",
    "    from setuptools import Extension\n",
    "except ImportError:\n",
    "    from distutils.core import setup\n",
    "    from distutils.extension import Extension\n",
    "\n",
    "\n",
    "from Cython.Distutils import build_ext\n",
    "import numpy\n",
    "import sys\n",
    "import re\n",
    "\n",
    "\n",
    "if len(sys.argv) != 4:\n",
    "    raise ValueError(\"Wrong number of paramethers received. Expected 4, got {}\".format(sys.argv))\n",
    "\n",
    "\n",
    "# Get the name of the file to compile\n",
    "fileToCompile = sys.argv[1]\n",
    "\n",
    "# Remove the argument from sys argv in order for it to contain only what setup needs\n",
    "del sys.argv[1]\n",
    "\n",
    "extensionName = re.sub(\"\\.pyx\", \"\", fileToCompile)\n",
    "\n",
    "\n",
    "ext_modules = Extension(extensionName,\n",
    "                [fileToCompile],\n",
    "                extra_compile_args=['-O3'],\n",
    "                include_dirs=[numpy.get_include(),],\n",
    "                )\n",
    "\n",
    "setup(\n",
    "    cmdclass={'build_ext': build_ext},\n",
    "    ext_modules=[ext_modules]\n",
    ")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step3: Compile your code with the following command \n",
    "\n",
    "python compileCython.py Cosine_Similarity_Cython.pyx build_ext --inplace"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step4: Generate cython report and look for \"yellow lines\". The report is an .html file which represents how many operations are necessary to translate each python operation in cython code. If a line is white, it has a direct C translation. If it is yellow it will require many indirect steps that will slow down execution. Some of those steps may be inevitable, some may be removed via static typing.\n",
    "\n",
    "### IMPORTANT: white does not mean fast!! If a system call is involved that part might be slow anyway.\n",
    "\n",
    "cython -a Cosine_Similarity_Cython.pyx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step5: Add static types and C functions to remove \"yellow\" lines.\n",
    "\n",
    "#### If you use a variable only as a C object, use primitive tipes \n",
    "cdef int namevar\n",
    "\n",
    "def double namevar\n",
    "\n",
    "cdef float namevar\n",
    "\n",
    "#### If you call a function only within C code, use a specific declaration \"cdef\"\n",
    "\n",
    "cdef function_name(self, int param1, double param2):\n",
    "...\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step6: Iterate step 4 and 5 until you are satisfied with how clean your code is, then compile. An example of non optimized code can be found in the source folder of this notebook with the _SLOW suffix\n",
    "\n",
    "## Step7: the compilation generates a file wose name is something like \"Cosine_Similarity_Cython.cpython-36m-x86_64-linux-gnu.so\" and tells you the source file, the architecture it is compiled for and the OS\n",
    "\n",
    "## Step8: Import and use the compiled file as if it were a python class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Base.Simialrity.Cython.Cosine_Similarity_Cython import Cosine_Similarity\n",
    "\n",
    "cosine_cython = Cosine_Similarity(URM_train, TopK=100)\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "cosine_cython.compute_similarity()\n",
    "\n",
    "print(\"Similarity computed in {:.2f} seconds\".format(time.time()-start_time))"
   ]
  },
  {
   "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}