3

Given an array of integers and an integer value K my task is to write a function that prints to the standard output the highest number for that value in the array and the past K entries before it.

Example Input:

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

Example Output:

6
9
9
9
7
7

I have been told that the code I have written could be made much more efficient for large data sets. How can I make this code most efficient?

def tweets_per_second(tps, k):
    past = [tps[0]]
    for t in tps[1:]:
        past.append(t)
        if len(past) > k: past = past[-k:]
        print max(past)
kilojoules
  • 9,768
  • 18
  • 77
  • 149
  • 2
    I don't understand how your input gives that output. Why do you get multiple `9`s and `7`s? – Adam Smith Jan 09 '15 at 22:37
  • 1
    @Adam: For each member of the array, it prints the maximum value of the past K members (including the current member). – Ani Jan 09 '15 at 22:41
  • 1
    You can use max heap with up to k elements (http://en.wikipedia.org/wiki/Heap_(data_structure)). Complexity would be O(nlogk) and it is optimal I believe. – Jarlax Jan 09 '15 at 22:45
  • Possible duplicates: https://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array, https://stackoverflow.com/questions/8499227/minimum-value-of-maximum-values-in-sub-segments-in-on-complexity/8499392#8499392 – augurar Jan 09 '15 at 23:22
  • 2
    @Jarlax Nope, not optimal. Optimal is `O(n)`. – btilly Jan 09 '15 at 23:31
  • @btilly You are right, thanks for pointing out! Didn't know [this](http://stackoverflow.com/a/8905575/4430998) approach. – Jarlax Jan 09 '15 at 23:44

3 Answers3

6

You can achieve a linear time complexity using a monotonic queue(O(n) for any value of k). The idea is the following:

  1. Let's maintain a deque of pairs (value, position). Initially, it is empty.

  2. When a new element arrives, do the following: while the position of the front element is out of range(less than i - K), pop it. While the value of the back element is less than the new one, pop it. Finally, push a pair (current element, its position) to the back of the deque.

  3. The answer for the current position is the front element of the deque.

Each element is added to the deque only once and removed at most once. Thus, the time complexity is linear and it does not depend on K. This solution is optimal because just reading the input is O(n).

kraskevich
  • 18,368
  • 4
  • 33
  • 45
3

Try using a heap to achieve reducing the complexity of the max operation in from O(K) to O(logK) time.

  • Add first (-tps[i])*, i in range(0,k) and output (-heap[0]) each time
  • for the next N-k numbers you should add in the heap the tps[i] remove tps[i-k], and print (-heap[0])

Overall you get a O(N log(K)) algorithm, while what you use now is O(N*K). This will be very helpful if K is not small.

*Since the implementation of heap has the min(heap) in heap[0] as an invariant, if you add -value the -heap[0] will be the max(heap) as you want it.

pankgeorg
  • 123
  • 1
  • 9
  • 1
    This is better but not optimal, you can achieve amortized O(1) complexity for this operation. (See [ILoveCoding's answer](http://stackoverflow.com/a/27870655/2572431)) – augurar Jan 09 '15 at 23:28
0

pandas can do this pretty well:

import pandas as pd
df = pd.DataFrame(dict(data=[6, 9, 4, 7, 4, 1]))
df['running_max'] = pd.expanding_max(df.data)
df['rolling_max'] = pd.rolling_max(df.data, 3, min_periods=0)


print df
   data  running_max  rolling_max
0     6            6            6
1     9            9            9
2     4            9            9
3     7            9            9
4     4            9            7
5     1            9            7
acushner
  • 9,595
  • 1
  • 34
  • 34