#!/usr/bin/python
"Compare performance of two different ways to implement a queue."
import time

class ImperativeQueue:
    "By Kragen Sitaker."
    def __init__(self, initially=[]):
        self.queue = initially[:]
        self.ptr = 0

    def shift(self):
        rv = self.queue[self.ptr]
        self.ptr += 1
        if self.ptr > len(self.queue) / 2:
            self.queue[:self.ptr] = []
            self.ptr = 0
        return rv

    def push(self, item):
        self.queue.append(item)

    def __len__(self):
        return len(self.queue) - self.ptr

class FunctionalQueue:
    "By Darius Bacon."
    def __init__(self):
        self.front, self.back = [], []

    def shift(self):
        if not self.back:
            self.back, self.front = list(reversed(self.front)), []
        return self.back.pop()

    def push(self, x):
        self.front.append(x)

    def __len__(self):
        return len(self.front) + len(self.back)

def exercise_queue(implementation, length, iterations):
    qq = implementation()

    for ii in range(length):
        qq.push(0)

    for ii in range(iterations-length):
        qq.push(0)
        qq.shift()

    while qq:
        qq.shift()

def timeit(thunk):
    start = time.time()
    thunk()
    return time.time() - start

def benchmark_queue(implementation, length, iterations):
    return timeit(lambda:
                  exercise_queue(implementation, length, iterations))

def display_bm_queue(implementation, length, iterations):
    seconds = benchmark_queue(implementation, length, iterations)
    print '%s: %d iteration%s with length %d: %.2g (%.2g/iter)' % (
        implementation.__name__,
        iterations,
        '' if iterations == 1 else 's',
        length,
        seconds,
        seconds / iterations,
        )

def main():
    for implementation in [ImperativeQueue, FunctionalQueue]:
        for length in 1, 3, 10, 30, 100, 300, 1000, 3000:
            for iterations in 10000, 30000, 100000, 300000, 1000000:
                display_bm_queue(implementation, length, iterations)

if __name__ == '__main__':
    main()