минимальное и максимальное движущееся окно, лучшая реализация?

Question

Я пытаюсь найти min-max движущегося окна, используя очереди. Я смог создать решение, но это очень медленно.

Вот мое решение:

def min_max(value:T, windowSize: Int):(T,T) = { 
    val queue = new scala.collection.mutable.Queue[A]() //I added the creation of this queue here for you to see 
    if(queue.size == windowSize) queue.dequeue 
    queue.enqueue(value)  
    var min = queue.head 
    var max = queue.head 
    for(i <- queue) { 
    if(i<min) min = i 
    if(i>max) max = i 
    } 
    (min, max)     // returns the min and max in a tuple 
} 

Answer 1

Это зависит от того, как устроена ваша очередь и заселена, и насколько она велика. Короче говоря, вы можете ускорить сканирование с минимальным/максимальным ускорением, но это приведет к замедлению добавления элементов в очередь или повлечет за собой некоторые первоначальные затраты.

То, что вы делаете, является линейным, что примерно так же хорошо, как вы можете сделать с линейной структурой данных, но вы можете написать его более идиоматическим образом (а также я не уверен, что такое сделка с dequeue в начало, и что вы ожидаете произойдет, когда размер очереди меньше или больше, чем параметр):

queue 
    .take(windowSize) 
    .foldLeft(Option.empty[A] -> Option.empty[A]) { 
    case ((None, None), x) => Some(x) -> Some(x) 
    case ((x, y), z) => x.map(x min z) -> y.map(y max z) 
    } 

Это также подразумевает, что нет никакой гонки (никто не добавляет данные в очередь, пока вы обходе его) , Все это было бы намного легче рассуждать, если бы вы применили функциональный подход, не используя изменчивые структуры, если вам это не нужно.