From 277842eff12eba1ceeeba1cee93db3ec99d5c95a Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sun, 11 May 2014 01:55:46 -0700
Subject: Issue #21424:  Optimize heaqp.nlargest() to make fewer tuple
 comparisons.

Consolidates the logic for nlargest() into a single function so that
decoration tuples (elem,order) or (key, order, elem) only need to
be formed when a new element is added to the heap.  Formerly, a tuple
was created for every element regardless of whether it was added to
the heap.

The change reduces the number of tuples created, the number of ordering
integers created, and total number of tuple comparisons.
---
 Modules/_heapqmodule.c | 85 --------------------------------------------------
 1 file changed, 85 deletions(-)

(limited to 'Modules/_heapqmodule.c')

diff --git a/Modules/_heapqmodule.c b/Modules/_heapqmodule.c
index b3e4753f26..964f511646 100644
--- a/Modules/_heapqmodule.c
+++ b/Modules/_heapqmodule.c
@@ -267,89 +267,6 @@ heapify(PyObject *self, PyObject *heap)
 PyDoc_STRVAR(heapify_doc,
 "Transform list into a heap, in-place, in O(len(heap)) time.");
 
-static PyObject *
-nlargest(PyObject *self, PyObject *args)
-{
-    PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;
-    Py_ssize_t i, n;
-    int cmp;
-
-    if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))
-        return NULL;
-
-    it = PyObject_GetIter(iterable);
-    if (it == NULL)
-        return NULL;
-
-    heap = PyList_New(0);
-    if (heap == NULL)
-        goto fail;
-
-    for (i=0 ; i<n ; i++ ){
-        elem = PyIter_Next(it);
-        if (elem == NULL) {
-            if (PyErr_Occurred())
-                goto fail;
-            else
-                goto sortit;
-        }
-        if (PyList_Append(heap, elem) == -1) {
-            Py_DECREF(elem);
-            goto fail;
-        }
-        Py_DECREF(elem);
-    }
-    if (PyList_GET_SIZE(heap) == 0)
-        goto sortit;
-
-    for (i=n/2-1 ; i>=0 ; i--)
-        if(_siftup((PyListObject *)heap, i) == -1)
-            goto fail;
-
-    sol = PyList_GET_ITEM(heap, 0);
-    while (1) {
-        elem = PyIter_Next(it);
-        if (elem == NULL) {
-            if (PyErr_Occurred())
-                goto fail;
-            else
-                goto sortit;
-        }
-        cmp = PyObject_RichCompareBool(sol, elem, Py_LT);
-        if (cmp == -1) {
-            Py_DECREF(elem);
-            goto fail;
-        }
-        if (cmp == 0) {
-            Py_DECREF(elem);
-            continue;
-        }
-        oldelem = PyList_GET_ITEM(heap, 0);
-        PyList_SET_ITEM(heap, 0, elem);
-        Py_DECREF(oldelem);
-        if (_siftup((PyListObject *)heap, 0) == -1)
-            goto fail;
-        sol = PyList_GET_ITEM(heap, 0);
-    }
-sortit:
-    if (PyList_Sort(heap) == -1)
-        goto fail;
-    if (PyList_Reverse(heap) == -1)
-        goto fail;
-    Py_DECREF(it);
-    return heap;
-
-fail:
-    Py_DECREF(it);
-    Py_XDECREF(heap);
-    return NULL;
-}
-
-PyDoc_STRVAR(nlargest_doc,
-"Find the n largest elements in a dataset.\n\
-\n\
-Equivalent to:  sorted(iterable, reverse=True)[:n]\n");
-
 static int
 _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
 {
@@ -531,8 +448,6 @@ static PyMethodDef heapq_methods[] = {
         METH_VARARGS,           heapreplace_doc},
     {"heapify",         (PyCFunction)heapify,
         METH_O,                 heapify_doc},
-    {"nlargest",        (PyCFunction)nlargest,
-        METH_VARARGS,           nlargest_doc},
     {"nsmallest",       (PyCFunction)nsmallest,
         METH_VARARGS,           nsmallest_doc},
     {NULL,              NULL}           /* sentinel */
-- 
cgit v1.2.1