Minimum und Maximum des beweglichen Fensters, bessere Implementierung?

Question

Ich versuche, ein Min-Max eines bewegten Fensters mit Hilfe von Warteschlangen zu finden. Ich konnte eine Lösung schaffen, aber das fühlt sich sehr langsam an.

Hier ist meine Lösung:

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

Es hängt davon ab, wie Sie Ihre Warteschlange aufgebaut ist und bevölkert, und wie groß es ist. Kurz gesagt, Sie können die Suche nach Min/Max schneller durchführen, aber das Hinzufügen von Elementen zur Warteschlange wird langsamer oder es entstehen Kosten im Voraus.

Was Sie tun, ist linear, das ist so gut wie Sie mit einer linearen Datenstruktur tun können, aber Sie könnten es in einer idiomatischen Art und Weise schreiben (und ich bin mir nicht sicher, was ist der Deal mit dequeue in der Anfang, und was Sie passieren erwarten, wenn die Warteschlangengröße kleiner oder größer als der Parameter ist):

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) 
    } 

Dies geht auch davon aus, dass es keine Rennen (niemand ist, Daten zu der Warteschlange hinzugefügt, während Sie es durchqueren) . All diese Dinge wären viel einfacher zu verstehen, wenn Sie den funktionalen Ansatz, keine veränderlichen Strukturen zu verwenden, übernehmen, es sei denn, Sie müssen es unbedingt tun.