## 6. Performance testing

To test whether the implementation gives ```O(log n)``` performance, script `bigotest` generates random floating-point values, then searches for a given number of them, and accumulates statistics on the number of comparisons per search.

Here is the raw data. For each `n`, five runs were made. The last column shows the mean of the five runs.

`n`SamplesMean
1e423.426.526.226.125.125.46
1e531.830.732.733.431.031.92
1e641.039.736.436.138.338.30
2e639.338.340.143.140.440.24
4e641.041.242.841.444.942.26

Here is a plot of the mean number of comparisons as a function of the common log of `n`.

Here is the `bigotest` script.

bigotest
```#!/usr/bin/env python
#================================================================
# bigotest: Test that pyskip has O(log n) time complexity
#--
# Command line arguments:
#   bigotest [N]
# where N is the number of floats to generate, default DEFAULT_N.
#----------------------------------------------------------------

# - - - - -   I m p o r t s

from __future__ import print_function
import sys
import pyskip
import random

# - - - - -   M a n i f e s t   c o n s t a n t s

DEFAULT_N = 10**6          # Default number of items
N_SAMPLES = 100            # How many lookups we try

# - - - - -   m a i n

def main():
"""Main program.

[ sys.stdout  +:=  statistics on number of elements and number
of compares per lookup on a set of HOW_MANY random floats ]
"""
#-- 1
# [ if there is one positive float argument ->
#     n  :=  int(that argument)
#   else if there are no arguments->
#     n  :=  DEFAULT_N
#   else ->
#     sys.stderr  +:=  error message
#     stop execution ]
n = checkArgs()

#-- 2
# [ skip  :=  a new pyskip.SkipList instance that allows duplicates
#       and has no key or compare function and is optimized for at
#       least n elements ]
skip = pyskip.SkipList(allowDups=1, count=n*4)

#-- 3
# [ skip  +:=  HOW_MANY uniform random floats ]
#   sampleList  :=  N_SAMPLES of those random floats ]
for k in range(n-N_SAMPLES):
skip.insert(random.random())

sampleList = []
for k in range(N_SAMPLES):
sample = random.random()
sampleList.append(sample)
skip.insert(sample)

#-- 4
# [ sys.stdout  +:=  statistics on the number of compares required
#       to look up each element of sampleList once ]
oldCompares = skip.nCompares
for sample in sampleList:
if sample not in skip:
print("Failed to find value {0:.5f}!".format(sample))
delta = skip.nCompares - oldCompares
print("Average of {0} random lookups out of {1} total "
"elements:".format(N_SAMPLES, len(skip)))
print("{0:.1f} compares per lookup.".format(float(delta)/N_SAMPLES))

# - - -   c h e c k A r g s

def checkArgs():
'''General command line argument processing.

[ if there is one positive float argument ->
return int(that argument)
else if there are no arguments->
return DEFAULT_N
else ->
sys.stderr  +:=  error message
stop execution ]
'''
#-- 1
argList = sys.argv[1:]

#-- 2
if len(argList) == 0:
return DEFAULT_N

#-- 3
try:
n = int(float(argList[0]))
except ValueError:
fatal("The argument must be a positive integer.")

#-- 4
if n < N_SAMPLES:
fatal("The argument must be at least {0}.".format(N_SAMPLES))

return n

# - - -   f a t a l

def fatal(*L):
'''Print a message and terminate.

[ L is a list of strings ->
sys.stderr  +:=  concatenated elements of L
stop execution ]
'''
print(''.join(L), file=sys.stderr)
sys.exit(1)

# - - -   r e p o r t

def report(skip, label):
'''Display accumulated statistics.
'''
print("=== {0}".format(label))
print("  {0:9d} elements.".format(len(skip)))

# - - - - -   E p i l o g u e

if __name__ == "__main__":
main()
```