Created
February 2, 2016 12:31
-
-
Save cysin/4fadc49607713bb86343 to your computer and use it in GitHub Desktop.
A k-selection example in python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python | |
import heapq | |
import random | |
import time | |
def createArray(): | |
array = range( 10 * 1000 * 1000 ) | |
random.shuffle( array ) | |
return array | |
def linearSearch( bigArray, k ): | |
return sorted(bigArray, reverse=True)[:k] | |
def heapSearch( bigArray, k ): | |
heap = [] | |
# Note: below is for illustration. It can be replaced by | |
# heapq.nlargest( bigArray, k ) | |
for item in bigArray: | |
# If we have not yet found k items, or the current item is larger than | |
# the smallest item on the heap, | |
if len(heap) < k or item > heap[0]: | |
# If the heap is full, remove the smallest element on the heap. | |
if len(heap) == k: heapq.heappop( heap ) | |
# add the current element as the new smallest. | |
heapq.heappush( heap, item ) | |
return heap | |
start = time.time() | |
bigArray = createArray() | |
print "Creating array took %g s" % (time.time() - start) | |
start = time.time() | |
print linearSearch( bigArray, 10 ) | |
print "Linear search took %g s" % (time.time() - start) | |
start = time.time() | |
print heapSearch( bigArray, 10 ) | |
print "Heap search took %g s" % (time.time() - start) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment