Tweets per second

Question

This challenge is from Talent Buddy:

Tweets per second

Japan Castle in the Sky airing broke a Twitter record on August 3, 2013. At one point during the classic anime movie showing, people submitted 143,199 tweets per second. This particular spike was about 25 times greater than Twitter’s steady state.

Given an array of integers representing the number of tweets recorded every second and an integer value K, your task is to write a function that prints to the standard output (stdout) the highest number of tweets recorded between each second in the array and the past K seconds before it

Note that your function will receive the following arguments: tps, which is an array of integers representing the number of tweets recorded every second, and k, which is the integer number mentioned above.

Data constraints: the length of the array above will not exceed 500,000 numbers

Efficiency constraints: your function is expected to print the requested result and return in less than 2 seconds

Example Input

tps: 6, 9, 4, 7, 4, 1

k: 3

Output

6 9 9 9 7 7

Please Note: The above program should run in below 2 seconds

My Program

start=1
for i,j in enumerate(tps):
    if start<=k:
        print max(tps[:start])
        start+=1
    else:
        print max(tps[i-(start)+2:i+1])

This function takes more than 2 seconds for the test case.

How can we do same thing less in than 2 seconds? How can this be optimized to make it faster?

Answer 1

The problem with your implementation is you will slice the list each iteration, thus the \$O(n*k)\$ complexity Josay talked about. To (somewhat) fix this, you can change your code so that it will only slice your list at most once every k indices.

In order to do this, we can need to store the current maximum value as well as its 'life' (i.e. the number of iterations the value can be still in a window). A basic algorithm is explained on this site provided in the comments by Jaime.

Here is my first implementation:

def tweets_per_second(tps, k):
    life = k
    maximum = -1
    for index, val in enumerate(tps):
        # Is the current value a new maximum?
        # If so, set it and give it a maximum lifespan.
        if val >= maximum:
            maximum = val
            life = k

        print maximum

        # The current maximum has one less window it can reside in.
        # Once we reach zero, we need to find the maximum from 
        # the (k-1 length) window starting IMMEDIATELY after the 
        # previous maximum and the current value. 
        life -= 1
        if not life:
            window = tps[index-k+2:index+1]
            maximum = max(window)

            # Reassign the lifespan based on how far back in the window
            # the maximum value is.
            life = k - window[::-1].index(maximum) - 1

Notice there are a few improvements that we can make, most namely, getting rid of the slicing which takes \$O(k)\$ time. So instead lets use a deque from the collections module. It has an \$O(1)\$ time when appending. Thus, instead of generating the window each time we need find a new maximum, we simply keep the active window in memory.

This change does force use to move some things around, but they are not too major:

from collections import deque

def tweets_per_second(tps, k):
    life = k
    maximum = -1
    window = deque(maxlen=k)
    for index, val in enumerate(tps):
        # Because we specified `maxlen` when creating our window,
        # it will only keep `k` elements.
        window.append(val)

        if not life:
            maximum = -1

            # windex.....get it?
            for windex, win_val in enumerate(window): 
                if win_val >= maximum:
                    maximum = win_val
                    max_index = windex

            life = max_index + 1

        # Is the current value a new maximum?
        # If so, set it and give it a maximum lifespan.
        if val >= maximum:
            maximum = val
            life = k

        print maximum
        life -= 1

The above algorithm runs in under 2 seconds for all of their test cases, and passes all but one. This fail, I believe, is on their end as the output they generate is inconsistent from test to test.

Answer 2

Variable names i, j, k are cryptic. Furthermore, naming them similarly implies that there is some relationship between them, but actually there isn't any. i is an index, j is a data point, and k is a fixed interval size parameter.

Having the initial start <= k case in the loop slows down the loop even after it has reached steady state.

Some abstraction would be nice. It's a good habit to package your code in a function, and for the calculation and output routines to be decoupled.

There's a lot of array slicing going on. The solution, I think, is to use a circular-buffer.

def max_over_interval(data, interval_size=1):
    ring_buf = [0] * interval_size
    for i, datum in enumerate(data):
        ring_buf[i % interval_size] = datum
        yield(max(ring_buf))

The solution above works when data points are at least 0, which should be a reasonable assumption if the data represent tweet rates.

---

The next optimization might be to do some caching to avoid having to call max().

from operator import itemgetter

def max_over_interval(data, interval_size=1):
    ring_buf = [0] * interval_size
    cached_max_pos, cached_max = 0, 0
    for i, datum in enumerate(data):
        j = i % interval_size
        ring_buf[j] = datum

        if datum > cached_max:
            cached_max_pos, cached_max = j, datum
            yield cached_max
        elif j != cached_max_pos:
            yield cached_max
        else:
            cached_max_pos, cached_max = max(enumerate(ring_buf), key=itemgetter(1))
            yield cached_max

def tweets_per_second(tps, k):
    for n in max_over_interval(tps, k):
        print(n)

The online judge somehow declares that it takes longer than two seconds to process a sample tps of 81259 elements and an interval size of 31763, even though it completes in about 1/3 of a second on my machine.

Answer 3

Making your solution better

You won't get a huge performance boost unless you change your algorithm. Anyway, let's try to see what could be done to improve your code.

You are playing with a variable start. It is easy to check that a few properties hold (cf assert statement):

def solution_0_bis(tps, k):
    start=1
    for i,j in enumerate(tps):
        if start<=k:
            assert i < k
            assert i+1 == start
            print max(tps[:start]),
            start+=1
            assert i+2 == start
        else:
            assert i >= k
            assert start == k+1
            print max(tps[i-(start)+2:i+1]),
    print "done"

Thus, because start can be re-expressed in terms of other variables, we can get rid of it. After substitution and removal of asserts, your code becomes :

def solution_0_bis(tps, k):
    for i,j in enumerate(tps):
        if i<k:
            print max(tps[:i+1]),
        else:
            print max(tps[i-(k+1)+2:i+1]),
    print "done"

After introduction of 0 in the first slice expression and a bit of mathematics, in the condition check and in the second slice expression, the code is now :

def solution_0_bis(tps, k):
    for i,j in enumerate(tps):
        if i-k+1 <= 0:
            print max(tps[0:i+1]),
        else:
            print max(tps[i-k+1:i+1]),
    print "done"

This is when the magic can happen as you can get rid of duplicated code :

def solution_0_bis(tps, k):
    for i,j in enumerate(tps):
        print max(tps[max(0,i-k+1):i+1]),
    print "done"

You can easily see what are the partial lists we are working on by removing the call to max. (To be fair, I first wrote that piece of code and then tried to reduce your code to this).

Once you have this, you have an easy solution that you can use to compare results while implementing a different algorithm among one suggested in the comments.