Python- Algorithmic Statement

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 wil

Solution 1:

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,

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

is slightly more efficient.

Solution 2:

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:

• Initilizeq 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(xforx in n ifx >= n[0])
    res = [q[0]]
    for i in xrange(w, len(nums)):
        while len(q) > 0andq[0] <= i - w:
            q.popleft()
        while len(q) > 0and 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:

>>>defrolling_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