theory_analysis.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib\n",
    "matplotlib.rcParams['text.usetex'] = True\n",
    "matplotlib.rc('pdf', fonttype=42)\n",
    "import itertools as it\n",
    "%matplotlib inline\n",
    "\n",
    "L = np.logspace(-5,0,100)\n",
    "# S = np.linspace(1,1000,100)\n",
    "# N = np.linspace(10,1010,, dtype=int)\n",
    "N = np.logspace(2,4,20)\n",
    "T = np.logspace(1,4,4)\n",
    "\n",
    "data = {'L':[],\n",
    "        'Linv':[],\n",
    "        'N':[],\n",
    "        'T':[],\n",
    "        'limit':[],\n",
    "        'term2':[],\n",
    "        'term3':[]\n",
    "       }\n",
    "for i, l in enumerate(L):\n",
    "    for j, n in enumerate(N):\n",
    "        for k, t in enumerate(T):\n",
    "            data['L'].append(l)\n",
    "            data['Linv'].append(1/l)\n",
    "            data['N'].append(int(n))\n",
    "            data['T'].append(t)\n",
    "            data['limit'] = n*t\n",
    "            data['term2'].append(np.log(1/n)/np.log(1-l))\n",
    "            data['term3'].append((l+n-1)/l)\n",
    "            data['dterm3_dL'] = (1-n)/(l**2)\n",
    "        \n",
    "df = pd.DataFrame.from_records(data)\n",
    "df['total'] = df['term3'] + df['term2'] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "h = plt.figure(figsize=(5,5))\n",
    "ax = h.add_subplot(111)\n",
    "sns.lineplot(data=df[['L','N','term3']].drop_duplicates(), \n",
    "             x = 'L',\n",
    "             y='term3',\n",
    "             hue='N',\n",
    "             linestyle='-'\n",
    "            )\n",
    "sns.lineplot(data=df, x = 'L', y='term2',hue='N', linestyle=':',legend=False)\n",
    "\n",
    "plt.legend(loc='lower right', title='N')\n",
    "# plot T lines\n",
    "i = 0\n",
    "for (t,n),dfg in df.loc[df.N==df.N.max()].groupby(['T','N']):\n",
    "    plt.text(s='NT, T={}'.format(int(t)),x = 1, y = n*t*1.2, \n",
    "#              bbox=dict(facecolor='white', edgecolor='w', alpha=0.5)\n",
    "            )\n",
    "    plt.plot([1, 1/t], [n*t, n*t], ':r')#, alpha=0.25 )\n",
    "    plt.plot([1/t, 1/t], [0, n*t], ':r')#, alpha=0.25 )\n",
    "    if i < 3:\n",
    "        plt.text(s='1/T',x = 1/t, y = 2 )\n",
    "    plt.plot(1/t, n*t, 'rx', label='t={},n={}'.format(t,n) )\n",
    "    i+=1\n",
    "    \n",
    "# Nmax = df.N.max()\n",
    "# # dRdL3 = (1-N)/(L**2)\n",
    "# Rsim = []\n",
    "# Rsim.append(df.loc[df.N==df.N.max()]['term3'].min())\n",
    "# l0 = L[0]\n",
    "# for l in L[1:]:\n",
    "#     Rsim.append(Rsim[-1]*(1-Nmax)/(l**2)*(l-l0))  \n",
    "#     l0 = l\n",
    "    \n",
    "# plt.plot(df.L,df.Linv**2,'--k')\n",
    "# plt.plot(df.L,df.Linv,'xb')\n",
    "plt.xlabel('$\\\\bar{L}$')\n",
    "plt.ylabel('')\n",
    "\n",
    "# plt.legend(['(L+N-1)/L','log(1/N)/log(1-L)'])\n",
    "plt.gca().set_xscale('log')\n",
    "plt.gca().invert_xaxis()\n",
    "plt.xticks([1,.1,.01,.001,.0001,0.00001]) #, ['10^0','10^-1','10^-2','10^-3',10^-4])\n",
    "plt.gca().set_yscale('log')\n",
    "\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.savefig('figs/linear_and_quad_growth_of_boolean_lex_running_time.pdf',dpi=200,bbox_inches='tight')\n",
    "plt.savefig('figs/linear_and_quad_growth_of_boolean_lex_running_time.png',dpi=200,bbox_inches='tight')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(df.Linv,df['term3'])\n",
    "plt.gca().set_yscale('log')\n",
    "plt.gca().set_xscale('log')\n",
    "plt.ylabel('Third term Eqn. 11')\n",
    "plt.xlabel('1/L')\n",
    "plt.savefig('figs/Linv_scaling.pdf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sns.histplot(\n",
    "#     data=df, x='L', y=\"N\", hue=\"total\" )\n",
    "from mpl_toolkits.mplot3d import axes3d, Axes3D #<-- Note the capitalization! \n",
    "import matplotlib.cm as cm\n",
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(1, 2, 1, projection='3d')\n",
    "ax.plot_trisurf(df.L, df.N, df.total, cmap=cm.jet, linewidth=0.2)\n",
    "ax.view_init(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# df['dRdL3'] = (1-df.N)/(df.L**2)\n",
    "plt.plot(df['L'], df['term3'].diff())\n",
    "plt.plot(df['L'], df['dterm3_dL'])\n",
    "plt.gca().set_yscale('log')\n",
    "plt.gca().set_xscale('log')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# df['L'] = df['L'].apply(int)\n",
    "# df['N'] = df['N'].apply(int)\n",
    "dfsq = df.pivot(index='L',columns='N')['total']\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib.colors import LogNorm\n",
    "sns.heatmap(dfsq, \n",
    "             norm=LogNorm(),\n",
    "            robust=True,\n",
    "#             yticklabels=[str(round(y,1)) for y in L],\n",
    "            yticklabels=20,\n",
    "#             xticklabels=0\n",
    "            )\n",
    "plt.gca().invert_yaxis()\n",
    "plt.savefig('figs/heatmap_growth_of_boolean_lex_running_time.pdf')\n",
    "# plt.gca().set_xscale('log')\n",
    "# plt.gca().set_yscale('log')\n",
    "# plt.yticks(ticks=L[::10],labels=[str(round(y,1)) for y in L[::10]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "plt.figure(figsize=(20,20))\n",
    "pf = np.linspace(0,1,101)\n",
    "\n",
    "for N in np.linspace(10,1000,901):\n",
    "    for pfi in pf:\n",
    "        plt.scatter(pfi,N,c=np.log(1/N)/np.log(pfi))\n",
    "plt.show()"
   ]
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}