How to represent sets

Anton Vredegoor anton at vredegoor.doge.nl
Sun Sep 15 11:17:08 CEST 2002


On Sun, 15 Sep 2002 00:31:48 -0700, "James J. Besemer"
<jb at cascade-sys.com> wrote:

>For dense sets isomorphic with integers, the long integer implementation 
>probably will be superior.
>
>For other, more general applications the dictionary approach may be better.

My script is not yet fully optimized, I just made some minor tweaks 
(the new version is at the same adress as before)
and there's some test output below.

For somewhat longer strings Set loads faster but if there are a lot of
operations on the sets, set is faster. For some other cases see below.

Could someone please check these results? It could be a programming
error since I am still tweaking the script.

from sets import Set
from universe import set
from time import time

def test():
    n = 100
    k = 10000
    r1 = [(i,j) for i in range(n) for j in range(n)]
    r2 = [(i,j) for i in range(n) for j in range(n-1,-1,-1)]
    t = time()
    S1 = Set(r1)
    S2 = Set(r2)
    for i in range(k):
        S3 = S1-S2
    print time()-t
    print "S finished"    
    t = time()
    s1 = set(r1)
    s2 = set(r2)
    for i in range(k):
        s3 = s1-s2
    print time()-t
    print "s finished"
    print 

if __name__=='__main__':
    test()

>d:\python22\pythonw -u test.py
92.5499999523
S finished
0.44000005722
s finished

from sets import Set
from universe import set
from time import time

def test():
    n = 100000
    k = 1000
    r1 = [i for i in range(n)]
    r2 = [i for i in range(0,n,2)]
    t = time()
    S1 = Set(r1)
    S2 = Set(r2)
    for i in range(k):
        S3 = S1-S2
    print time()-t
    print "S finished"    
    t = time()
    s1 = set(r1)
    s2 = set(r2)
    for i in range(k):
        s3 = s1-s2
    print time()-t
    print "s finished"
    print 

if __name__=='__main__':
    test()

>d:\python22\pythonw -u test2.py
104.090000033
S finished
2.58000004292
s finished




More information about the Python-list mailing list