Author stargaming
Recipients
Date 2007-08-02.16:14:47
SpamBayes Score
Marked as misclassified
Message-id
In-reply-to
Content
Membership tests for xrange result in loss of xrange's laziness by iterating through every single item. This yields a complexity of O(n) and an unbearable runtime when handling larger ranges.

This issue can be fixed by using arithmetic decision instead of generic lookup/iteration. This will boil down the complexity to O(1) and make tests near the start of the range as fast as those near the end. The same technique is already used in item lookups.

The fix has been inspired by the "optimizing [x]range" thread in the python-3000-devel mailing list (see http://article.gmane.org/gmane.comp.python.python-3000.devel/8732).

A patch to Objects/rangeobject.c is attached. It modifies tp_as_sequence in PyRange_Type to include the sq_contains field and implement the procedure range_contains right there.
History
Date User Action Args
2007-08-23 15:59:32adminlinkissue1766304 messages
2007-08-23 15:59:32admincreate