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

Groups > comp.lang.python > #51237

Re: Python 3: dict & dict.keys()

Show key headers only | View raw

On Thu, Jul 25, 2013 at 2:13 AM, Peter Otten <__peter__@web.de> wrote:
> Chris Angelico wrote:
>
>> On Thu, Jul 25, 2013 at 5:04 PM, Steven D'Aprano
>> <steve+comp.lang.python@pearwood.info> wrote:
>>> - Views support efficient (O(1) in the case of keys) membership testing,
>>> which neither iterkeys() nor Python2 keys() does.
>>
>> To save me the trouble and potential error of digging through the
>> source code: What's the complexity of membership testing on
>> values/items? Since you're calling it "efficient" it must be better
>> than O(n) which the list form would be, yet it isn't O(1) or you
>> wouldn't have qualified "in the case of keys". Does this mean
>> membership testing of the values and items views is O(log n) in some
>> way, eg a binary search?
>
> keys() and items() is O(1); both look up the key in the dictionary and
> items() then proceeds to compare the value. values() is O(n).

3.x values() is O(n) but avoids the unnecessary step of copying all the
values in the dict that you get when performing the same operation
using 2.x values().  Hence, although the asymptotic complexity is the
same, it's still more efficient.

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

Thread

Re: Python 3: dict & dict.keys() Ethan Furman <ethan@stoneleaf.us> - 2013-07-24 11:31 -0700
  Re: Python 3: dict & dict.keys() alex23 <wuwei23@gmail.com> - 2013-07-25 16:01 +1000
    Re: Python 3: dict & dict.keys() Ethan Furman <ethan@stoneleaf.us> - 2013-07-25 06:47 -0700
  Re: Python 3: dict & dict.keys() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-25 07:04 +0000
    Re: Python 3: dict & dict.keys() Chris Angelico <rosuav@gmail.com> - 2013-07-25 18:02 +1000
    Re: Python 3: dict & dict.keys() Peter Otten <__peter__@web.de> - 2013-07-25 10:13 +0200
    Re: Python 3: dict & dict.keys() Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-25 09:53 -0600
    Re: Python 3: dict & dict.keys() Peter Otten <__peter__@web.de> - 2013-07-25 18:25 +0200

csiph-web