New submission from Will Haldean Brown: The implementation of nsmallest in heapq contains an optimization for when n is an order of magnitude less than the size of the data, which uses bisect to find the n-smallest elements. This optimization is guarded by a check to ensure that the data iterable has a length method.
This method is then decorated to add support for the key kwarg. The decorator creates a zip object and passes the zip object to the decorated nsmallest. As zip objects are generators, they do not have a __len__ attribute, and the bisect optimization is never used. The attached patch file detects whether the data passed to the decorator has a length attribute, and if it does, it creates a list with the data before passing it to the decorated nsmallest. This is my first patch, so if I've done something wrong please let me know. Thanks! ---------- components: Library (Lib) files: heapq-use-bisect.20121001.patch keywords: patch messages: 171706 nosy: haldean priority: normal severity: normal status: open title: Bisect optimization in heapq.nsmallest is never used type: performance versions: Python 3.4 Added file: http://bugs.python.org/file27372/heapq-use-bisect.20121001.patch _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue16098> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
