max_sliding_window.py

# coding: utf-8

import random
import timeit
from collections import deque

list = range(50000*2)
random.shuffle(list)
#print list
k = 5000


def max_sliding_window(list, k):
	queue = deque()
	ret = []
	n = len(list)
	for i in range(0, n):
		#print "ITER",i
		item = list[i]
		#queueBefore = queue[:]
		#print list[max(i-k,0):i]
		if queue and queue[0][1] == i-k:
			#print "removing old", queue[0][0]
			queue.popleft()
		while queue and item > queue[-1][0]:
			#print "removing small", queue[-1][0]
			queue.pop()
		queue.append((item, i))
		#print len(queue), [x for x,y in queueBefore], " + ", item ," -> ",[x for x,y in queue]
		if i >= k-1:
			ret.append(queue[0][0])
	return ret	
		
		
def max_sliding_window_naive(list, k):
	ret = []
	n = len(list)
	for i in range(0, n - k + 1):
		window = list[i:i+k]
		#print window, max(window)		
		ret.append(max(window))
	return ret
	
def test():
	print "test"
	
if __name__ == '__main__':
	import timeit
	#print(timeit.timeit("test()", setup="from __main__ import test", number=2))
	print(timeit.timeit("max_sliding_window(list, k)", setup="from __main__ import max_sliding_window; from __main__ import list; from __main__ import k", number=1))
	
	print(timeit.timeit("max_sliding_window_naive(list, k)", setup="from __main__ import max_sliding_window_naive; from __main__ import list; from __main__ import k", number=1))
	
	
	#a = max_sliding_window_naive(list, k)
	#b = max_sliding_window(list, k)
	#print a
	#print b
	#print min(a), min(b)
	#print a == b