Last active
June 25, 2022 08:35
-
-
Save graingert/00172a62c3c69a0a0fed8fb6f026b97e to your computer and use it in GitHub Desktop.
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
import timeit, random | |
import heapq | |
random.seed(42) | |
left = [] | |
right = [] | |
# Create two sorted lists of integers | |
n = 0 | |
for i in range(100000): | |
n += random.randint(1, 10) | |
left.append(n) | |
n = 0 | |
for i in range(100000): | |
n += random.randint(1, 10) | |
right.append(n) | |
def merge(): | |
sortedResult = [] | |
iLeft = 0 | |
iRight = 0 | |
while (len(sortedResult) < (len(left) + len(right))): | |
# Append the smaller of left & right's value to `sortedResult`. | |
if left[iLeft] < right[iRight]: | |
sortedResult.append(left[iLeft]) | |
iLeft += 1 | |
else: | |
sortedResult.append(right[iRight]) | |
iRight += 1 | |
# If one of the pointers has reached the end of its list, | |
# put the rest of the other list into `sortedResult`. | |
if iLeft == len(left): | |
sortedResult.extend(right[iRight:]) | |
break | |
elif iRight == len(right): | |
sortedResult.extend(left[iLeft:]) | |
break | |
def heapq_merge(_heapq_merge=heapq.merge, _list=list): | |
_list(_heapq_merge(left, right)) | |
def appendAndSort(): | |
sortedResult = left + right | |
sortedResult.sort() | |
def appendAndSorted(_sorted=sorted): | |
sortedResult = _sorted(left + right) | |
n = 100 | |
print(f"{timeit.timeit('merge()', globals=globals(), number=n)=}") | |
print(f"{timeit.timeit('appendAndSort()', globals=globals(), number=n)=}") | |
print(f"{timeit.timeit('appendAndSorted()', globals=globals(), number=n)=}") | |
print(f"{timeit.timeit('heapq_merge()', globals=globals(), number=n)=}") |
Author
graingert
commented
Jun 25, 2022
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment