Next / Previous / Contents / TCC Help System / NM Tech homepage

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.

nSamplesMean
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()