cs260-cw1-q2.py

# 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)