Patches item #1766304, was opened at 2007-08-02 18:14 Message generated for change (Comment added) made by stargaming You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1766304&group_id=5470
Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: Core (C code) Group: Python 2.6 Status: Open Resolution: None Priority: 5 Private: No Submitted By: Stargaming (stargaming) Assigned to: Nobody/Anonymous (nobody) Summary: improve xrange.__contains__ Initial Comment: 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. ---------------------------------------------------------------------- >Comment By: Stargaming (stargaming) Date: 2007-08-06 13:37 Message: Logged In: YES user_id=1491473 Originator: YES The Python 3000 patch required a rewrite from scratch since we can't issue PyIntObject->ob_ival directly any longer. Instead, we use the PyNumber-API now. File Added: rangeobject.c.diff ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1766304&group_id=5470 _______________________________________________ Patches mailing list [email protected] http://mail.python.org/mailman/listinfo/patches
