Python- Algorithmic statement

Question

I want to write a program which does the follows : -

Sample Input:

3
10 4 18 2 6 19 24 1 20

Expected Output:

4 2 2 2 6 1 1

The input will from a file in which the first line will contain the window size N, the second line will contain a stream of numbers separated by space. You need to output the smallest numbers in each window separated by space.

This is what I wrote:-

with open ("file") as f1:
    n = int(f1.readline())
    numbers = f1.readline()

# converting the string of numbers into a list
numbers_list = map(int,numbers[:-1].split(' ')) 

# getting all the sub-lists of size n from the numbers_list and printing their respective minimum elements.
print [min(numbers_list[i:i+n]) for i in xrange(len(numbers_list)-n+1)] 

My o/p

[4, 2, 2, 2, 6, 1, 1]

Is there some better solution than this? Any optimized version of this solution.

Answer 1

Here's some kind of optimization. Main idea is not to scan window for each index, but to maintain a sorted double ended queue (collections.deque), let's call it q, and remove unneseccary elements while traversing through original list. This queue remains sorted while traversing, so first element is always minimum, see algorithm below:

Algorithm:

• Initilize q with indexes of sorted first w (window length) elements of list, in OP case this would be [1, 0, 2] (because first 3 elements sorted are [4, 10, 18], so we just need to take indexes of these elements). I've used numpy.argsort for this task.
• Remove all indexes which are less then index of minimum element of q (we don't need it, because elements with these indexes can't be mins in any new window). So now we have [1, 2].
• Now iterate over remaining indexes, for each index:
  • Remove indexes from the left end of q if it's not in current window (so we get rid of previous minimum elements if they are outside of the current window).
  • Remove indexes from the right end of q if elements on these indexes are greater that element with current index.
  • Add q[0] to resulting list res of indexes.
• Return elements with indexes from res.

Note that each element added and removed from the q only once, so amortized complexity is O(N) where N is size of initial array/list. The simple algorithm counting min for each window would be O(NW) where W is window size.

Code:

def rolling_min(nums, w):
    n = np.argsort(nums[:w])
    q = deque(x for x in n if x >= n[0])
    res = [q[0]]
    for i in xrange(w, len(nums)):
        while len(q) > 0 and q[0] <= i - w:
            q.popleft()
        while len(q) > 0 and nums[q[-1]] > nums[i]:
            q.pop()
        q.append(i)
        res.append(q[0])
    return [nums[i] for i in res]

Tests:

May be my code could be optimized even further, here's some tests, my code works 10 times slower than simple list comprehension on OP data, but it works 10 times faster on larger list and larger window:

>>> def rolling_min1(nums, w):
...     return [min(nums[x:x + w]) for x in xrange(len(nums) - (w - 1))]
>>> rolling_min2 = rolling_min

# OP data, small list, small window
>>> nums = numbers_list
>>> w = 3
>>> timeit('r = rolling_min1(nums, w)', 'from __main__ import nums, w, rolling_min1', number=100)
0.0005016330251237378
>>> timeit('r = rolling_min2(nums, w)', 'from __main__ import nums, w, rolling_min2', number=100)
0.004806720447959378

# Large list, large window
>>> nums = np.random.randint(0, 100, 10000)
>>> w = 100
>>> timeit('r = rolling_min1(nums, w)', 'from __main__ import nums, w, rolling_min1', number=100)
13.711818511466845
>>> timeit('r = rolling_min2(nums, w)', 'from __main__ import nums, w, rolling_min2', number=100)
1.3878068031772273

Answer 2

map(min, [nums[x:x+window] for x in xrange(len(nums)-(window-1))])

However, this creates an intermediate list, so:

[min(nums[x:x+window]) for x in xrange(len(nums)-(window+1))] 

is actually better, which is what you currently have.

There is a more time efficient way, however, it would be more code. Once you have the min-value for a window, all you're doing is looking at the next slot, so all you need to do is compare the min value from the previous (window-1) elements to the next value. Whichever is smaller will be the next number in your results list. Repeat.

For example, if you have a four element list and your window is size 3. The first value in your results list will be the minimum of the first three elements, and the second value in your results list will be the minimum of the last three elements.

There's a two element overlap there. So you can save the minimum value of the last window-1 elements and compare that to the next value in the list to get the min value for the next window. Repeat.

With respect to the file handling,

with open ("file") as f1:
    n = int(f1.readline())
    numbers_list = map(int, f1.readline().split(' ')) 

is slightly more efficient.