tdigest.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPACkG0SjTlxUY5EZRNNC/J",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/microprediction/timeseries-notebooks/blob/main/tdigest.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ZfIwcM8FVikW"
      },
      "outputs": [],
      "source": [
        "!pip install tdigest"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "USE_HACK = True\n",
        "\n",
        "from tdigest import TDigest\n",
        "import numpy as np \n",
        "data = [1,2,3,4,5,6]*5000\n",
        "if USE_HACK:\n",
        "  data = [ d+np.random.randn()*0.000001 for d in data]\n",
        "t = TDigest()\n",
        "t.batch_update(data)\n",
        "t.percentile(1/6)\n",
        "t.cdf(1.2)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bzKNiXmHWdXZ",
        "outputId": "974ba28c-dc66-4e39-e699-d53ad70fe8fa"
      },
      "execution_count": 91,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0.16629666468785598"
            ]
          },
          "metadata": {},
          "execution_count": 91
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np \n",
        "\n",
        "def perc_plot(t):\n",
        "  xs = np.linspace(0.5,99.5,100)\n",
        "  print(xs)\n",
        "  ys = [ t.percentile(x) for x in xs ]\n",
        "  print(ys)\n",
        "  import matplotlib.pyplot as plt\n",
        "  plt.plot(xs,ys,'g+')\n",
        "\n",
        "def cdf_plot(t):\n",
        "  xs = np.linspace(0,7,100)\n",
        "  ys = [ t.cdf(x) for x in xs ]\n",
        "  print(list(zip(xs,ys)))\n",
        "  import matplotlib.pyplot as plt\n",
        "  plt.plot(xs,ys,'g+')"
      ],
      "metadata": {
        "id": "Cw2FG96ycKQl"
      },
      "execution_count": 92,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "cdf_plot(t)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 303
        },
        "id": "mG0GGvzfdPGo",
        "outputId": "31e4f855-8a64-42b4-d6dd-e5403043be3f"
      },
      "execution_count": 93,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[(0.0, 0.0), (0.0707070707070707, 0.0), (0.1414141414141414, 0.0), (0.2121212121212121, 0.0), (0.2828282828282828, 0.0), (0.35353535353535354, 0.0), (0.4242424242424242, 0.0), (0.4949494949494949, 0.0), (0.5656565656565656, 0.0), (0.6363636363636364, 0.0), (0.7070707070707071, 0.0), (0.7777777777777778, 0.0), (0.8484848484848484, 0.0), (0.9191919191919191, 0.0), (0.9898989898989898, 0.0), (1.0606060606060606, 0.16612474458591173), (1.1313131313131313, 0.16621195043472403), (1.202020202020202, 0.16629915628353634), (1.2727272727272727, 0.16638636213234861), (1.3434343434343434, 0.16647356798116092), (1.4141414141414141, 0.16656077382997322), (1.4848484848484849, 0.16664797967878553), (1.5555555555555556, 0.16666666666666666), (1.6262626262626263, 0.16666666666666666), (1.6969696969696968, 0.16666666666666666), (1.7676767676767675, 0.16666666666666666), (1.8383838383838382, 0.16666666666666666), (1.909090909090909, 0.16666666666666666), (1.9797979797979797, 0.16666666666666666), (2.0505050505050506, 0.3325841710570777), (2.121212121212121, 0.33270201676564687), (2.191919191919192, 0.3328198624742161), (2.2626262626262625, 0.33293770818278523), (2.333333333333333, 0.33305555389135444), (2.404040404040404, 0.33317339959992365), (2.4747474747474745, 0.3332912453084928), (2.5454545454545454, 0.3333333333333333), (2.616161616161616, 0.3333333333333333), (2.686868686868687, 0.3333333333333333), (2.7575757575757573, 0.3333333333333333), (2.8282828282828283, 0.3333333333333333), (2.898989898989899, 0.3333333333333333), (2.9696969696969697, 0.3333333333333333), (3.04040404040404, 0.4964917360360087), (3.111111111111111, 0.4970314690381338), (3.1818181818181817, 0.49757120204025884), (3.2525252525252526, 0.4981109350423839), (3.323232323232323, 0.49865066804450897), (3.3939393939393936, 0.49919040104663404), (3.4646464646464645, 0.4997301340487591), (3.535353535353535, 0.5), (3.606060606060606, 0.5), (3.6767676767676765, 0.5), (3.7474747474747474, 0.5), (3.818181818181818, 0.5), (3.888888888888889, 0.5), (3.9595959595959593, 0.5), (4.03030303030303, 0.6655237315469522), (4.101010101010101, 0.6656957862918967), (4.171717171717171, 0.6658678410368412), (4.242424242424242, 0.6660398957817856), (4.313131313131313, 0.66621195052673), (4.383838383838384, 0.6663840052716744), (4.454545454545454, 0.6665560600166189), (4.525252525252525, 0.6666666666666666), (4.595959595959596, 0.6666666666666666), (4.666666666666666, 0.6666666666666666), (4.737373737373737, 0.6666666666666666), (4.808080808080808, 0.6666666666666666), (4.878787878787879, 0.6666666666666666), (4.949494949494949, 0.6666666666666666), (5.02020202020202, 0.8323577388462239), (5.090909090909091, 0.8325015105943574), (5.161616161616162, 0.832645282342491), (5.232323232323232, 0.8327890540906246), (5.303030303030303, 0.8329328258387583), (5.373737373737374, 0.8330765975868919), (5.444444444444445, 0.8332203693350254), (5.515151515151515, 0.8333333333333334), (5.585858585858586, 0.8333333333333334), (5.656565656565657, 0.8333333333333334), (5.727272727272727, 0.8333333333333334), (5.797979797979798, 0.8333333333333334), (5.8686868686868685, 0.8333333333333334), (5.9393939393939394, 0.8333333333333334), (6.0101010101010095, 1), (6.08080808080808, 1), (6.151515151515151, 1), (6.222222222222222, 1), (6.292929292929292, 1), (6.363636363636363, 1), (6.434343434343434, 1), (6.505050505050505, 1), (6.575757575757575, 1), (6.646464646464646, 1), (6.717171717171717, 1), (6.787878787878787, 1), (6.858585858585858, 1), (6.929292929292929, 1), (7.0, 1)]\n"
          ]
        },
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ],
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAQ2klEQVR4nO3de4yld13H8feHXSqKSP/Y1ZBu69SkEBtipHNSMRh2ImK2aFoT0bQJeIk6JlKC0aj1EuaZGhMviVFjvYwFxQuUAmI2WKwGu/USiz3LTdqKWSq1W6td8IJItFa//jGnOp2eM3Ome2aec377fiVP+P3O75fn+bYhn3n6PZcnVYUkafE9q+8CJEmzYaBLUiMMdElqhIEuSY0w0CWpEYf7uvCRI0dqaWmpr8tL0kI6ffr0J6vq6Li13gJ9aWmJ4XDY1+UlaSEleWjSmi0XSWqEgS5JjTDQJakRBrokNcJAl6RG7BroSd6c5LEkH52wniS/kORMko8kuWr2ZUrSzrpT3VyN97JvZqpqxwN4OXAV8NEJ668C3gsEeCnw/t3OWVUsLy+XJM0KHXM13su+vQCGNSFXd71Dr6o/Af5phy3XAb85utY9wMVJXnBef2UkSXuWmuL30JMsAe+pqhePWXsP8JNV9Wej+fuAH6qqp31rKMkqsApw2WWXLT/00MTPx0vSrrpTHet3r/ddxnlZO75Gt9JNvT/J6aoajF2cdOu+9QCWmNxyeQ/wVVvm7wMGu53TloukWZqHNsvct1ym8Ahw6Zb5sdFrkqQDNItAPwl8y+jTLi8F/rWqHp3BeSVpamvH1+ZqvJd9s7JrDz3J24AV4Ajwj8Aa8GyAqvqVJAF+ETgBfBb49hrTP99uMBiUP84lSXuzUw99119brKobdlkv4HXPsDZJ0oz4TVFJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJE3Wnurkdj5tf8Kqql2N5ebkkzTc65nY8bn4hAIY1IVe9Q5ekRmQz8A/eYDCo4XDYy7UlTdad6li/e73vMvZs7fga3UrXdxn7LsnpqhqMXZx0677fhy0Xaf7NQ2vFlstTYctFktp3qOu6Xi68sbHRra6u9nJtSdNbWVqZ2/G4eevW19cf7bpuY9zaVD30JCeAnwcOAbdW1U9uW78MeAtw8WjPTVV1x07ntIcuSXu3Uw9915ZLkkPALcA1wJXADUmu3Lbtx4Dbq+olwPXAL51fyZKkvZqmh341cKaqHqyqx4HbgOu27SngC0bj5wN/P7sSJUnTmCbQLwEe3jI/O3ptqw54TZKzwB3A68edKMlqkmGS4blz555BuZKkSWb1KZcbgN+oqmPAq4DfSvK0c1fVRlUNqmpw9OjRGV1akgTTBfojwKVb5sdGr231HcDtAFX1F8BzgCOzKFCSNJ1pAv1e4Ioklye5iM03PU9u2/N3wCsAknwpm4FuT0WSDtCugV5VTwA3AncCD7D5aZb7ktyc5NrRtu8HvivJh4G3Ad9W03weUpI0M4en2TT6TPkd215745bx/cDLZluaJGkv/Oq/JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAlw5Yd6pbiLEWUFX1ciwvL5d0IaJjIcaaT8CwJuSqd+iS1IhsBv7BGwwGNRwOe7m2dNC6Ux3rd6/3XcaerB1fo1vp+i5D2yQ5XVWDsYuTbt33+7DlogvVPLRTbLksLmy5SFL7DnVd18uFNzY2utXV1V6uLfVtZWllIcaaP+vr6492Xbcxbs0euiQtkJ166LZcJKkRBrokNcJAl6RGGOiS1AgDXZIaMVWgJzmR5GNJziS5acKeb05yf5L7krx1tmVKknZzeLcNSQ4BtwCvBM4C9yY5WVX3b9lzBfDDwMuq6p+TfOF+FSxJGm+aO/SrgTNV9WBVPQ7cBly3bc93AbdU1T8DVNVjsy1TkrSbaQL9EuDhLfOzo9e2eiHwwiR/nuSeJCfGnSjJapJhkuG5c+eeWcWSpLFm9aboYeAKYAW4Afi1JBdv31RVG1U1qKrB0aNHZ3RpSRJMF+iPAJdumR8bvbbVWeBkVf1XVf0t8DdsBrwk6YBME+j3AlckuTzJRcD1wMlte36PzbtzkhxhswXz4AzrlCTtYtdAr6ongBuBO4EHgNur6r4kNye5drTtTuBTSe4H7gJ+oKo+tV9FS5Kezl9blKQF4q8tStIFwECXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXReM7lTX+1jaV1XVy7G8vFzSLKzdtTZxvnVMR+9j6XwBw5qQq96ha+Gt370+cb59TWqZP5+rhZf1UGs1dp719FXWWGvH1+hWur7L0ALb6edzDx90MdIsdKe6p9x9bw/uSUG+Nej7GEv7yZaLFlK30lFr9X9B+eR4+3z7WGqZga4Lxtrxtd7H0n6yh66F153qntKX3jrfviYtup166Aa6JC0QnykqSRcAA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSI6YK9CQnknwsyZkkN+2w7xuTVJKxvzMgSdo/uwZ6kkPALcA1wJXADUmuHLPvecAbgPfPukhJ0u6muUO/GjhTVQ9W1ePAbcB1Y/b9OPBTwH/MsD5J0pSmCfRLgIe3zM+OXvs/Sa4CLq2q39/pRElWkwyTDM+dO7fnYiVJk533m6JJngX8LPD9u+2tqo2qGlTV4OjRo+d7aUnSFtME+iPApVvmx0avPel5wIuBU0k+AbwUOOkbo5J0sKYJ9HuBK5JcnuQi4Hrg5JOLVfWvVXWkqpaqagm4B7i2qnwckSQdoF0DvaqeAG4E7gQeAG6vqvuS3Jzk2v0uUJI0ncPTbKqqO4A7tr32xgl7V86/LEnSXvlNUUlqhIEuSY0w0CWpEQa6JDXCQNdY3alu4nzexpJGqqqXY3l5uTS/6Jg4n7exdCEBhjUhV71Dl6RGZDPwD95gMKjh0C+TzpPuVMf63et9l7Fna8fX6Fa6vsuQDkSS01U1/qdVJt267/dhy2W+2XKR5hO2XCSpfYe6ruvlwhsbG93q6mov19Z0VpZWJs7nbSxdKNbX1x/tum5j3Jo9dElaIDv10G25SFIjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqxFSBnuREko8lOZPkpjHr35fk/iQfSfK+JF88+1IlSTvZNdCTHAJuAa4BrgRuSHLltm0fBAZV9WXAO4GfnnWhkqSdTXOHfjVwpqoerKrHgduA67ZuqKq7quqzo+k9wLHZlilJ2s00gX4J8PCW+dnRa5N8B/DecQtJVpMMkwzPnTs3fZWSpF3N9E3RJK8BBsDPjFuvqo2qGlTV4OjRo7O8tCRd8A5PsecR4NIt82Oj154iydcAPwocr6r/nE15kqRpTXOHfi9wRZLLk1wEXA+c3LohyUuAXwWurarHZl+mJGk3uwZ6VT0B3AjcCTwA3F5V9yW5Ocm1o20/A3w+8I4kH0pycsLpLmjdqW7seKe1vsaSFlBV9XIsLy/XhYaOseOd1voaS5pPwLAm5KrfFJWkRmQz8A/eYDCo4XDYy7UPUneqY/3u9b7L2LO142t0K13fZUjaJsnpqhqMXZx0677fhy0XWy6S9g5bLpLUvkNd1/Vy4Y2NjW51dbWXa/dpZWll7Hintb7GkubP+vr6o13XbYxbs4cuSQtkpx66LRdJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJasRUgZ7kRJKPJTmT5KYx65+T5O2j9fcnWZp1oVt1p7pdx9PuO8ixJO2rqtrxAA4BHwe+BLgI+DBw5bY93wP8ymh8PfD23c67vLxczxQdu46n3XeQY0k6X8CwJuTqNHfoVwNnqurBqnocuA24btue64C3jMbvBF6RJOfzh0aStDfZDPwdNiSvBk5U1XeO5q8FvqKqbtyy56OjPWdH84+P9nxy27lWgVWAyy67bPmhhx6autDuVMf63etT759Ha8fX6Fa6vsuQtMCSnK6qwdjFSbfuTx7Aq4Fbt8xfC/zitj0fBY5tmX8cOLLTeW25SNLecZ4tl0eAS7fMj41eG7snyWHg+cCnpvlrI0majWkC/V7giiSXJ7mIzTc9T27bcxL41tH41cAfj/6S7Iu142u7jqfdd5BjSdpPu/bQAZK8Cvg5Nj/x8uaq+okkN7N5638yyXOA3wJeAvwTcH1VPbjTOQeDQQ2Hw/P+B5CkC8lOPfTD05ygqu4A7tj22hu3jP8D+KbzKVKSdH78pqgkNcJAl6RGGOiS1AgDXZIaMdWnXPblwsk5YPqvij7VEeCTu+6aH4tU7yLVCotV7yLVCotV7yLVCudX7xdX1dFxC70F+vlIMpz0sZ15tEj1LlKtsFj1LlKtsFj1LlKtsH/12nKRpEYY6JLUiEUN9I2+C9ijRap3kWqFxap3kWqFxap3kWqFfap3IXvokqSnW9Q7dEnSNga6JDVi4QJ9twdWz5Mkb07y2OiJTnMtyaVJ7kpyf5L7kryh75omSfKcJH+Z5MOjWhfiUVZJDiX5YJL39F3LTpJ8IslfJflQkrn/SdQkFyd5Z5K/TvJAkq/su6Zxkrxo9O/0yePTSb53ptdYpB56kkPA3wCvBM6y+VvtN1TV/b0WNkGSlwOfAX6zql7cdz07SfIC4AVV9YEkzwNOA98wj/9uR8+rfW5VfSbJs4E/A95QVff0XNqOknwfMAC+oKq+vu96JknyCWBQ2x4hOa+SvAX406q6dfTMhs+rqn/pu66djLLsETYf1flMv2D5NIt2hz7NA6vnRlX9CZu/Dz/3qurRqvrAaPxvwAPAJf1WNd7oSVyfGU2fPTrm+s4kyTHg64Bb+66lJUmeD7wceBNAVT0+72E+8grg47MMc1i8QL8EeHjL/CxzGjqLLMkSmw8reX+/lUw2al98CHgM+KOqmttaR34O+EHgf/ouZAoF/GGS06MHu8+zy4FzwK+P2lm3Jnlu30VN4XrgbbM+6aIFuvZZks8H3gV8b1V9uu96Jqmq/66qL2fzGbdXJ5nbllaSrwceq6rTfdcypa+qqquAa4DXjVqH8+owcBXwy1X1EuDfgXl/b+0i4FrgHbM+96IF+jQPrNYzNOpHvwv4nar63b7rmcboP6/vAk70XcsOXgZcO+pN3wZ8dZLf7rekyarqkdH/Pga8m81W57w6C5zd8l9o72Qz4OfZNcAHquofZ33iRQv0aR5YrWdg9Ebjm4AHqupn+65nJ0mOJrl4NP5cNt8k/+t+q5qsqn64qo5V1RKb/5/946p6Tc9ljZXkuaM3xRm1Lr4WmNtPaVXVPwAPJ3nR6KVXAHP3Rv42N7AP7RaY8pmi86KqnkhyI3An///A6vt6LmuiJG8DVoAjSc4Ca1X1pn6rmuhlwGuBvxr1pgF+ZPQ82XnzAuAto08KPAu4varm+qOAC+SLgHdv/n3nMPDWqvqDfkva1euB3xnd5D0IfHvP9Uw0+iP5SuC79+X8i/SxRUnSZIvWcpEkTWCgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEb8LyT3q/7D6kD7AAAAAElFTkSuQmCC\n"
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    }
  ]
}