{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ab5cd7d1-1a57-46fc-8282-dae0a6cc2944",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import random\n",
    "import pandas as pd\n",
    "import itertools\n",
    "from joblib import Parallel, delayed\n",
    "import os.path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3d1ad0b9-f6a8-4e98-84aa-6e02e4279954",
   "metadata": {},
   "outputs": [],
   "source": [
    "SEED = 42\n",
    "np.random.seed(SEED)\n",
    "random.seed(SEED)\n",
    "\n",
    "ZIPF_CONSTANT = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5a27d416-8f98-4814-af9e-6c6bef95f4ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def eta_star(db_object_count, c_f, cache_sz, c_delta, lambda_vals):\n",
    "    num = (db_object_count * c_f - cache_sz * c_delta)\n",
    "    denom = np.sum(1.0/lambda_vals)\n",
    "    return max(0, num/denom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6276a9ce-f839-4fe6-90f2-2195cf065fc8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def h_i_star(c_f, eta, lambda_vals, c_delta):\n",
    "    optimized_hitrate = (c_f - (eta/lambda_vals)) / c_delta\n",
    "    return optimized_hitrate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "dcd31a8c-6864-4b9a-8bb3-998f0c32baf6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_index_of_furthest_hitrate_from_boundary(hitrates):\n",
    "    lower_bound_violation =  hitrates[(hitrates < 0)]\n",
    "    upper_bound_violation = hitrates[(hitrates > 1)]\n",
    "    smallest_delta = np.abs(np.min(lower_bound_violation))\n",
    "    biggest_delta = np.max(upper_bound_violation) - 1\n",
    "    if smallest_delta > biggest_delta:\n",
    "        index = np.where(hitrates == np.min(local_hitrates))[0][0]\n",
    "        return index\n",
    "    else:\n",
    "        \n",
    "        index = np.where(hitrates == np.max(local_hitrates))[0][0]\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9d774304-ae68-43b3-a76a-e970c06c5236",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_index_of_furthest_hitrate_from_boundary(hitrates):\n",
    "    outside_bounds = (hitrates < 0) | (hitrates > 1)\n",
    "    distances = np.where(outside_bounds, np.maximum(np.abs(hitrates - 0), np.abs(hitrates - 1)), -np.inf)\n",
    "    index = np.argmax(distances)\n",
    "    return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "0e21c26f-058a-4e56-a5ad-1c47bf28656c",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def optimize_hitrates(db_object_count, cache_size, c_f, c_delta, lambda_vals):\n",
    "    optimized_hitrates = np.zeros(db_object_count)\n",
    "    current_db_object_count = db_object_count\n",
    "    current_cache_size = cache_size\n",
    "    \n",
    "    differenc_set = np.arange(db_object_count)\n",
    "    fix_i = []\n",
    "    while True:\n",
    "        if current_db_object_count == 0:\n",
    "            if current_cache_size > 0:\n",
    "                # print(\"Re-optimize objects with optimal hitrate of 0.\")\n",
    "                differenc_set = np.where(optimized_hitrates == 0)[0]\n",
    "                fix_i = np.setdiff1d(np.arange(db_object_count), differenc_set).tolist()\n",
    "                current_db_object_count = len(differenc_set)\n",
    "                continue\n",
    "            else:\n",
    "                # print(\"Stop optimization.\")\n",
    "                optimized_hitrates[differenc_set] = 0\n",
    "                break\n",
    "        \n",
    "        eta = eta_star(current_db_object_count, c_f, current_cache_size, c_delta, lambda_vals[differenc_set])\n",
    "        optimized_hitrates[differenc_set] = h_i_star(c_f, eta, lambda_vals[differenc_set], c_delta)\n",
    "\n",
    "        if eta < 0:\n",
    "            # print(\"eta was negative.\")\n",
    "            current_cache_size = current_db_object_count * c_f / c_delta  # Adjust cache size for next iteration\n",
    "            continue\n",
    "        \n",
    "        if len((optimized_hitrates[differenc_set])[((optimized_hitrates[differenc_set]) < 0) | ((optimized_hitrates[differenc_set])> 1)]) == 0:\n",
    "            # print(\"All values optimized.\")\n",
    "            break\n",
    "        \n",
    "        max_outbound_index = get_index_of_furthest_hitrate_from_boundary(optimized_hitrates)\n",
    "        fix_i.append(max_outbound_index)\n",
    "        differenc_set = np.setdiff1d(np.arange(db_object_count), fix_i)\n",
    "    \n",
    "        old_hitrate = optimized_hitrates[max_outbound_index]\n",
    "        optimized_hitrates[max_outbound_index] = (1 if optimized_hitrates[max_outbound_index] > 1 else 0)\n",
    "        \n",
    "        current_db_object_count -= 1\n",
    "        current_cache_size -= optimized_hitrates[max_outbound_index]\n",
    "    return optimized_hitrates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b6bf3329-3a63-4807-ab8b-8a54f824f47e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def objective_function(optimized_hitrates, c_f, c_delta, lambda_vals):\n",
    "    return np.sum(lambda_vals*(1-optimized_hitrates)*c_f+0.5*np.power(optimized_hitrates,2)*c_delta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a289bb1a-0385-4835-bc92-88304c1834df",
   "metadata": {},
   "outputs": [],
   "source": [
    "def optimize_ttl(optimized_hitrates, lambda_vals):\n",
    "    result = []\n",
    "    for i in range(len(lambda_vals)):\n",
    "        if optimized_hitrates[i] < 1:\n",
    "            result.append(-1 / lambda_vals[i] * np.log(1 - optimized_hitrates[i]))\n",
    "        else:\n",
    "            result.append(np.inf)\n",
    "    # ti_values = np.where(\n",
    "    #     optimized_hitrates < 1,\n",
    "    #     -1 / lambda_vals * np.log(1 - optimized_hitrates),\n",
    "    #     np.inf\n",
    "    # )\n",
    "    \n",
    "    return np.array(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "bd4536e9-273b-4f49-b06c-2f00605e0f7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the task to be parallelized\n",
    "def grid_search_task(db_object_count, cache_size, c_f, c_delta):\n",
    "    if db_object_count < cache_size:\n",
    "        return None  # Skip this combination if db_object_count < cache_size\n",
    "    \n",
    "    # Generate lambda_vals\n",
    "    lambda_vals = np.array([np.random.zipf(ZIPF_CONSTANT) for _ in np.arange(1, db_object_count + 1, 1)])\n",
    "    \n",
    "    # Call the optimization function\n",
    "    optimized_hitrates = optimize_hitrates(db_object_count, cache_size, c_f, c_delta, lambda_vals)\n",
    "\n",
    "    optimized_ttl = optimize_ttl(optimized_hitrates, lambda_vals)\n",
    "    \n",
    "    # Compute the objective function\n",
    "    objective = objective_function(optimized_hitrates, c_f, c_delta, lambda_vals)\n",
    "\n",
    "    return (objective, optimized_ttl, db_object_count, cache_size, c_f, c_delta, optimized_hitrates)\n",
    "\n",
    "# Perform grid search with parallelization and tqdm progress bar\n",
    "def grid_search(db_object_counts, cache_sizes, c_f_values, c_delta_values):\n",
    "    results = []  # List to collect the results (objective, parameters)\n",
    "    total_combinations = len(db_object_counts) * len(cache_sizes) * len(c_f_values) * len(c_delta_values)\n",
    "    \n",
    "    # Use Parallel from joblib to parallelize the grid search\n",
    "    task_results = Parallel(n_jobs=-1, verbose=1)(\n",
    "        delayed(grid_search_task)(db_object_count, cache_size, c_f, c_delta)\n",
    "        for db_object_count, cache_size, c_f, c_delta in itertools.product(db_object_counts, cache_sizes, c_f_values, c_delta_values)\n",
    "    )\n",
    "\n",
    "    # Collect valid results\n",
    "    for result in task_results:\n",
    "        if result is not None:\n",
    "            results.append(result)\n",
    "    \n",
    "    # Convert the results into a pandas DataFrame\n",
    "    df = pd.DataFrame(results, columns=[\"Objective\", \"Optimal TTL\", \"db_object_count\", \"cache_size\", \"c_f (Miss Cost)\", \"c_delta (Refresh Cost)\", \"optimized_hitrates\"])\n",
    "    \n",
    "    return df\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "a92c6772-6609-41a8-a3d1-4d640b69a864",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[Parallel(n_jobs=-1)]: Using backend LokyBackend with 12 concurrent workers.\n",
      "[Parallel(n_jobs=-1)]: Done  26 tasks      | elapsed:    0.4s\n",
      "[Parallel(n_jobs=-1)]: Done 1420 tasks      | elapsed:    0.7s\n",
      "[Parallel(n_jobs=-1)]: Done 64152 out of 64152 | elapsed:  1.4min finished\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 42 s, sys: 731 ms, total: 42.7 s\n",
      "Wall time: 2min 5s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "# Define the grid search space\n",
    "test_ratios = np.array([0.1, 0.2, 0.5, 0.7, 1, 1.5, 2, 5, 10])\n",
    "db_object_count_values = np.round(np.array([10, 15, 30, 100, 200, 500]))\n",
    "cache_size_values = np.unique(np.round(np.array([db_object_count_values * i for i in test_ratios]).flatten()))\n",
    "c_f_values = np.array([0.1, 0.2, 0.5, 0.7, 1, 1.5, 2, 5, 10])\n",
    "c_delta_values = np.unique(np.array([c_f_values * i for i in test_ratios]).flatten())\n",
    "\n",
    "objective_result_file = \"./objective_grid-search_multi-core.csv\"\n",
    "\n",
    "results_df = None\n",
    "if not os.path.isfile(objective_result_file):\n",
    "    # Call the grid search function\n",
    "    results_df = grid_search(db_object_count_values, cache_size_values, c_f_values, c_delta_values)\n",
    "    results_df.to_csv(objective_result_file,index=False)\n",
    "else:\n",
    "    results_df = pd.read_csv(objective_result_file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "e79e6ed1-d6a5-4b04-a2b2-b3f0984e0fbe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best Result:\n",
      "Objective                                                              0.05\n",
      "Optimal TTL               [inf, inf, inf, inf, inf, inf, inf, inf, inf, ...\n",
      "db_object_count                                                          10\n",
      "cache_size                                                             10.0\n",
      "c_f (Miss Cost)                                                         0.7\n",
      "c_delta (Refresh Cost)                                                 0.01\n",
      "optimized_hitrates        [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, ...\n",
      "Name: 2376, dtype: object\n"
     ]
    }
   ],
   "source": [
    "# After performing the grid search and obtaining the DataFrame 'results_df'\n",
    "best_row = results_df.loc[results_df['Objective'].idxmin()]\n",
    "\n",
    "# Display the best row\n",
    "print(\"Best Result:\")\n",
    "print(best_row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "95af94b4-05c0-488c-9561-50fc4e7cc3d4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.049999999999999996,\n",
       " array([inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]),\n",
       " 10,\n",
       " 10,\n",
       " 1.5,\n",
       " 0.01,\n",
       " array([1., 1., 1., 1., 1., 1., 1., 1., 1., 1.]))"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid_search_task(10, 10, 1.5, 0.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20c943b4-b32b-4294-949b-0f3abe2fb97a",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "graphs",
   "language": "python",
   "name": "graphs"
  },
  "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.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
