Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #34489

Re: Confused compare function :)

Show all headers | View raw

On 12/7/2012 5:16 PM, Steven D'Aprano wrote:
> On Thu, 06 Dec 2012 23:14:17 +1100, Chris Angelico wrote:
>
>> Setting up the try/except is a constant time cost,
>
> It's not just constant time, it's constant time and *cheap*. Doing
> nothing inside a try block takes about twice as long as doing nothing:
>
> [steve@ando ~]$ python2.7 -m timeit "try: pass
>> except: pass"
> 10000000 loops, best of 3: 0.062 usec per loop
>
> [steve@ando ~]$ python2.7 -m timeit "pass"
> 10000000 loops, best of 3: 0.0317 usec per loop
>
>
>> while the duplicated
>> search for k inside the dictionary might depend on various other
>> factors.
>
> It depends on the type, size and even the history of the dict, as well as
> the number, type and values of the keys. Assuming a built-in dict, we can
> say that in the absence of many collisions, key lookup can be amortized
> over many lookups as constant time.
>
>
>> In the specific case of a Python dictionary, the membership
>> check is fairly cheap (assuming you're not the subject of a hash
>> collision attack - Py3.3 makes that a safe assumption),
>
> Don't be so sure -- the hash randomization algorithm for Python 3.3 is
> trivially beaten by an attacker.
>
> http://bugs.python.org/issue14621#msg173455
>
> but in general, yes, key lookup in dicts is fast. But not as fast as
> setting up a try block.
>
> Keep in mind too that the "Look Before You Leap" strategy is
> fundamentally unsound if you are using threads:
>
> # in main thread:
> if key in mydict:  # returns True
>      x = mydict[key]  # fails with KeyError
>
> How could this happen? In the fraction of a second between checking
> whether the key exists and actually looking up the key, another thread
> could delete it! This is a classic race condition, also known as a Time
> Of Check To Time Of Use bug.

I generally agree with everything Steven has said here and in previous 
responses and add the following.

There are two reasons to not execute a block of code.

1. It could and would run, but we do not want it to run because a) we do 
not want an answer, even if correct; b) it would return a wrong answer 
(which of course we do not want); or c) it would run forever and never 
give any answer. To not run code, for any of these reasons, requires an 
if statement.

2. It will not run but will raise an exception instead. In this case, we 
can always use try-except. Sometimes we can detect that it would not run 
before running it, and can use an if statement instead. (But as Steven 
points out, this is sometimes trickier than it might seem.) However, 
even if we can reliably detect that code would either run or raise an 
exception, this often or even usually requires doing redundant calculation.

For example, 'key in mydict' must hash the key, mod the hash according 
to the size of the dict, find the corresponding slot in the dict, and do 
an equality comparison with the existing key in the dict. If not equal, 
repeat according to the collision algorithm for inserting keys.

In other words, 'key in mydict' does everything done by 'mydict[key]' 
except to actually fetch the value when the right slot is found or raise 
an exception if there is no right slot.

So why ever use a redundant condition check? A. esthetics. B. 
practicality. Unfortunately, catching exceptions may be and often is as 
slow as the redundant check and even multiple redundant checks.

-- 
Terry Jan Reedy

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Confused compare function :) Bruno Dupuis <python.ml.bruno.dupuis@lisael.org> - 2012-12-06 01:19 +0100
  Re: Confused compare function :) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-12-06 00:42 +0000
    Re: Confused compare function :) Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-12-06 13:41 -0500
    Re: Confused compare function :) Anatoli Hristov <tolidtm@gmail.com> - 2012-12-06 19:55 +0100
  Re: Confused compare function :) Rotwang <sg552@hotmail.co.uk> - 2012-12-06 03:22 +0000
    Re: Confused compare function :) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-12-06 04:32 +0000
      Re: Confused compare function :) Bruno Dupuis <python.ml.bruno.dupuis@lisael.org> - 2012-12-06 09:49 +0100
        Re: Confused compare function :) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-12-06 11:47 +0000
          Re: Confused compare function :) peter <pjmakey2@gmail.com> - 2012-12-06 08:55 -0300
            Re: Confused compare function :) Hans Mulder <hansmu@xs4all.nl> - 2012-12-06 14:32 +0100
              Re: Confused compare function :) Chris Angelico <rosuav@gmail.com> - 2012-12-07 00:47 +1100
          Re: Confused compare function :) Chris Angelico <rosuav@gmail.com> - 2012-12-06 23:14 +1100
            Re: Confused compare function :) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-12-07 22:16 +0000
              Re: Confused compare function :) Terry Reedy <tjreedy@udel.edu> - 2012-12-08 02:01 -0500
              Re: Confused compare function :) Chris Angelico <rosuav@gmail.com> - 2012-12-08 18:17 +1100
              Re: Confused compare function :) MRAB <python@mrabarnett.plus.com> - 2012-12-08 17:50 +0000
            Re: Confused compare function :) Ramchandra Apte <maniandram01@gmail.com> - 2012-12-08 19:07 -0800
              Re: Confused compare function :) Chris Angelico <rosuav@gmail.com> - 2012-12-09 14:22 +1100
                Re: Confused compare function :) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-12-09 07:39 +0000
            Re: Confused compare function :) Ramchandra Apte <maniandram01@gmail.com> - 2012-12-08 19:07 -0800
          Re: Confused compare function :) Neil Cerutti <neilc@norwich.edu> - 2012-12-06 13:51 +0000
            Re: Confused compare function :) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-12-07 02:55 +0000
              Re: Confused compare function :) Neil Cerutti <neilc@norwich.edu> - 2012-12-07 16:40 +0000
        Re: Confused compare function :) Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2012-12-06 14:33 +0100
          Re: Confused compare function :) Chris Angelico <rosuav@gmail.com> - 2012-12-07 00:58 +1100
            Re: Confused compare function :) Hans Mulder <hansmu@xs4all.nl> - 2012-12-06 15:21 +0100
              Re: Confused compare function :) Chris Angelico <rosuav@gmail.com> - 2012-12-07 01:28 +1100
          Re: Confused compare function :) Anatoli Hristov <tolidtm@gmail.com> - 2012-12-06 15:22 +0100
          Re: Confused compare function :) Dave Angel <d@davea.name> - 2012-12-06 09:40 -0500
          Re: Confused compare function :) peter <pjmakey2@gmail.com> - 2012-12-06 11:46 -0300
          Re: Confused compare function :) Anatoli Hristov <tolidtm@gmail.com> - 2012-12-06 17:16 +0100
          Re: Confused compare function :) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-12-06 16:52 +0000
          Re: Confused compare function :) Anatoli Hristov <tolidtm@gmail.com> - 2012-12-06 18:08 +0100
          Re: Confused compare function :) MRAB <python@mrabarnett.plus.com> - 2012-12-06 17:10 +0000
          Re: Confused compare function :) Anatoli Hristov <tolidtm@gmail.com> - 2012-12-06 18:31 +0100
          Re: Confused compare function :) MRAB <python@mrabarnett.plus.com> - 2012-12-06 17:52 +0000
          Re: Confused compare function :) Anatoli Hristov <tolidtm@gmail.com> - 2012-12-06 19:25 +0100
          Re: Confused compare function :) Anatoli Hristov <tolidtm@gmail.com> - 2012-12-07 14:36 +0100
        Re: Confused compare function :) Rotwang <sg552@hotmail.co.uk> - 2012-12-06 19:24 +0000
      Re: Confused compare function :) Chris Angelico <rosuav@gmail.com> - 2012-12-06 20:34 +1100
      Re: Confused compare function :) Rotwang <sg552@hotmail.co.uk> - 2012-12-06 19:25 +0000

csiph-web