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
numbers = map(int, f1.readline().split())next(f1)tof1.readline()...