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>
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

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