[Python-checkins] python/nondist/sandbox/set settimings.py, NONE, 1.1

rhettinger@users.sourceforge.net rhettinger at users.sourceforge.net
Fri Jul 29 21:59:30 CEST 2005

Update of /cvsroot/python/python/nondist/sandbox/set
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv16836

Added Files:
Log Message:
Sandbox a benchmarking tool.

Compares relative performance of dicts vs sets.
Compares set() vs sets.Set().
Compares operations with various input types (sets, dicts, lists, uniqlists).
Also useful for comparing the Py2.4 version to the Py2.5 version.

--- NEW FILE: settimings.py ---
# timings of the new sets module

from timeit import Timer

setup = """
from random import randrange, seed
from sets import Set, ImmutableSet
n = 1000
a = [randrange(n) for i in xrange(n)]
b = [randrange(n) for i in xrange(n)]
seta = set(a)
Seta = Set(a)
setb = set(b)
dicta = dict.fromkeys(a, True)
dictb = dict.fromkeys(b, True)
NONE = None
TRUE = True
listseta = list(seta)
listsetb = list(setb)
dac = dicta.__contains__
dah = dicta.has_key
sac = seta.__contains__
sadd = seta.add
setc = set(seta)
for _ in setc: pass

If you don't already have a set,
   then passing the list form is always better or as good a making a temp set

If you do have a set or dict, then passing it is better or as good (w/in 20)% as a listset()

The w/20 is because looping over sets is slower than looping over a list.

Need more study on difference (first result) and sym_diff_up (second result)


set(a).binop(b)  vs set(a).binop(set(b))
   when =, it means internally b is first converted to a set if not already
   when <, it means the binop uses an algo that doesn't make a set first:
       diff, diff_up, inter, inter_up, union, union_up

set(a).binop(listsetb) vs set(a).binop(setb)
   when >>, it means that the list had to be coerced to a set first
       diff, sym_diff_up
   when >, it means that faster merge was used instead of iter
       union, union_up,

   when < 1/6, just means looping over dicts is slower than lists which is ok
       inter, inter_up, diff_up
   or something else
       sym_diff has ?flawed strategy of makingset and passing to sym_up
            B:makeset, A:sparseloop  A:contains  A-m:adds m:deletes
        vs. B:makeset, A:sparseloop  A:contains A-m:adds
                       B:sparseloop  B:contains B-m:adds
            delete B


# set_diff use of iterable vs set
stmts = [
    'setc.__contains__(None); list(setc)',
    'setc.discard(None); list(setc)',
    "'< means binop bypassed forcing to set'",


    "'>> due to set coercion; > merge faster than iter; < 1/6 dict looping is slow'",


    "for i in xrange(500): seta.add(i)",
    "for i in xrange(500): Seta.add(i)",
    "for i in xrange(500): dicta[i] = NONE",
    "for i in xrange(500): sadd(i)",
    "dict.fromkeys(b, TRUE)",


    "for i in xrange(200): i in seta",
    "for i in xrange(200): i in Seta",
    "for i in xrange(200): i in dicta",

    "for i in xrange(200): dah(i)",
    "for i in xrange(200): dac(i)",
    "for i in xrange(200): sac(i)",

    "for i in xrange(200): seta.discard(i)",
    "for i in xrange(20):  Seta.discard(i)",
    "for i in xrange(200): dicta.pop(i, NONE)",

# Repeat first five to check validity of timings

# Uniquification,

from time import time
import gc
start = time()

for stmt in stmts:
    print "%f\t%s" % (min(Timer(stmt, setup).repeat(9, 3500)), stmt)

end = time()
print end-start, "! total elapsed"

More information about the Python-checkins mailing list