O(1) xrange membership testing

[boredzo]

BPO	1002085
Nosy	@tim-one, @loewis, @ronaldoussoren
Files	rangeobject.patch: The patch, affecting Objects/rangeobject.c and Lib/test/test_xrange.py.

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2004-08-04.17:35:11.000>
created_at = <Date 2004-08-02.16:43:46.000>
labels = ['interpreter-core']
title = 'O(1) xrange membership testing'
updated_at = <Date 2004-08-04.17:35:11.000>
user = 'https://bugs.python.org/boredzo'

bugs.python.org fields:

activity = <Date 2004-08-04.17:35:11.000>
actor = 'loewis'
assignee = 'none'
closed = True
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2004-08-02.16:43:46.000>
creator = 'boredzo'
dependencies = []
files = ['6132']
hgrepos = []
issue_num = 1002085
keywords = ['patch']
message_count = 8.0
messages = ['46513', '46514', '46515', '46516', '46517', '46518', '46519', '46520']
nosy_count = 4.0
nosy_names = ['tim.peters', 'loewis', 'ronaldoussoren', 'boredzo']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue1002085'
versions = []

[boredzo]

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 
darwin
Type "help", "copyright", "credits" or "license" for more 
information.
>>> import sys
>>> sys.maxint
2147483647
>>> sys.maxint in xrange(sys.maxint)
False

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.

[ronaldoussoren]

Logged In: YES
user_id=580910

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

BTW. Does your patch include unittests?

[boredzo]

Logged In: YES
user_id=711099

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 test_xrange.py.

[boredzo]

Logged In: YES
user_id=711099

found and fixed a bug: the new __contains__ method didn't check for
an exception from PyInt_AsLong.

[loewis]

Logged In: YES
user_id=21627

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.

[boredzo]

Logged In: YES
user_id=711099

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

[tim-one]

Logged In: YES
user_id=31435

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.

[loewis]

Logged In: YES
user_id=21627

Ah, forgot/ignored that. Rejecting the patch because the
feature was deprecated.