This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: O(1) xrange membership testing
Type: Stage:
Components: Interpreter Core Versions:
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: boredzo, loewis, ronaldoussoren, tim.peters
Priority: normal Keywords: patch

Created on 2004-08-02 16:43 by boredzo, last changed 2022-04-11 14:56 by admin. This issue is now closed.

File name Uploaded Description Edit
rangeobject.patch boredzo, 2004-08-04 05:59 The patch, affecting Objects/rangeobject.c and Lib/test/
Messages (8)
msg46513 - (view) Author: Mac-arena the Bored Zo (boredzo) Date: 2004-08-02 16:43
this patch applies to anonymous CVS as of 2004-08-02 at 07:
54:58 PDT.

it adds O(1) membership testing; for example:

Python 2.4a1+ (#2, Aug  2 2004, 09:11:43) 
[GCC 3.3 20030304 (Apple Computer, Inc. build 1495)] on 
Type "help", "copyright", "credits" or "license" for more 
>>> import sys
>>> sys.maxint
>>> sys.maxint in xrange(sys.maxint)

in current CVS, this would take untold hours to complete 
(because Python arrives at this answer by iterating on the 
sequence). this patch adds a __contains__ method to the 
xrange object which examines the xrange's pattern and 
determines the correct answer instantly based on that pattern.
msg46514 - (view) Author: Ronald Oussoren (ronaldoussoren) * (Python committer) Date: 2004-08-02 17:28
Logged In: YES 

You forgot to add the patch (did you check the checkbox?).

BTW. Does your patch include unittests?
msg46515 - (view) Author: Mac-arena the Bored Zo (boredzo) Date: 2004-08-02 18:25
Logged In: YES 

heh, no I didn't check the checkbox. thanks for reminding me. :)

the original patch didn't include unit tests, but that is a good idea. ;) 
so I've added changes to
msg46516 - (view) Author: Mac-arena the Bored Zo (boredzo) Date: 2004-08-02 19:42
Logged In: YES 

found and fixed a bug: the new __contains__ method didn't check for 
an exception from PyInt_AsLong.
msg46517 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2004-08-03 12:50
Logged In: YES 

This patch is incorrect. Currently,

"s" in xrange(3,4)

gives False. With the patch, it raises an exception.

Your patch should only take integer objects into account. 
Any other object might have an __eq__ that makes it compare
equal to a number from the range.
msg46518 - (view) Author: Mac-arena the Bored Zo (boredzo) Date: 2004-08-04 05:59
Logged In: YES 

__contains__ never fails anymore; it now falls back on the old 
behaviour of iterating on the sequence when the object being tested 
for membership is not a Python int. (I didn't know it did that before. 
another cool Python feature. :)

also, the new patch is current with anonymous CVS as of 2004-08-03 
at 10:47:53 PM PDT.
msg46519 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2004-08-04 12:51
Logged In: YES 

You should know that xrange objects *used* to have 
efficient "in" testing, and a whole bunch of other features 
too.  They were deliberately removed in 2.2a1.  Search 
for "xrange" in your Python NEWS file.
msg46520 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2004-08-04 17:35
Logged In: YES 

Ah, forgot/ignored that. Rejecting the patch because the
feature was deprecated.
Date User Action Args
2022-04-11 14:56:06adminsetgithub: 40674
2004-08-02 16:43:46boredzocreate