Presentation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Принципы обработки больших данных\n",
    "Дмитрий Бугайченко, Mail.ru"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Принцип 1\n",
    "\n",
    "\n",
    "__Большие данные – это то, что вы не можете втянуть в память на одной машине__\n",
    "\n",
    "### Применительно к нашей задаче\n",
    "\n",
    "* Объем данных (текст в гзипе) меньше гигабайта. Для обработки в таком случае обычно достаточно 6-8 гигабайт, но можно упереться рогом и уложится и в 4.\n",
    "* И это хорошо, так как питон это не инструмент больших данных \n",
    "* Но остальные принципы продолжают работать"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Принцип 2\n",
    "\n",
    "__Верное решение это простое решение__\n",
    "\n",
    "### Применительно к нашей задаче\n",
    "\n",
    "* Первый прогноз можно построить по счетчику общих друзей\n",
    "* Выданный граф не симетричный (по сути двудольный), чтобы удобно считать общих друзей нужно его развернуть\n",
    "* Имея в памяти основной и развернуты графы задача решается просто"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Попытка номер 1\n",
    "\n",
    "Рекомендуем в качестве друзей тех, у кого много общих друзей с нами. Для этого втягиваем в память словарь вида [я->мои друзья], и его же в \"развернутом виде\" [я->те у кого я в друзьях]\n",
    "\n",
    "Для начала импортнем пакеты для работы с файлами"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Для чтения/записи csv файлов\n",
    "import csv\n",
    "# Для работы с архивами\n",
    "import gzip\n",
    "# Для работы с файловой системой\n",
    "import os\n",
    "\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Законстантим относителные пути"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Пути к данным\n",
    "dataPath = \"./\"\n",
    "graphPath = os.path.join(dataPath, \"trainGraph\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь будем читать"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mineFriends = defaultdict(list)\n",
    "friendsOfMine = defaultdict(list)\n",
    "\n",
    "# Итерируемся по файлам в папке\n",
    "for file in [f for f in os.listdir(graphPath) if f.startswith(\"part\")]:\n",
    "    csvinput = gzip.open(os.path.join(graphPath, file))\n",
    "    csv_reader = csv.reader(csvinput, delimiter='\\t')\n",
    "    # А теперь по строкам в файле\n",
    "    for line in csv_reader:\n",
    "        user = int(line[0]) \n",
    "        # Разбираем идшки и маски друзей\n",
    "        for friendship in line[1].replace(\"{(\", \"\").replace(\")}\", \"\").split(\"),(\"):\n",
    "            parts=friendship.split(\",\")\n",
    "            friend = int(parts[0])\n",
    "            mineFriends[user] += [friend]\n",
    "            friendsOfMine[friend] += [user]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Все бы ничего, но два словарика в памяти *уже* заняли больше трех гигабайт и дальше ворочать их будет неудобно. Но поробуем..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-4-50b962fc16e3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mfriend\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfriends\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0mtheirFriend\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mfriendsOfMine\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mfriend\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m             \u001b[0mfriendsOfFriends\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0muser\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mtheirFriend\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "friendsOfFriends = defaultdict(lambda: defaultdict(int))\n",
    "\n",
    "for (user,friends) in mineFriends.iteritems():\n",
    "    for friend in friends:\n",
    "        for theirFriend in friendsOfMine[friend]:\n",
    "            friendsOfFriends[user][theirFriend] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На 22-х гигах пришлось прибить... Теперь надо еще и вычистить из памяти шлак."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "del friendsOfFriends\n",
    "del mineFriends\n",
    "del friendsOfMine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Принцип 3\n",
    "\n",
    "__Семь раз отмерь, один втяни.__\n",
    "\n",
    "### Применительно к нашей задаче\n",
    "\n",
    "* Стоит заранее оценить объемы памяти, которые потребуются\n",
    "* Использовать подходящие структуры данных"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ислледуем данные\n",
    "\n",
    "Если с ходу не получилось, значит пришло время задуматся о том, как использовать память эффективнее. Для начала давайте попробуем прикинуть базовые показатели графа с которым работаем."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Num users from 107474, max 16619036, num total 12417564, max 16619131, num links 36192484\n"
     ]
    }
   ],
   "source": [
    "numUsersFrom = 0\n",
    "numLinks = 0\n",
    "maxUserIdFrom = 0\n",
    "maxUserIdTo = 0\n",
    "allIds = set()\n",
    "\n",
    "for file in [f for f in os.listdir(graphPath) if f.startswith(\"part\")]:\n",
    "    csvinput = gzip.open(os.path.join(graphPath, file))\n",
    "    csv_reader = csv.reader(csvinput, delimiter='\\t')\n",
    "    for line in csv_reader:\n",
    "        user = int(line[0])\n",
    "        numUsersFrom += 1\n",
    "        maxUserIdFrom = max(user,maxUserIdFrom)\n",
    "        allIds.add(user)\n",
    "        for friendship in line[1].replace(\"{(\", \"\").replace(\")}\", \"\").split(\"),(\"):\n",
    "            parts=friendship.split(\",\")\n",
    "            friend = int(parts[0])\n",
    "            allIds.add(friend)\n",
    "            numLinks += 1\n",
    "            maxUserIdTo = max(maxUserIdTo,friend)\n",
    "            \n",
    "print(\"Num users from {0}, max {1}, num total {2}, max {3}, num links {4}\".format(\n",
    "        numUsersFrom,maxUserIdFrom,len(allIds),maxUserIdTo,numLinks))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Выбираем структуры данных\n",
    "\n",
    "### Словари\n",
    "\n",
    "* Легко пользоватся.\n",
    "* Но _ОЧЕНЬ_ много накладных расходов: указатель на запись, указатель на ключ/значение, объектная обертка для ключа и значения.\n",
    "* Итого: на пару инт-инт _накладных_ расходов 48 байт (facepalm).\n",
    "* Данные размазаны по памяти и фрагментированны - кеш процессора резко терят эффективность.\n",
    "\n",
    "### Списки\n",
    "\n",
    "* Если ключ инт - можно использовать вместо словаря.\n",
    "* НО! Список в питоне это массив указателей, а значит накладные расходы на указатель и объектную обертку ключа. остаются - 20 байт накладных расходов на запист :(.\n",
    "* Проблема с потерей эффективности кеша сохраняется.\n",
    "\n",
    "### Массивы numpy\n",
    "\n",
    "* На пару инт-инт нужно всего 4 байта.\n",
    "* Кеш процессора работает.\n",
    "* Но нужно чтобы ключи шли последовательно (к счастью, в наших даных это так почти так: максимальный ид 16619131 при общем числе 12417564).\n",
    "* Для того чтобы заполнить массив _очень_ желательно знать его размер изначально.\n",
    "* Если делать двумерный массив 100к на 16м - будет очень, очень, очень больно...\n",
    "\n",
    "### Спарс матрицы scipy\n",
    "\n",
    "* Предназначены для хранения двмерных матриц с очень большим количеством нулей.\n",
    "* Эффективные варианты хранят в виде нескольких массивов numpy.\n",
    "* COO - три массива одинаковой длинны моделируют списов троек [(i,j,v)]. Просто строить, легко интегрировать с пандой.\n",
    "* CSR - один маленьки массив с индексом начала для каждого ряда (монотонно растет), и два массива равно длинны с ид колонки и значением: [{i : [(j,v)]}]. Более компактна в памяти, быстрые опреации.\n",
    "* CSC - тоже самое что CSR, но индексированны колонки.\n",
    "\n",
    "### Применительно к нашей задаче\n",
    "\n",
    "* Инициализруем граф в виде COO матрицы, затем переводим в CSR.\n",
    "* Развернутый граф получаем с помощью транспонирования.\n",
    "* Общих друзей считаем умножая матрицы."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Попытка номер 2\n",
    "\n",
    "Считаем на базе матриц!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Почистим шлак и оставим константы чтоб потом не пресчитывать\n",
    "del allIds\n",
    "maxUserId = 16619131\n",
    "numLinks = 36192484"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Эффективные массивы простых типов\n",
    "import numpy\n",
    "# Работа с матрицами (подсчет общих друзей реализован как умножение матрицы графа самое на себя)\n",
    "import scipy\n",
    "from scipy.sparse import coo_matrix, csr_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Собственно давайте попробуем вчитать матрицу используя coc формат и затем преобразуем в csr."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# В этих массивах мы будем собирать данные. Инициализируем их заранее нужным размером чтобы \n",
    "# небыло лишнего копирования\n",
    "formUser = numpy.zeros( (numLinks), dtype=numpy.int32 ) \n",
    "toUser = numpy.zeros( (numLinks), dtype=numpy.int32 ) \n",
    "data = numpy.ones( (numLinks), dtype=numpy.int16 ) \n",
    "\n",
    "# Здесь храним позицию, на которую надо записать новую связь\n",
    "current = 0\n",
    "\n",
    "# Итерируемся по файлам в папке... Да, опять. God bless Cmd+C/Cmd+V\n",
    "for file in [f for f in os.listdir(graphPath) if f.startswith(\"part\")]:\n",
    "    csvinput = gzip.open(os.path.join(graphPath, file))\n",
    "    csv_reader = csv.reader(csvinput, delimiter='\\t')\n",
    "    # А теперь по строкам в файле\n",
    "    for line in csv_reader:\n",
    "        user = int(line[0]) \n",
    "        maxUserId = max(user,maxUserId)\n",
    "        # Разбираем идшки и маски друзей\n",
    "        for friendship in line[1].replace(\"{(\", \"\").replace(\")}\", \"\").split(\"),(\"):\n",
    "            parts=friendship.split(\",\")\n",
    "            # Записываем связь в массивы и двигаем указатель\n",
    "            formUser[current] = user\n",
    "            friend = int(parts[0])\n",
    "            toUser[current] = friend\n",
    "            maxUserId = max(friend,maxUserId)\n",
    "            current += 1\n",
    "            \n",
    "    # Не забываем закрыть файл\n",
    "    csvinput.close()\n",
    "    \n",
    "# Собственно из массивов создаем нашу матрицу\n",
    "fullMatrix = coo_matrix(\n",
    "    (data, (formUser, toUser)),\n",
    "    shape=(maxUserId + 1, maxUserId + 1)).tocsr()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В матрице три массива, соответственно легко померять сколько памяти она занимает"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "283631436\n"
     ]
    }
   ],
   "source": [
    "print fullMatrix.data.nbytes + fullMatrix.indptr.nbytes + fullMatrix.indices.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь аккуратно вычистим ненужное"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "del formUser\n",
    "del toUser\n",
    "del data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Матрицу надо развернуть. К счастью все уже украдено до нас и её можно просто транспонировать :). Главное не забыть перевести обрантно в csr формат (после транспонирования получим csc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reversedMatrix = scipy.transpose(fullMatrix).tocsr()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Есть развернутая матрица, проверим сколько занимает"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "283631436\n"
     ]
    }
   ],
   "source": [
    "print reversedMatrix.data.nbytes + reversedMatrix.indptr.nbytes + reversedMatrix.indices.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Итого - две матрицу в сумме 540Мб в памяти :). Как будем считать общих друзей? Умножением матриц!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "commonFriends = fullMatrix.dot(reversedMatrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Долговато, интересно, сколько получилось в памяти?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3387510156\n"
     ]
    }
   ],
   "source": [
    "print commonFriends.data.nbytes + commonFriends.indptr.nbytes + commonFriends.indices.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мда, 3 с лишним гигабайта, а в мониторе на процессе почти 5... На ваших 6Гб ноутах может и не пролезть...\n",
    "\n",
    "Эврика! Нам же нужно предиктить не для всех! Давайте отфильтруем только нужных :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Принцип 4\n",
    "\n",
    "__Фильтрую ненужное сразу.__\n",
    "\n",
    "### Применительно к нашей задаче\n",
    "\n",
    "* Считать общих друзей только для 1/11-й."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Попытка номер 3\n",
    "\n",
    "Фильтруем данные и пробуем построить прогноз."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Но сначала память подчистим\n",
    "del commonFriends \n",
    "\n",
    "# Забьем ненужное 0-ями\n",
    "for i in range(maxUserId + 1):\n",
    "    if i % 11 != 7:\n",
    "        ptr = fullMatrix.indptr[i]\n",
    "        ptr_next = fullMatrix.indptr[i+1]\n",
    "        if ptr != ptr_next:\n",
    "            fullMatrix.data[ptr:ptr_next].fill(0)\n",
    "            \n",
    "# Чтобы нули не мешались при умножении, вычистим их и подуменьшим матрицу\n",
    "fullMatrix.eliminate_zeros()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сколько получилось после фильтрации?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "85726554\n"
     ]
    }
   ],
   "source": [
    "print fullMatrix.data.nbytes + fullMatrix.indptr.nbytes + fullMatrix.indices.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "85Мб :) Другое дело. Теперь можно и умножать"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "commonFriends = fullMatrix.dot(reversedMatrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Заметно быстрее :) А по памяти что?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "350058222\n"
     ]
    }
   ],
   "source": [
    "print commonFriends.data.nbytes + commonFriends.indptr.nbytes + commonFriends.indices.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "350Мб, у вас тоже наверняка в память влезет :)\n",
    "\n",
    "### Генерируем прогноз\n",
    "\n",
    "Ну а теперь, давайте записывать прогноз."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "output = gzip.open( os.path.join(dataPath,\"prediction.gz\"), \"w\")\n",
    "writer = csv.writer(output, delimiter='\\t')\n",
    "\n",
    "for i in range(maxUserId + 1):\n",
    "    # Два указателя дают нам границы в которых лежат данные для этого i в матрице\n",
    "    ptr = commonFriends.indptr[i]\n",
    "    ptr_next = commonFriends.indptr[i+1] \n",
    "    # Если они не равны, значит данные есть и можно экспортировать\n",
    "    if ptr != ptr_next:\n",
    "        # Достаем счетчики общих друзей и создаем порядок на них от большего к меньшему\n",
    "        counts = commonFriends.data[ptr:ptr_next]\n",
    "        order = numpy.argsort(-counts)\n",
    "        \n",
    "        # Не забываем что из прогноза надо убрать себя и своих известных друзей\n",
    "        mineFriends = set(fullMatrix.indices[fullMatrix.indptr[i]:fullMatrix.indptr[i+1]])\n",
    "        mineFriends.add(i)\n",
    "        \n",
    "        # Достаем идшки друзей, сортируем, фильтруем, обрезаем и пишем\n",
    "        ids = commonFriends.indices[ptr:ptr_next]        \n",
    "        writer.writerow([i] + filter(lambda x: x not in mineFriends, ids[order]))      \n",
    "\n",
    "# Не забываем закрыть файл\n",
    "output.close()        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хм, как долго-то... И сколько получилось в итоге?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "182059146\n"
     ]
    }
   ],
   "source": [
    "print os.path.getsize(os.path.join(dataPath,\"prediction.gz\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мда, 182Мб, не влезет ни в какие лимиты. Снова применим _4-й принцип_ - надо рубить хвосты!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Попытка номер 4\n",
    "\n",
    "Уменьшаем объем результата"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "output = gzip.open( os.path.join(dataPath,\"prediction_short.gz\"), \"w\")\n",
    "writer = csv.writer(output, delimiter='\\t')\n",
    "\n",
    "for i in range(maxUserId + 1):\n",
    "    ptr = commonFriends.indptr[i]\n",
    "    ptr_next = commonFriends.indptr[i+1] \n",
    "    if ptr != ptr_next:\n",
    "        counts = commonFriends.data[ptr:ptr_next]\n",
    "        order = numpy.argsort(-counts)\n",
    "        mineFriends = set(fullMatrix.indices[fullMatrix.indptr[i]:fullMatrix.indptr[i+1]])\n",
    "        mineFriends.add(i)\n",
    "        ids = commonFriends.indices[ptr:ptr_next]   \n",
    "        # И собственно фильтр. 42\n",
    "        writer.writerow([i] + filter(lambda x: x not in mineFriends, ids[order])[:42])      \n",
    "\n",
    "# Не забываем закрыть файл\n",
    "output.close() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Гораздо быстрее! И сколько же там?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1471944\n"
     ]
    }
   ],
   "source": [
    "print os.path.getsize(os.path.join(dataPath,\"prediction_short.gz\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Полтора мегабайта! Первый сабмит готов! Что делать дальше?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Принцип 5\n",
    "\n",
    "__Слышишь тревожный шум вентилятора - сохраняйся__\n",
    "\n",
    "### Применительно к нашей задаче\n",
    "\n",
    "* Сохраним полученные результаты (граф, развернутый граф, счетчики общих друзей) в бинарном формате, чтобы не тратить время на чтение текстов.\n",
    "* Подготовим выборки для тренировочного и тестового множества, если хотим пробовать машинное обучений."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cохраняемся\n",
    "\n",
    "### Сначала данные по валидационному множеству"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "numpy.savez(os.path.join(dataPath, \"commonFriends_validation.npz\"),\n",
    "            data=commonFriends.data,\n",
    "            indices=commonFriends.indices,\n",
    "            indptr=commonFriends.indptr,\n",
    "            shape=commonFriends.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сколько занял файл?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "350058960\n"
     ]
    }
   ],
   "source": [
    "print os.path.getsize(os.path.join(dataPath,\"commonFriends_validation.npz\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Те же 350Мб. Как теперь его вчитать обратно?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "loaded = numpy.load(os.path.join(dataPath,\"commonFriends_validation.npz\"))\n",
    "commonFriends_validation = csr_matrix((loaded['data'], loaded['indices'], loaded['indptr']), shape=loaded['shape'])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Перввая фича для валидациионного множества есть."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Теперь трэйн и тест\n",
    "\n",
    "Но полную матрицу мы уже пофильтровали... Но у нас же есть транспонированная полная матрица, транспонируем её еще раз!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "train = scipy.transpose(reversedMatrix).tocsr()\n",
    "test = train.copy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь пофильтруем каждую"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in range(maxUserId + 1):\n",
    "    if i % 11 != 3:\n",
    "        ptr = train.indptr[i]\n",
    "        ptr_next = train.indptr[i+1]\n",
    "        if ptr != ptr_next:\n",
    "            train.data[ptr:ptr_next].fill(0)\n",
    "    if i % 11 != 9:\n",
    "        ptr = test.indptr[i]\n",
    "        ptr_next = test.indptr[i+1]\n",
    "        if ptr != ptr_next:\n",
    "            test.data[ptr:ptr_next].fill(0)\n",
    "\n",
    "train.eliminate_zeros()\n",
    "test.eliminate_zeros()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ок - теперь у нас есть разметка для тестового и тренировочного множества. Сохраним её"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "numpy.savez(os.path.join(dataPath, \"train_markup.npz\"),\n",
    "            data=train.data,\n",
    "            indices=train.indices,\n",
    "            indptr=train.indptr,\n",
    "            shape=train.shape)\n",
    "\n",
    "numpy.savez(os.path.join(dataPath, \"test_markup.npz\"),\n",
    "            data=test.data,\n",
    "            indices=test.indices,\n",
    "            indptr=test.indptr,\n",
    "            shape=test.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Да, известную часть графа по валидационному множеству тоже сохраним"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "numpy.savez(os.path.join(dataPath, \"validation_markup.npz\"),\n",
    "            data=fullMatrix.data,\n",
    "            indices=fullMatrix.indices,\n",
    "            indptr=fullMatrix.indptr,\n",
    "            shape=fullMatrix.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Сохраняем распаршенные графы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И обратную матрицу с полным графом тоже сохраним, чтобы не парсить снова тексты"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "numpy.savez(os.path.join(dataPath, \"reverseGraph.npz\"),\n",
    "            data=reversedMatrix.data,\n",
    "            indices=reversedMatrix.indices,\n",
    "            indptr=reversedMatrix.indptr,\n",
    "            shape=reversedMatrix.shape)\n",
    "\n",
    "validation_markup = fullMatrix\n",
    "fullMatrix = scipy.transpose(reversedMatrix).tocsr()\n",
    "\n",
    "numpy.savez(os.path.join(dataPath, \"fullGraph.npz\"),\n",
    "            data=fullMatrix.data,\n",
    "            indices=fullMatrix.indices,\n",
    "            indptr=fullMatrix.indptr,\n",
    "            shape=fullMatrix.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь подсчитаем общих друзей по тесту и трейну и сохраним их:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "trainCommon = train.dot(reversedMatrix)\n",
    "testCommon = test.dot(reversedMatrix)\n",
    "\n",
    "# Надоело копировать - заведи метод!\n",
    "numpy.savez(os.path.join(dataPath, \"commonFriends_train.npz\"),\n",
    "            data=trainCommon.data,\n",
    "            indices=trainCommon.indices,\n",
    "            indptr=trainCommon.indptr,\n",
    "            shape=trainCommon.shape)\n",
    "\n",
    "numpy.savez(os.path.join(dataPath, \"commonFriends_test.npz\"),\n",
    "            data=testCommon.data,\n",
    "            indices=testCommon.indices,\n",
    "            indptr=testCommon.indptr,\n",
    "            shape=testCommon.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сколько получилось в памяти?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "373562826\n",
      "371175918\n"
     ]
    }
   ],
   "source": [
    "print trainCommon.data.nbytes + trainCommon.indptr.nbytes + trainCommon.indices.nbytes\n",
    "print testCommon.data.nbytes + testCommon.indptr.nbytes + testCommon.indices.nbytes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хм, на 20Мб больше чем на валидационном множестве... Ну понятно, для них же связи не прятали так активно.. Надо иметь ввиду что наша тренировочная выборка получилась смещенной!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Итоги\n",
    "\n",
    "Итого, сейчас в памяти:\n",
    "* Полная и развернутая матрица графа.\n",
    "* Три частичных матрицы графа (3/11)\n",
    "* Три блока счетчиков общих друзей\n",
    "\n",
    "И монитор системы показывает почти 5Гб - на 6 гигах памяти уже есть риск уйти в своп :(\n",
    "\n",
    "## Принцип 6\n",
    "\n",
    "__Жадность фраера погубит.__\n",
    "\n",
    "### Применительно к нашей задаче\n",
    "\n",
    "* Держать в памяти только то, что нужно.\n",
    "* А раз уж мы в этом блокноте намусорили, надо его закрыть и начать готовить данные для машинного обучения в отдельном.\n",
    "\n",
    "# Главный принцип действительно больших данных\n",
    "\n",
    "__Разделяй и властвуй.__\n",
    "\n",
    "<img src=\"./images/MapReduceExplained.png\" />"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}