[issue16098] Bisect optimization in heapq.nsmallest is never used

[Will Haldean Brown]

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 <report at bugs.python.org>
<http://bugs.python.org/issue16098>
_______________________________________