{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5a603968",
   "metadata": {},
   "source": [
    "(lab-search-performance)=\n",
    "\n",
    "# Lab: Performance\n",
    "\n",
    "- **This section is kept here for your reference**.\n",
    "\n",
    "In {ref}`sorting` we took advantage of a few ideas\n",
    "to show how to do basic\n",
    "benchmarking to compare the various approaches.\n",
    "\n",
    "- using randomly-generated data\n",
    "- making sure each algorithm is working with the same data\n",
    "- making sure that we try a range of sizes to observe the effects of scaling\n",
    "- using a timer with sufficiently high resolution (the `Stopwatch` gives\n",
    "  us measurements in milliseconds).\n",
    "\n",
    "In this lab, you get your chance to learn a bit more about performance\n",
    "by comparing *searches*.\n",
    "The art of benchmarking is\n",
    "something that is easy to learn but takes a lifetime to master (to borrow\n",
    "a phrase from the famous Othello board game).\n",
    "\n",
    "Most of the algorithms we cover in introductory courses tend to be *polynomial*\n",
    "in nature. That is, the execution time can be bounded by a polynomial function\n",
    "of the data size $n$. A more accurate measure may also include\n",
    "a logarithm. Examples\n",
    "include but are not limited to:\n",
    "\n",
    "- $O(1)$ is constant time,\n",
    "  characterized by a calculation with a limited number of steps.\n",
    "- $O(n)$ is linear time; often characterized by a single loop\n",
    "- $O(n^2)$ is the time squared; often characterized by a nested loop\n",
    "- $O(log\\ n)$ is logarithmic (base 2) time; often characterized by a loop\n",
    "  that repeatedly divides its work in half. The binary search is a well-known example.\n",
    "- $O(n\\ log\\ n)$ is an example of a hybrid. Perhaps there is an outer loop that\n",
    "  is linear and an inner loop that is logarithmic.\n",
    "\n",
    "And there are way more than these shown here. As you progress in computing, you'll\n",
    "come to know and appreciate these in greater detail.\n",
    "\n",
    "In this lab, we're going to look at a few different data structures and methods\n",
    "that perform searches on them and do *empirical* analysis to get an idea of how\n",
    "well each combination works. Contrasted with other labs where you had to write\n",
    "a lot of code, we're going to give you some code to do all of the needed work\n",
    "but ask you to write the code to\n",
    "do the actual analysis and produce a basic table.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4fb5162",
   "metadata": {},
   "source": "## The Experiments\n\nWe're going to measure the performance of data structures we have been learning\nabout (and *will* learn about, for lists and sets). For this lab, we'll focus on:\n\n- Integer arrays using {ref}`searching` and {ref}`binarysearching`\n- {ref}`list` of integers with linear searching\n- {ref}`sets` of integers; checking if an item is contained in the set\n\nIn the interest of fairness, we are only going to look at the time it takes\nto perform the various search operations. We're not going to count the time\nto randomly-generate the data and actually *build* the data structure. The\nreasoning is straightforward. We're interested in the search time, which is\ncompletely independent of other aspects that may be at play. We're not at all\nsaying that the other aspects are unimportant but want to keep the assignment\nfocus on search.\n\nThe experimental apparatus that we are constructing will do the following\nfor each of the cases:\n\n- create the data structure (e.g. new array, new list, new set)\n- use a random seed `seed`, initialize a random generator that will generate\n  `n` values.\n- insert the random values into the data structure .\n  For the case of sets, which eliminate duplicates, it is\n  entirely possible you will end up with a tiny fraction of a percent\n  fewer than `n` values.\n- to measure the performance of any given search method, we need to perform a\n  significant number of lookups (based on numbers in the random sequence) to\n  ensure that we get an accurate idea of the *average* lookup time in practice.\n  We'll call this parameter, `rep`. We will spread out the values looked for\n  by checking data elements that have indices at a regular interval throughout the array.\n  The separation is `m = n/rep` when `rep < n`. The separation is 1, and\n  we wrap around at the end of the array if `rep > n`.\n- We'll start a Stopwatch just before entering the loop to perform the lookups."
  },
  {
   "cell_type": "markdown",
   "id": "ffe4e8f0",
   "metadata": {},
   "source": "## Starter Project\n\nTo make your life easier, we have put together a project\nthat refers to all the code for all of the experiments you need\nto run. (That's right, we're giving you the code for the *experiments*,\nbut you're going to write\nsome code to run the various experiments and then run for varying sizes of `n`.)\nThe stub file is [performance_lab_stub/performance_lab.cs](https://github.com/mstbit/introcs-csharp-examples/blob/master/performance_lab_stub/performance_lab.cs).\n\nRecreate example project performance_lab_stub in your solution as performance_lab,\nso you have your own copy to modify. You can either\n\n- copy into the\n  lab project the files [sorting/sorting.cs](https://github.com/mstbit/introcs-csharp-examples/blob/master/sorting/sorting.cs),\n  [searching/searching.cs](https://github.com/mstbit/introcs-csharp-examples/blob/master/searching/searching.cs), and\n  [binary_searching/binary_searching.cs](https://github.com/mstbit/introcs-csharp-examples/blob/master/binary_searching/binary_searching.cs). *If* you copy them into the lab\n  project, *rename* the unused `Main` method from {file}`binary_searching.cs`\n  to something else (since Xamarin Studio allows only one `Main` method in a\n  project).\n- An alternative is to recreate their whole projects,\n  and *reference* them from the lab project.\n\nHere is the code for the first experiment, to test the performance of linear\nsearching on integer arrays:\n\n```{literalinclude} ../../examples/performance_lab_stub/performance_lab.cs\n:dedent: 6\n:end-before: chunk-experiment1-end\n:linenos: true\n:start-after: chunk-experiment1-begin\n```\n\nLet's take a quick look at how this experiment is constructed. We'll also take a\nlook at the other experiments but these will likely be presented in a bit\nless detail, except to highlight the differences:\n\n- On line 3, we create a `Stopwatch` instance. We'll be using this to do the timing.\n- On lines 4-5, we are creating the data to be searched. Because we have already\n  written this code in our sorting algorithms examples, we can refer to the\n  Sorting class code in {file}`sorting.cs`, as long as you made the lab project\n  able to reference it. We use the `Sorting` class name\n  to access the method `IntArrayGenerate()` within this class. We also take advantage\n  of this in the other experiments.\n- Line 6 converts the number of repetitions into the increment in index values for each\n  time.\n- Line 7 resets the stopwatch. It is not technically required; however, we tend to be\n  in the habit of doing it, because we sometimes reuse the same stopwatch and want\n  to make sure it is completely zeroed out. A call to `Reset()` ensures it is zero.\n- Line 8 actually starts the stopwatch. We are starting here as opposed to before line\n  4, because the random data generation has nothing to do with the actual searching of\n  the array data structure.\n- Lines 10 through 12 are searching `rep` times for an item already known to\n  be in the array.\n- Line 13 stops the stopwatch.\n- Line 14 returns the elapsed time in *milliseconds*\n  between the `Start()` and `Stop()` method calls,\n  which reflects the actual time of the experiment.\n\nEach of the other experiments is constructed similarly.\nFor linear search and binary search\nwe use the methods created earlier.\nFor the lists and the set we use the built-in `Contains`\nmethod to search.\nThe list and set are directly initialized in their constructors from the\narray data. (More on that in later chapters.)\n\nYou need to fill in the `Main` method.\nThe stub already has code to generate a random value for the `seed` for\nany run of the program. *Read* through to the end of the lab before\nstarting to code. A step-by-step sequence is suggested at the end.\n\n- Your code must parse command line `args` for the parameters `rep`\n  and *any number*\n  of values for `n`. For instance:\n\n  > mono PerformanceLab.exe 50000 1000 10000 100000\n\n  would generate the table shown below for 50000 repetitions\n  for each of the values of `n`: 1000,\n  10000, and 100000.\n\n- In the end you will want to run each experiment\n  for `rep` repetitions and iterate through each different value of `n`.\n\n- Present the result data in a nice printed right-justified table for\n  all values of n,\n  with a title including the number of repetitions. Print\n  something like the following, with the number of seconds calculated.\n\n  ```none\n  Times in seconds with 50000 repetitions\n         n    linear      list  binary     set\n      1000  ????.???  ????.???  ??.???  ??.???\n     10000  ????.???  ????.???  ??.???  ??.???\n    100000  ????.???  ????.???  ??.???  ??.???\n  ```\n\n  The table would be longer if more values of n were entered on the command line.\n  Note that the experiments return times in milliseconds, (1/1000 of a second)\n  while the table should print times in *seconds*.\n\n- Your final aim is to\n  show your TA or instructor the results of\n  a run with a table with at least three lines of data and with n\n  being successive powers of 10, and *non-zero entries everywhere*. *Read on*\n  for the major catch!\n\n  You will need to\n  *experiment* and adjust the repetitions and `n` choices.\n  In order to *get all perceptible values* (nonzero), you will need a\n  very large number of repetitions to work for the fastest searches.\n  Our choice of 50000 in the example is not appropriate with these `n` values.\n  The catch is that without further tweaking, you will only get nonzero\n  values for all the fastest searches if the slower ones take\n  *ridiculously long*.\n\n  Because the range of speeds is so enormous, make an accommodation with the\n  slow linear versions: If `rep >= 100` and `(long)n*rep >= 100000000`,\n  then, for the linear and list columns *only*, time with `rep2 = rep/100`\n  instead of `rep`,\n  and then compensate by multiplying the resulting time by `(double)rep/rep2`\n  to produce the final table value.\n  (This multiplier is not necessarily just 100, since the integer division creating\n  `rep2` may not be exact.)\n\nBefore making the modification for large numbers, be sure to test with\nsmall enough values (though some results will be 0).\nOnce again, you are encouraged to develop this is steps, for example:\n\n1. Make sure you can parse the command line parameters. In a testing version\n   write code to print out `rep`,\n   and *separate* code to print out all `n` values, for any number\n   of `n` values.\n2. Print out one *linear* test for `rep` and one value of `n`.\n3. Print out the results for all tests for `rep` and one value of `n`.\n   Keep `rep*n` small enough so the linear searches do not take too much time.\n4. Do all values of `n`.\n5. Make the printing be formatted as in the sample table.\n6. Add the modification for large `rep*n`.\n7. Experiment and get a table to show off!"
  }
 ],
 "metadata": {
  "jupytext": {
   "cell_metadata_filter": "-all",
   "main_language": "python",
   "notebook_metadata_filter": "-all"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}