Feature Requests item #1619060, was opened at 2006-12-19 22:14 Message generated for change (Comment added) made by karlb You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=355470&aid=1619060&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: Extension Modules Group: Python 2.6 Status: Open Resolution: None Priority: 5 Private: No Submitted By: Jeffrey C. Jacobs (timehorse) Assigned to: Raymond Hettinger (rhettinger) Summary: bisect on presorted list Initial Comment: The python and c implementation of bisect do not support custom-sorted lists using the list.sort method. In order to support an arbitrarily sorted list via sort(cmp, key, reverse), I have added 3 corresponding parameters to the bisect methods for bisection and insort (insert-sorted) corresponding to the parameters in sort. This would be useful if a list is initially sorted by its sort method and then the client wishes to maintain the sort order (or reverse-sort order) while inserting an element. In this case, being able to use the same, arbitrary binary function cmp, unary function key and boolean reverse flag to preserve the list order. The change imposes 3 new branch conditions and potential no-op function calls for when key is None. I have here implemented and partially tested the python implementation and if someone besides me would find this useful, I will update the _bisectmodule.c for this change as well. The Heap functions may also find use of an arbitrary predicate function so I may look at that later, but because bisect goes hand in hand with sorting, I wanted to tackle that first. ---------------------------------------------------------------------- Comment By: Karl Bartel (karlb) Date: 2007-08-17 17:09 Message: Logged In: YES user_id=787 Originator: NO +1 for adding a reverse parameter. ---------------------------------------------------------------------- Comment By: Raymond Hettinger (rhettinger) Date: 2006-12-19 22:43 Message: Logged In: YES user_id=80475 Originator: NO I'm -1 on this patch. At first blush it would seem nice to progagate sort's notion of a key= function; however, sort() is an all at once operation that can guarantee the function gets called only once per key. In contrast, bisect() is more granualar so consecutive calls may need to invoke the same key= function again and again. This is almost always the the-wrong-way-to-do-it (the key function should be precomputed and either stored separately or follow a decorate-sort pattern). By including custom sorting in bisect's API we would be diverting users away from better approaches. A better idea would be to create a recipe for a SortedList class that performed pre-calculated custom keys upon insertion and maintained an internal, decorated list. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=355470&aid=1619060&group_id=5470 _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
