mit6006_fall2011_lesson1

1d_peak_finding.py

#coding:UTF-8

from math import inf, floor
from time import time
from random import randint

def linear_find_peak_1d(l, start, end):
    minus_inf = -1 * inf
    l = [minus_inf] + l[start:end] + [minus_inf]
    for i in range(1, len(l)+1):
        if l[i] >= l[i-1] and l[i] >= l[i+1]:
            return l[i], start+i-1
    else:
        raise Exception("no peak.")

def logarithmic_find_peak_1d(l, start, end):
    if start == end:
        return l[start], start

    mid_idx = (end-start)//2 + start
    mid = l[mid_idx]
    mid_left = l[mid_idx-1]

    try:
        mid_right = l[mid_idx+1]
    except IndexError:
        mid_right = -1 * inf

    if mid_left > mid:
        return logarithmic_find_peak_1d(l, start, mid_idx)
    elif mid_right > mid:
        return logarithmic_find_peak_1d(l, mid_idx+1, end)
    else:
        return mid, mid_idx

n = 10
item_min = 1
item_max = 100
l = [randint(item_min, item_max) for i in range(n)]
print(l)
print(logarithmic_find_peak_1d(l, 0, len(l)))
print(linear_find_peak_1d(l, 0, len(l)))

###########################
# time complexity
# l = list(range(1,10000)) # worst case:

# def test(n, f, *args):
#     msg = "run {} on {} for {} time: {}"
#     start = time()
#     for i in range(n):
#         f(*args)
#     end = time()
#     print(msg.format(f.__name__, "range(1, 10000)", n, end-start))

# test(1000, linear_find_peak_1d, l, 0, len(l))
# test(1000, logarithmic_find_peak_1d, l, 0, len(l))

###########################
# 

2d_peak_finding.py

#coding:UTF-8

from random import randint
from pprint import pprint
from math import inf

def logarithmic_find_peak_2d(arr, start, end):
    print("=".center(40, "="))
    print("start: {} end: {}".format(start, end))
    if start == end:
        col = arr[start]
        return max(col), start, col.index(max(col))

    mid_col_num = (end-start) // 2 + start
    col_max = max(arr[mid_col_num])
    col_max_idx = arr[mid_col_num].index(col_max)

    col_max_left = arr[mid_col_num-1][col_max_idx]

    try:
        col_max_right = arr[mid_col_num+1][col_max_idx]
    except IndexError:
        col_max_right = -1 * inf

    if col_max < col_max_left:
        return logarithmic_find_peak_2d(arr, start, mid_col_num)
    elif col_max < col_max_right:
        return logarithmic_find_peak_2d(arr, mid_col_num+1, end)
    else:
        return col_max, mid_col_num, col_max_idx

def make_arr(n, m, min, max):
    return [[randint(min, max) for j in range(n)] for i in range(m)]

def print_arr(arr, n, m):
    for i in range(n):
        for j in range(m):
            print("%3d" % arr[j][i], end=" ")
        print("")

n_row = 8
n_column = 8
item_min = 1
item_max = 100

arr = make_arr(n_row, n_column, item_min, item_max)
# pprint(arr)
print_arr(arr, n_row, n_column)
peak = logarithmic_find_peak_2d(arr, 0, n_column)
msg = "peak: {} col: {} row: {}"
print(msg.format(*peak))