spark/Median for RDDs, Datasets, and Dataframes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Median for RDDs, Datasets, and Dataframes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Getting `spark` up and running"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "143 new artifact(s)\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "143 new artifacts in macro\n",
      "143 new artifacts in runtime\n",
      "143 new artifacts in compile\n"
     ]
    },
    {
     "data": {
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "classpath.add(\n",
    "  \"org.apache.spark\" %% \"spark-core\" % \"2.0.2\",\n",
    "  \"org.apache.spark\" %% \"spark-sql\" % \"2.0.2\",\n",
    "  \"org.apache.spark\" %% \"spark-mllib\" % \"2.0.2\"\n",
    ");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[36morg.apache.spark.sql.{SparkSession, DataFrame, Dataset}\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import org.apache.spark.sql.{SparkSession, DataFrame, Dataset}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Using Spark's default log4j profile: org/apache/spark/log4j-defaults.properties\n",
      "17/08/03 23:24:04 INFO SparkContext: Running Spark version 2.0.2\n",
      "17/08/03 23:24:04 WARN NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where applicable\n",
      "17/08/03 23:24:04 INFO SecurityManager: Changing view acls to: amir.ziai\n",
      "17/08/03 23:24:04 INFO SecurityManager: Changing modify acls to: amir.ziai\n",
      "17/08/03 23:24:04 INFO SecurityManager: Changing view acls groups to: \n",
      "17/08/03 23:24:04 INFO SecurityManager: Changing modify acls groups to: \n",
      "17/08/03 23:24:04 INFO SecurityManager: SecurityManager: authentication disabled; ui acls disabled; users  with view permissions: Set(amir.ziai); groups with view permissions: Set(); users  with modify permissions: Set(amir.ziai); groups with modify permissions: Set()\n",
      "17/08/03 23:24:04 INFO Utils: Successfully started service 'sparkDriver' on port 53119.\n",
      "17/08/03 23:24:04 INFO SparkEnv: Registering MapOutputTracker\n",
      "17/08/03 23:24:04 INFO SparkEnv: Registering BlockManagerMaster\n",
      "17/08/03 23:24:04 INFO DiskBlockManager: Created local directory at /private/var/folders/8n/xtn3n2c50tbgtcr2pnh21dl4002rn2/T/blockmgr-ba771fc8-e73c-4b14-a159-787d0bb2a583\n",
      "17/08/03 23:24:04 INFO MemoryStore: MemoryStore started with capacity 2004.6 MB\n",
      "17/08/03 23:24:04 INFO SparkEnv: Registering OutputCommitCoordinator\n",
      "17/08/03 23:24:05 WARN Utils: Service 'SparkUI' could not bind on port 4040. Attempting port 4041.\n",
      "17/08/03 23:24:05 INFO Utils: Successfully started service 'SparkUI' on port 4041.\n",
      "17/08/03 23:24:05 INFO SparkUI: Bound SparkUI to 0.0.0.0, and started at http://192.168.0.4:4041\n",
      "17/08/03 23:24:05 INFO Executor: Starting executor ID driver on host localhost\n",
      "17/08/03 23:24:05 INFO Utils: Successfully started service 'org.apache.spark.network.netty.NettyBlockTransferService' on port 53120.\n",
      "17/08/03 23:24:05 INFO NettyBlockTransferService: Server created on 192.168.0.4:53120\n",
      "17/08/03 23:24:05 INFO BlockManagerMaster: Registering BlockManager BlockManagerId(driver, 192.168.0.4, 53120)\n",
      "17/08/03 23:24:05 INFO BlockManagerMasterEndpoint: Registering block manager 192.168.0.4:53120 with 2004.6 MB RAM, BlockManagerId(driver, 192.168.0.4, 53120)\n",
      "17/08/03 23:24:05 INFO BlockManagerMaster: Registered BlockManager BlockManagerId(driver, 192.168.0.4, 53120)\n",
      "17/08/03 23:24:05 WARN SparkContext: Use an existing SparkContext, some configuration may not take effect.\n",
      "17/08/03 23:24:05 INFO SharedState: Warehouse path is 'file:/Users/amir.ziai/Dropbox/jupyter/spark-warehouse'.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mspark\u001b[0m: \u001b[32mSparkSession\u001b[0m = org.apache.spark.sql.SparkSession@6bdd6f2a"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val spark = SparkSession.builder().master(\"local[*]\").getOrCreate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[36mspark.implicits._\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import spark.implicits._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating a `Dataset[Double]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mds1\u001b[0m: \u001b[32mDataset\u001b[0m[\u001b[32mDouble\u001b[0m] = [value: double]\n",
       "\u001b[36mds2\u001b[0m: \u001b[32mDataset\u001b[0m[\u001b[32mDouble\u001b[0m] = [value: double]\n",
       "\u001b[36mds3\u001b[0m: \u001b[32mDataset\u001b[0m[\u001b[32mDouble\u001b[0m] = [value: double]\n",
       "\u001b[36mds4\u001b[0m: \u001b[32mDataset\u001b[0m[\u001b[32mDouble\u001b[0m] = [value: double]\n",
       "\u001b[36mds5\u001b[0m: \u001b[32mDataset\u001b[0m[\u001b[32mDouble\u001b[0m] = [value: double]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val ds1 = spark.createDataset(Seq(1)).map(_.toDouble)\n",
    "val ds2 = spark.createDataset(Seq(1, 2)).map(_.toDouble)\n",
    "val ds3 = spark.createDataset(Seq(1, 2, 3)).map(_.toDouble)\n",
    "val ds4 = spark.createDataset(Seq(1, 2, 3, 4)).map(_.toDouble)\n",
    "val ds5 = spark.createDataset(Seq(1, 2, 3, 4, 5)).map(_.toDouble)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Dataset with odd number of elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmedian\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m3.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val Array(median) = ds5.stat.approxQuantile(\"value\",\n",
    "                                            Array(0.5),\n",
    "                                            relativeError = 0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is strange to me. My understanding is that `relativeError=0` is supposed to result in an exact median calculation. I will have to look into this further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmedian\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m4.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val Array(median) = ds5.stat.approxQuantile(\"value\",\n",
    "                                            Array(0.5),\n",
    "                                            relativeError = 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Dataset with even number of elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmedian\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m2.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val Array(median) = ds4.stat.approxQuantile(\"value\",\n",
    "                                            Array(0.5),\n",
    "                                            relativeError = 0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmedian\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m3.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val Array(median) = ds4.stat.approxQuantile(\"value\",\n",
    "                                            Array(0.5),\n",
    "                                            relativeError = 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Dataset of 1 element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmedian\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m1.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val Array(median) = ds1.stat.approxQuantile(\"value\",\n",
    "                                            Array(0.5),\n",
    "                                            relativeError = 0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmedian\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m1.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val Array(median) = ds1.stat.approxQuantile(\"value\",\n",
    "                                            Array(0.5),\n",
    "                                            relativeError = 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exact median calculation with RDDs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is not an efficient implementation but it works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[36morg.apache.spark.sql.Dataset\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import org.apache.spark.sql.Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mmedian\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def median(ds: Dataset[Double], column: String = \"value\"): Double = {\n",
    "    // Order the dataset\n",
    "    val dsOrdered = ds.orderBy(column)\n",
    "    val count = ds.count()\n",
    "    val dsDouble = dsOrdered.select(column).as[Double]\n",
    "    \n",
    "    // Zip the Dataset with index so we can lookup \n",
    "    // values by index\n",
    "    val dsWithIndex = dsDouble.rdd.zipWithIndex()\n",
    "    if (count % 2 == 0) {\n",
    "      val left = dsWithIndex\n",
    "        .filter(_._2 == count / 2 - 1)\n",
    "        .collect()(0)._1\n",
    "      val right = dsWithIndex\n",
    "        .filter(_._2 == count / 2)\n",
    "        .collect()(0)._1\n",
    "      (left + right) / 2\n",
    "    } else {\n",
    "      dsWithIndex.\n",
    "        filter(_._2 == count / 2)\n",
    "        .collect()(0)._1\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres37\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m3.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "median(ds5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres38\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m2.5\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "median(ds4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres39\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m1.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "median(ds1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres40\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m1.5\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "median(ds2)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Scala 2.11",
   "language": "scala211",
   "name": "scala211"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala211",
   "pygments_lexer": "scala",
   "version": "2.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}