We will be timing some specific operations and measuring their performance
on the two stack implementations. We will then graph the performance as the data size
(n) increases.
We will use System.nanoTime() for time measurement.
System.nanoTime() returns the the number of nanoseconds that
have passed since midnight, Jan. 1, 1970. We use this method
to create a "stopwatch". To do this we:
- Call System.nanoTime() and save the result as
the start time.
- Run our tests.
- Call System.nanoTime() again and use the new reading
as the stop time.
The difference between the stop and start times will indicate how much time has
elapsed.
There are some problems that often occur trying to perform timing measurements
of algorithms:
- The timer resolution problem:
Modern computers are (thankfully) blindingly fast. But,
unfortunately, the timer mechanism and the operating systems
scheduler often take more time than the actual operation.
This means that many simple operations appear to take the
the same amount of time, when, in reality, they might just take
so little time that they are difficulty to accurately measure.
- The suspension problem:
Modern computers multitask, have complex memory
caching and virtual memory, and java runs in a virtual machine,
which sometimes optimizes programs in ways that interfere with the consistency
of time measurements.
All this means that our program may be "stopped" to perform another
program or task while in the middle of an important measurement.
Although it is great that the computers give the illusion of
several programs running at once, we would prefer that our
measurements not include the spent playing part of an MP3
or at least that this extra time is negligible compared to what
we are trying to measure.
For now we will design tests and collect multiple samples - we will
start the timer, perform one type of test many times (samples), and then stop the
timer. We will then know the total time taken for all the samples. We
can then divide the total time by the number of samples to determine the
average time per sample. Assuming that we have a large enough sample
size, this will be sufficient to overcome both problems.
- Read through (but don't yet implement) the following experiments:
- For each type of stack (MinSpaceStack and
DynamicStack), create 5,000 empty stacks. Tests
will be performed on all 5,000 stacks (we will have 5,000
samples per test).
Measure the average time taken to insert the n-th element
into a stack for n=1 to 100.
Create a line graph showing both sets of data:
- The horizontal (x) axis should be "n"
- The vertical axis (y) should be "time in ns"
- The title should be "Average time taken by n-th insertion"
- Be sure it's a line graph
- Include a legend that clearly indicates which line is
for the MinSpaceStack and which is for the
DynamicStack
Note 1: this is identical to one of the tests already included
in main of MinSizeStack.
Note 2: 5000 stacks depends on the memory available, the
version of the JVM you use, and many other factors.
If 5000 is too large for your test setup, decrease it
to a suitable value. If your setup can handle
more than 5000 stacks, feel free to increase it.
- For each type of stack (MinSpaceStack and
DynamicStack).
Measure (over 5000 samples):
Average time taken to create an empty stack and push 1 item onto it
Average time taken to create an empty stack and push 2 items onto it
...
Average time taken to create an empty stack and push 200 items onto it
So the data points for n=200 will indicate how long it takes
to push 200 items onto each stack.
Create a line graph showing both sets of data:
- The horizontal (x) axis should be "n"
- The vertical axis (y) should be "time in ns"
- The title should be "Average time taken to insert n items into a stack"
- Be sure it's a line graph
- Include a legend that clearly indicates which line is
for the MinSpaceStack and which is for the
DynamicStack
Note: These tests should not exceed memory availability on
any reasonable setup (do not use multiple stacks). Each
sample should create an empty stack and push the appropriate
number of items onto the stack.
- Based on your big-O analysis of the operations draw a sketch
of what you expect each graph to look like. You don't need to
include units, but estimate the shape of lines in each graph.
This will be included
with your homework. It is important that you do this before
implementing your tests and performing measurements.
- Implement the tests, perform the measurements, and produce the
required graphs.
- Answer the following questions:
- Did your empirical tests match what you expected from
analysis (sketches)?
- What, if anything, surprised you about the results?
- What are the advantages or disadvantages of each type of
stack?
- What are the advantages and disadvantages of each type of
analysis (empirical vs. analytic)?
- What big-O notation do the two lines in the second graph
match?
- If you were using a stack that would always contain between
1 and 1,000,000 items and want to minimize run-time, which is
preferable and why?
- Assuming your stack will always have a fixed maximum size (a
maximum n), does either version ensure that both
push and pop are O(1)? If not,
briefly explain how this could be done.