Find max (and min) on a move interval with python

Question

I have an array like

[5.5, 6.0, 6.0, 6.5, 6.0, 5.5, 5.5, 5.0, 4.5]. 

all numbers of this array differ by 0.5, and the maximum difference of two consecutive numbers is also 0.5 (they can be the same, as in the example). and there is a moving interval or field that spans, for example, 3 consecutive numbers, for example:

[(5.5, 6.0, 6.0), 6.5, 6.0, 5.5, 5.5, 5.0, 4.5]  # min: 5.5, max: 6.0

and the field moves to the right in turn:

[5.5, (6.0, 6.0, 6.5), 6.0, 5.5, 5.5, 5.0, 4.5]  # min: 6.0, max: 6.5

[5.5, 6.0, (6.0, 6.5, 6.0), 5.5, 5.5, 5.0, 4.5]  # min: 6.0, max: 6.5

The question arises: how can I find the min and max numbers inside the field for each time window?

I can handle this when the block and array size is small, as in this example, but I need to apply it to an array size of 100000 and a box size of 10000. Using my method (I calculate each max and minimum using a for-loop for each window of time passes), it took too much time (I have another 100 arrays and need to be run many times). There is some time limit, so I need to run it as one calculation in 0.5 seconds.

Answer 1

Take a look at rolling windows from pandas:

>>> import pandas as pd
>>> L = [5.5, 6.0, 6.0, 6.5, 6.0, 5.5, 5.5, 5.0, 4.5]
>>> a = pd.DataFrame(L)
>>> pd.rolling_max(a, 3)
     0
0  NaN
1  NaN
2  6.0
3  6.5
4  6.5
5  6.5
6  6.0
7  5.5
8  5.5
>>> pd.rolling_min(a, 3)
     0
0  NaN
1  NaN
2  5.5
3  6.0
4  6.0
5  5.5
6  5.5
7  5.0
8  4.5

Answer 2

, O (log (window_size)) (. ). @wim , @adamax :

, push_rear(), pop_front() get_min() -

.

100000 1000 0,6 60 .

class MinMaxStack(object):

    def __init__(self):
        self.stack = []

    def push(self,val):
        if not self.stack:
            self.stack = [(val,val,val)]
        else:
            _,minimum,maximum = self.stack[-1]
            if val < minimum:
                self.stack.append((val,val,maximum))
            elif val > maximum:
                self.stack.append((val,minimum,val))
            else:
                self.stack.append((val,minimum,maximum))

    def pop(self):
        return self.stack.pop()

    def get_minimax(self):
        return self.stack[-1][1:]

    def __len__(self):
        return len(self.stack)

class RollingWindow(object):

    def __init__(self):
        self.push_stack = MinMaxStack()
        self.pop_stack = MinMaxStack()

    def push_only(self,o):
        self.push_stack.push(o)

    def push_and_pop(self,o):
        self.push_stack.push(o)
        if not self.pop_stack:
            for i in range(len(self.push_stack.stack)-1):
                self.pop_stack.push(self.push_stack.pop()[0])
            self.push_stack.pop()
        else:
            self.pop_stack.pop()

    def get_minimax(self):
        if not self.pop_stack:
            return self.push_stack.get_minimax()
        elif not self.push_stack:
            return self.pop_stack.get_minimax()
        mn1,mx1 = self.pop_stack.get_minimax()
        mn2,mx2 = self.push_stack.get_minimax()
        return min(mn1,mn2),max(mx1,mx2)



import time
import random
window = 10000
test_length = 100000
data = [random.randint(1,100) for i in range(test_length)]

s = time.time()

wr = RollingWindow()
answer1 = []
for i in range(test_length):
    if i < window:
        wr.push_only(data[i])
    else:
        wr.push_and_pop(data[i])
    answer1.append(wr.get_minimax())

print(s-time.time())

s = time.time()
answer2 = []
for i in range(test_length):
    if i+1 < window:
        current_window = i+1
    else:
        current_window = window
    answer2.append((min(data[i+1-current_window:i+1]),max(data[i+1-current_window:i+1])))

print(s-time.time())

if answer1 != answer2:
    print("Test Fail")

. python, . , . . , . , collections.deque 0,32 .

, C Cython ( ), .

Answer 3

l = [5.5, 6.0, 6.0, 6.5, 6.0, 5.5, 5.5, 5.0, 4.5]

windoSize = 3

for i in range(0,len(l)-windowSize+1):

    print max(l[i:i+windoSize])

:

6.0
6.5
6.5
6.5
6.0
5.5
5.5

Answer 4

, pandas, .

, , , . , , .

. , , 2 , .

, , , .

def updateMinMaxValues(minVal,maxVal,val):
    if val < minVal:
        minVal = val
    if val > maxVal:
        maxVal= val
    return minVal,maxVal

values = [5.5, 6.0, 6.0, 6.5, 6.0, 5.5, 5.5, 5.0, 4.5]
windowSize = 3
minVal,maxVal = min(values[:windowSize]),max(values[:windowSize])

print(minVal,maxVal)
for stepIndex in range(windowSize,len(values)):
    oldVal,newVal = values[stepIndex-windowSize],values[stepIndex]
    if oldVal == minVal:
        minVal = min(values[stepIndex-windowSize+1:stepIndex+1])
    if oldVal == maxVal:
        maxVal = max(values[stepIndex-(windowSize)+1:stepIndex+1])
    minVal,maxVal = updateMinMaxValues(minVal,maxVal,newVal)
    print(minVal,maxVal)

:

5.5 6.0
6.0 6.5
6.0 6.5
5.5 6.5
5.5 6.0
5.0 5.5
4.5 5.5

Answer 5

, .

, - . , . O (log (window_size)) .

wim , O (1), : , push_rear(), pop_front() get_min() -

, min max, .

:

, , . [O (log (window_size))], .

Python heapq Python. , . , , . , ( ) , .

, , :

http://code.activestate.com/recipes/522995-priority-dict-a-priority-queue-with-updatable-prio/

You will need to eliminate the ambiguity of the entries with the same value in the dictionary or save several values ​​for each key so that you can find all the instances when the time comes to delete them.