from heapq import heappop, heapify, heapreplace, nlargest
from itertools import islice
def klargest_fullheap(iterable, k):
heap = [-s for s in iterable]
heapify(heap)
return [-heappop(heap) for _ in range(k)]
def klargest_smallheap(iterable, k):
heap = list(islice(iterable, k))
heapify(heap)
for s in iterable:
if s > heap[0]:
heapreplace(heap, s)
return [heappop(heap) for _ in range(k)]
def klargest_heapq(iterable, k):
return nlargest(k, iterable)
if __name__ == "__main__":
from random import randrange
from time import clock
n = 6
for k_exp in range(n+1):
k = 10**k_exp
print("k=", k)
print("n=", 10**n)
for method in (klargest_smallheap, klargest_fullheap,
klargest_heapq):
example = (randrange(1, 1000000000) for _ in range(10**n))
t0 = clock()
method(example, k)
print("{:20s} {:6.3f}".format(method.__name__, clock() - t0))
ZnJvbSBoZWFwcSBpbXBvcnQgaGVhcHBvcCwgaGVhcGlmeSwgaGVhcHJlcGxhY2UsIG5sYXJnZXN0CmZyb20gaXRlcnRvb2xzIGltcG9ydCBpc2xpY2UKCgpkZWYga2xhcmdlc3RfZnVsbGhlYXAoaXRlcmFibGUsIGspOgogICAgaGVhcCA9IFstcyBmb3IgcyBpbiBpdGVyYWJsZV0KICAgIGhlYXBpZnkoaGVhcCkKICAgIHJldHVybiBbLWhlYXBwb3AoaGVhcCkgZm9yIF8gaW4gcmFuZ2UoayldCgoKZGVmIGtsYXJnZXN0X3NtYWxsaGVhcChpdGVyYWJsZSwgayk6CiAgICBoZWFwID0gbGlzdChpc2xpY2UoaXRlcmFibGUsIGspKQogICAgaGVhcGlmeShoZWFwKQogICAgZm9yIHMgaW4gaXRlcmFibGU6CiAgICAgICAgaWYgcyA+IGhlYXBbMF06CiAgICAgICAgICAgIGhlYXByZXBsYWNlKGhlYXAsIHMpCiAgICByZXR1cm4gW2hlYXBwb3AoaGVhcCkgZm9yIF8gaW4gcmFuZ2UoayldCgoKZGVmIGtsYXJnZXN0X2hlYXBxKGl0ZXJhYmxlLCBrKToKICAgIHJldHVybiBubGFyZ2VzdChrLCBpdGVyYWJsZSkKCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgZnJvbSByYW5kb20gaW1wb3J0IHJhbmRyYW5nZQogICAgZnJvbSB0aW1lIGltcG9ydCBjbG9jawoKICAgIG4gPSA2CiAgICBmb3Iga19leHAgaW4gcmFuZ2UobisxKToKICAgICAgICBrID0gMTAqKmtfZXhwCiAgICAgICAgcHJpbnQoIms9IiwgaykKICAgICAgICBwcmludCgibj0iLCAxMCoqbikKICAgICAgICBmb3IgbWV0aG9kIGluIChrbGFyZ2VzdF9zbWFsbGhlYXAsIGtsYXJnZXN0X2Z1bGxoZWFwLAogICAgICAgICAgICAgICAgICAgICAgICBrbGFyZ2VzdF9oZWFwcSk6CiAgICAgICAgICAgIGV4YW1wbGUgPSAocmFuZHJhbmdlKDEsIDEwMDAwMDAwMDApIGZvciBfIGluIHJhbmdlKDEwKipuKSkKICAgICAgICAgICAgdDAgPSBjbG9jaygpCiAgICAgICAgICAgIG1ldGhvZChleGFtcGxlLCBrKQogICAgICAgICAgICBwcmludCgiezoyMHN9IHs6Ni4zZn0iLmZvcm1hdChtZXRob2QuX19uYW1lX18sIGNsb2NrKCkgLSB0MCkp