Initial testing - 2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#lower bound: AM-LT problem\n",
    "def AM_LT (X, k, p):\n",
    "    H = []\n",
    "    tau = p*len(X)\n",
    "    #modify for AM_LT\n",
    "    tau = len(X) - tau + 1\n",
    "    N_1_H = 0\n",
    "    for x in X:\n",
    "        contains_x = False\n",
    "        for e_i in H:\n",
    "            if (e_i[0] == x):\n",
    "                e_i[1] += 1\n",
    "                N_1_H += 1\n",
    "                contains_x = True\n",
    "                break\n",
    "        if (contains_x == False):     \n",
    "            if (len(H) < k):\n",
    "                if (len(H)==0):\n",
    "                    H.insert (0, [x,1])\n",
    "                    N_1_H += 1\n",
    "                else:\n",
    "                    #insert (x,1) maintaining sorted order\n",
    "                    append = True\n",
    "                    for i in (range(0,len(H))):\n",
    "                        if (H[i][0] > x):\n",
    "                            H.insert (i, [x, 1])\n",
    "                            N_1_H += 1\n",
    "                            append = False\n",
    "                            break      \n",
    "                    if (append):\n",
    "                        H.append ([x,1])\n",
    "                        N_1_H += 1\n",
    "            elif (x < H[0][0]):\n",
    "                if (N_1_H < tau):\n",
    "                    H[len(H)-2][1] = H[len(H)-2][1] + H[len(H)-1][1]\n",
    "                    del H[len(H)-1]\n",
    "                    #insert (x,1)\n",
    "                    append = True\n",
    "                    for i in (range(0,len(H))):\n",
    "                        if (H[i][0] > x):\n",
    "                            H.insert (i, [x, 1])\n",
    "                            N_1_H += 1\n",
    "                            append = False\n",
    "                            break\n",
    "                    if (append):\n",
    "                        H.append ([x,1])\n",
    "                        N_1_H += 1\n",
    "            else:\n",
    "                for i in range(0,len(H)-1):\n",
    "                    if (H[len(H)-1-i][0]<x):\n",
    "                        H[len(H)-1-i][1] += 1\n",
    "                        N_1_H += 1\n",
    "                        break\n",
    "        N_2_H = N_1_H - H[0][1]\n",
    "        if(N_2_H>=tau):\n",
    "            count_to_delete = H[0][1]\n",
    "            del H[0]\n",
    "            N_1_H -= count_to_delete\n",
    "    return H[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#upper bound: AM-LEQ problem\n",
    "def AM_LEQ(X, k, p):\n",
    "    H = []\n",
    "    tau = p*len(X)\n",
    "    N_1_H = 0\n",
    "    for x in X:\n",
    "        contains_x = False\n",
    "        for e_i in H:\n",
    "            if (e_i[0] == x):\n",
    "                e_i[1] += 1\n",
    "                N_1_H += 1\n",
    "                contains_x = True\n",
    "                break\n",
    "        if (contains_x == False):     \n",
    "            if (len(H) < k):\n",
    "                if (len(H)==0):\n",
    "                    H.insert (0, [x,1])\n",
    "                    N_1_H += 1\n",
    "                else:\n",
    "                    #insert (x,1) maintaining sorted order\n",
    "                    append = True\n",
    "                    for i in (range(0,len(H))):\n",
    "                        if (H[i][0] < x):\n",
    "                            H.insert (i, [x, 1])\n",
    "                            N_1_H += 1\n",
    "                            append = False\n",
    "                            break      \n",
    "                    if (append):\n",
    "                        H.append ([x,1])\n",
    "                        N_1_H += 1\n",
    "            elif (x > H[0][0]):\n",
    "                if (N_1_H < tau):\n",
    "                    H[len(H)-2][1] = H[len(H)-2][1] + H[len(H)-1][1]\n",
    "                    del H[len(H)-1]\n",
    "                    #insert (x,1)\n",
    "                    append = True\n",
    "                    for i in (range(0,len(H))):\n",
    "                        if (H[i][0] < x):\n",
    "                            H.insert (i, [x, 1])\n",
    "                            N_1_H += 1\n",
    "                            append = False\n",
    "                            break\n",
    "                    if (append):\n",
    "                        H.append ([x,1])\n",
    "                        N_1_H += 1\n",
    "            else:\n",
    "                for i in range(0,len(H)-1):\n",
    "                    if (H[len(H)-1-i][0]>x):\n",
    "                        H[len(H)-1-i][1] += 1\n",
    "                        N_1_H += 1\n",
    "                        break\n",
    "        N_2_H = N_1_H - H[0][1]\n",
    "        if(N_2_H>=tau):\n",
    "            count_to_delete = H[0][1]\n",
    "            del H[0]\n",
    "            N_1_H -= count_to_delete\n",
    "    return H[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "#returns [t/f, chosen point] based on if the system guarante an approximation of the quantile within the maximum allowed relativ error\n",
    "def approximate_quantile (X, k, p, relative_error):\n",
    "    lower_bound = AM_LT (X, k, p)\n",
    "    upper_bound = AM_LEQ (X, k, p)\n",
    "    print (lower_bound)\n",
    "    print (upper_bound)\n",
    "    #choose the average\n",
    "    chosen_point = (int)((lower_bound + upper_bound)/2)\n",
    "    max_error = abs ((lower_bound - chosen_point)/lower_bound)\n",
    "    if (max_error <= relative_error):\n",
    "        return [True, chosen_point]\n",
    "    else:\n",
    "        return [False, chosen_point]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4976\n",
      "5001\n"
     ]
    }
   ],
   "source": [
    "#test on an example\n",
    "X = np.random.randint (0, 10000, (1,100000))[0]\n",
    "[can_compute, chosen_point] = approximate_quantile (X, 1000, .5, .1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4994.0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.median(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4988.5"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chosen_point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.random.randint (0, 10000, (1,100000))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#test lower and upper bound\n",
    "lower_bound = AM_LT (X, 1000, .5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4994"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lower_bound"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "upper_bound = AM_LEQ (X, 1000, .5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5004"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "upper_bound"
   ]
  },
  {
   "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
}