Testing for membership speed

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • Guest's Avatar
    #1

    Testing for membership speed

    I just ran this stuff for my own knowledge. Though it might be
    useful to some other people to know and maybe spark a discussion.

    I needed a fast way to test for membership, so naturally the
    choices were the builtin containers: lists, dictionaries, and
    tuples. The following is the test code and results:

    import timeit

    lst_i=timeit.Ti mer('random.ran drange(10000) in l','import
    random; l=range(10000)' )
    dct_i=timeit.Ti mer('l.has_key( random.randrang e(10000))','imp ort
    random; l=dict([(i,None) for i in xrange(10000)])')
    tup_i=timeit.Ti mer('random.ran drange(10000) in l','import
    random; l=tuple(range(1 0000))')

    lst_str=timeit. Timer('md5.md5( str(random.rand range(10000))). hexdigest()
    in l','import random,md5; l=[md5.md5(str(i)) .hexdigest() for i
    in xrange(10000)]')
    dct_str=timeit. Timer('l.has_ke y(md5.md5(str(r andom.randrange (10000))).hexdi gest())','impor t
    random,md5; l=dict([(md5.md5(str(i) ).hexdigest(),N one) for i
    in xrange(10000)])')
    tup_str=timeit. Timer('md5.md5( str(random.rand range(10000))). hexdigest()
    in l','import random,md5; l=tuple([md5.md5(str(i)) .hexdigest()
    for i in xrange(10000)])')

    print 'Integer lookup'
    r=lst_i.repeat( 100,100); print 'list:',min(r), max(r);
    r=dct_i.repeat( 100,100); print 'dict:',min(r), max(r);
    r=tup_i.repeat( 100,100); print 'tupl:',min(r), max(r);
    print 'String lookup'
    r=lst_str.repea t(100,100); print 'list:',min(r), max(r);
    r=dct_str.repea t(100,100); print 'dict:',min(r), max(r);
    r=tup_str.repea t(100,100); print 'tupl:',min(r), max(r);

    [[[Ran on IRIX64 6.5, 24 processors, 12G Memory, 4G Swap, this
    code only uses one processor at %100 the full length of the run]]]
    Python 2.2.3 (#1, Nov 25 2003, 18:58:21) [C] on irix646-n32
    Type "help", "copyright" , "credits" or "license" for more
    information.[color=blue][color=green][color=darkred]
    >>> ## working on region in file[/color][/color][/color]
    /usr/tmp/python-119959673PMu.py ...
    Integer lookup
    list: 0.126830816269 0.160212993622
    dict: 0.0036230087280 3 0.0038561820983 9
    tupl: 0.119297981262 0.161748170853
    String lookup
    list: 0.142526865005 0.188524961472
    dict: 0.0071139335632 3 0.0076019763946 5
    tupl: 0.143892049789 0.186873912811[color=blue][color=green][color=darkred]
    >>>[/color][/color][/color]

    The results are conclusive, go for dictionaries. But this
    surprised me a little, anyone have insight as to why?

    I was also surprised that tuples and lists scored exactly the
    same. I was hoping that immutable tuples might earn it some
    speed over lists.

    I will eventually need this for testing strings. So the
    doubling of speed for strings over integers for dictionaries
    is a little alarming. Lists and tuples only saw a modest increase.

    Thank you in advance for any clever tricks you suggest.

    -Brian

    Tags: None
    • Larry Bates
      #2
      Re: Testing for membership speed

      The dictionaries are faster because they are indexed.
      Lists/tuples must be searched serially from the
      beginning.

      Dictionary indexes are hashed and the
      hashing algorithm has more to do on a string
      than on an integer (see first article link
      below for explanation).

      You could check into pre-hashing your strings and using
      these as integer keys. It will take longer to build
      the dictionary, but searching should be faster.

      Here are some articles that might interest you:

      http://effbot.org/zone/python-hash.htm


      429 Too Many Requests
      http://mail.python.org/pipermail/python-dev/2003-June/036556.html


      eGenix.com: mxTextTools - Fast Text Processing for Python
      http://www.egenix.com/files/python/mxTextTools.html
      mxTextTools is an extension package for Python that provides high-performance text manipulation and searching algorithms, in addition to a very flexible and extendable state machine, the Tagging Engine, which allows scanning and processing text at C speeds.


      Searching list or tuple serially from the beginning
      should take approximately the same time. Nothing
      about the mutability can help the search speed.

      HTH,
      Larry Bates
      Syscon, Inc.


      <brianc@temple. edu> wrote in message
      news:mailman.42 .1087998564.275 77.python-list@python.org ...[color=blue]
      > I just ran this stuff for my own knowledge. Though it might be
      > useful to some other people to know and maybe spark a discussion.
      >
      > I needed a fast way to test for membership, so naturally the
      > choices were the builtin containers: lists, dictionaries, and
      > tuples. The following is the test code and results:
      >
      > import timeit
      >
      > lst_i=timeit.Ti mer('random.ran drange(10000) in l','import
      > random; l=range(10000)' )
      > dct_i=timeit.Ti mer('l.has_key( random.randrang e(10000))','imp ort
      > random; l=dict([(i,None) for i in xrange(10000)])')
      > tup_i=timeit.Ti mer('random.ran drange(10000) in l','import
      > random; l=tuple(range(1 0000))')
      >
      > lst_str=timeit. Timer('md5.md5( str(random.rand range(10000))). hexdigest()
      > in l','import random,md5; l=[md5.md5(str(i)) .hexdigest() for i
      > in xrange(10000)]')
      >[/color]
      dct_str=timeit. Timer('l.has_ke y(md5.md5(str(r andom.randrange (10000))).hexdi g
      est())','import[color=blue]
      > random,md5; l=dict([(md5.md5(str(i) ).hexdigest(),N one) for i
      > in xrange(10000)])')
      > tup_str=timeit. Timer('md5.md5( str(random.rand range(10000))). hexdigest()
      > in l','import random,md5; l=tuple([md5.md5(str(i)) .hexdigest()
      > for i in xrange(10000)])')
      >
      > print 'Integer lookup'
      > r=lst_i.repeat( 100,100); print 'list:',min(r), max(r);
      > r=dct_i.repeat( 100,100); print 'dict:',min(r), max(r);
      > r=tup_i.repeat( 100,100); print 'tupl:',min(r), max(r);
      > print 'String lookup'
      > r=lst_str.repea t(100,100); print 'list:',min(r), max(r);
      > r=dct_str.repea t(100,100); print 'dict:',min(r), max(r);
      > r=tup_str.repea t(100,100); print 'tupl:',min(r), max(r);
      >
      > [[[Ran on IRIX64 6.5, 24 processors, 12G Memory, 4G Swap, this
      > code only uses one processor at %100 the full length of the run]]]
      > Python 2.2.3 (#1, Nov 25 2003, 18:58:21) [C] on irix646-n32
      > Type "help", "copyright" , "credits" or "license" for more
      > information.[color=green][color=darkred]
      > >>> ## working on region in file[/color][/color]
      > /usr/tmp/python-119959673PMu.py ...
      > Integer lookup
      > list: 0.126830816269 0.160212993622
      > dict: 0.0036230087280 3 0.0038561820983 9
      > tupl: 0.119297981262 0.161748170853
      > String lookup
      > list: 0.142526865005 0.188524961472
      > dict: 0.0071139335632 3 0.0076019763946 5
      > tupl: 0.143892049789 0.186873912811[color=green][color=darkred]
      > >>>[/color][/color]
      >
      > The results are conclusive, go for dictionaries. But this
      > surprised me a little, anyone have insight as to why?
      >
      > I was also surprised that tuples and lists scored exactly the
      > same. I was hoping that immutable tuples might earn it some
      > speed over lists.
      >
      > I will eventually need this for testing strings. So the
      > doubling of speed for strings over integers for dictionaries
      > is a little alarming. Lists and tuples only saw a modest increase.
      >
      > Thank you in advance for any clever tricks you suggest.
      >
      > -Brian
      >[/color]


        Comment

        Previous template Next
        Working...