Last active
October 24, 2019 13:17
-
-
Save domdomegg/2783028abcfcf7bed5ef50cb1cea361b 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
# You can view me at https://gist.github.com/domdomegg/2783028abcfcf7bed5ef50cb1cea361b | |
# You can run me at https://repl.it/@domdomegg/cs260-cw1-q2 | |
TEST_RUNS = 5 | |
TEST_N = 1000 | |
TEST_MAX = 5000 # TEST_MIN will be -TEST_MAX | |
import numpy as np | |
import time | |
def efficient_iterative(a): | |
running_max1 = -float("inf") | |
running_max2 = -float("inf") | |
running_min1 = float("inf") | |
running_min2 = float("inf") | |
for elem in a: | |
if elem > running_max1: | |
running_max2 = running_max1 | |
running_max1 = elem | |
elif elem > running_max2: | |
running_max2 = elem | |
for elem in a: | |
if elem < running_min1: | |
running_min2 = running_min1 | |
running_min1 = elem | |
elif elem < running_min2: | |
running_min2 = elem | |
return max(running_max1 * running_max2, running_min1 * running_min2) | |
def efficient_recursive(a): | |
(max1, max2) = greatestTwoInArray(a) | |
(min1, min2) = leastTwoInArray(a) | |
return max(max1 * max2, min1 * min2) | |
def greatestTwoInArray(a, max1=-float("inf"), max2=-float("inf")): | |
if len(a) == 0: | |
return (max1, max2) | |
if a[0] > max1: | |
max2 = max1 | |
max1 = a[0] | |
elif a[0] > max2: | |
max2 = a[0] | |
return greatestTwoInArray(a[1:], max1, max2) | |
def leastTwoInArray(a, min1=float("inf"), min2=float("inf")): | |
if len(a) == 0: | |
return (min1, min2) | |
if a[0] < min1: | |
min2 = min1 | |
min1 = a[0] | |
elif a[0] < min2: | |
min2 = a[0] | |
return leastTwoInArray(a[1:], min1, min2) | |
def simple(a): | |
running_max = -1 | |
for i, elemI in enumerate(a): | |
for j, elemJ in enumerate(a): | |
if i < j: | |
running_max = max(running_max, elemI * elemJ) | |
return running_max | |
def test(a): | |
simpleStart = time.perf_counter() | |
simpleAns = simple(a) | |
simpleEnd = time.perf_counter() | |
simpleTime = simpleEnd - simpleStart | |
efficientStart = time.perf_counter() | |
efficientAns = efficient_iterative(a) | |
efficientEnd = time.perf_counter() | |
efficientTime = efficientEnd - efficientStart | |
if (simpleAns == efficientAns): | |
print("A[i] * A[j] =", efficientAns) | |
print("efficient method was", int(simpleTime/efficientTime), "times faster than simple method\n") | |
else: | |
print("Got different answers!") | |
print("A = ", a) | |
print("[simpleAns] =", simpleAns) | |
print("[efficientAns] =", efficientAns) | |
raise AssertionError | |
print("Running", TEST_RUNS, "test runs, with n =", TEST_N, "and", -TEST_MAX, "<= a[i] <=", TEST_MAX, end="\n\n") | |
for i in range(0, TEST_RUNS): | |
a = (np.random.random_sample(TEST_N) * TEST_MAX * 2) - TEST_MAX | |
test(a) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment