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

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<rosuav@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.027
X-Spam-Evidence	'H': 0.95; 'S': 0.00; 'subject:Python': 0.06; 'binary': 0.07; 'subject:()': 0.09; 'testing,': 0.09; "wouldn't": 0.14; '"in': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'keys)': 0.16; 'wrote:': 0.18; 'thu,': 0.19; 'error': 0.23; 'source': 0.25; 'code:': 0.26; 'values': 0.27; 'header:In-Reply-To:1': 0.27; 'testing': 0.29; 'message- id:@mail.gmail.com': 0.30; 'membership': 0.31; '25,': 0.31; "d'aprano": 0.31; 'steven': 0.31; 'trouble': 0.34; 'received:google.com': 0.35; 'list': 0.37; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'does': 0.39; 'to:addr:python.org': 0.39; "you're": 0.61; 'save': 0.62; 'subject: & ': 0.68; 'qualified': 0.72; 'jul': 0.74; 'complexity': 0.84; '2013': 0.98
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=rHQsy1PlyYJ6rJwG1ycZ840CZ9wpuGgIRLrmoUQeQ0w=; b=X4U3a4RaJ468ljTqid2P9ONr47tDxSjN1gioMt4Ugxhe9wMwtBz6cVRrUwxzcSEPDk 4UXxzP1AnGdRyTtCed/M7wvQHdb8ntdtPaLhhOnUM9KeiMR3AKwKxF70dqLtaBPEtoTo JDxw++39VSnjnrCLVGn4aRnje5maq/klPBvhMq9SY/bQ7XJJxf4Vxiz0GdxhkmnchpbZ NsjddMtNrIfFCsbhAixRNgjBc77uEdE1ARlxEBncny0b9D5B7gto8J+a1FFYi+x4VRRq wQlFNd9nXRX1aWvzPJomI3mKPxfKhRMOIMesxCZcKugRSEh06yhBz9MUG0XtCpU+L38N hqhQ==
MIME-Version	1.0
X-Received	by 10.58.187.4 with SMTP id fo4mr17122613vec.55.1374739331834; Thu, 25 Jul 2013 01:02:11 -0700 (PDT)
In-Reply-To	<51f0ce06$0$29971$c3e8da3$5496439d@news.astraweb.com>
References	<51EF2AD8.3080105@stoneleaf.us> <ksnrr9$k4t$1@ger.gmane.org> <ksp2it$21p$1@ger.gmane.org> <mailman.5061.1374692206.3114.python-list@python.org> <51f0ce06$0$29971$c3e8da3$5496439d@news.astraweb.com>
Date	Thu, 25 Jul 2013 18:02:11 +1000
Subject	Re: Python 3: dict & dict.keys()
From	Chris Angelico <rosuav@gmail.com>
To	python-list@python.org
Content-Type	text/plain; charset=ISO-8859-1
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.5085.1374739334.3114.python-list@python.org> (permalink)
Lines	14
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1374739334 news.xs4all.nl 15897 [2001:888:2000:d::a6]:36296
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:51204

Show key headers only | View raw

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?

ChrisA

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