Priority Queue in swift

Question

Ich versuche, eine Version von Dijkstra-Algorithmus zu implementieren, um die kürzeste Route für einen Bus von Anfang bis Ende zu finden. Unglücklicherweise kann ich keine Bibliothek oder eine andere Art finden, wie swift eine Art Prioritätswarteschlange bereitstellt, so dass es so aussieht, als müsste ich meine eigene schreiben.

Dies gesagt, kann mir jemand in die richtige Richtung zeigen, dies zu tun?

Derzeit mein Denken ist wie folgt:

eine Klasse schreiben, die die Priorität Array halten wird. In dieser Klasse gibt es eine Methode, die einen Wert erhält, ihn dem Priority-Array hinzufügt und ihn dann nach Priorität sortiert (in diesem Fall die Entfernung). Es wird auch eine get-Funktion geben, die das höchstpriore Element aus dem Array zurückgibt.

Ich würde gerne wissen, ob ich nah oder noch weit weg in meinem Verständnis einer Prioritätswarteschlange bin.

Vielen Dank.

EDIT:

Dies ist mein Code so weit. Scheint zu kurz und brutal ... Ich muss etwas in Bezug auf das Konzept vermissen.

var priorityQueue = Dictionary<String, Int>() 
var firstElement: String = "" 

func push(name: String, distance: Int) 
{ 
    priorityQueue[name] = distance 
    var myArr = Array(priorityQueue.keys) 
    var sortedKeys = sort(myArr) { 
     var obj1 = self.priorityQueue[$0] // get obj associated w/ key 1 
     var obj2 = self.priorityQueue[$1] // get obj associated w/ key 2 
     return obj1 > obj2 
    } 

    firstElement = myArr[0] 
    var tempPriorityQueue = Dictionary<String, Int>() 
    for val in myArr 
    { 
     tempPriorityQueue[val] = priorityQueue[val] 
    } 

    priorityQueue = tempPriorityQueue 
} 

func pop() -> String 
{ 
    priorityQueue.removeValueForKey(firstElement) 
} 

Answer 1

Schauen Sie sich den Code für "heapsort" an. Heapsort erstellt einen "Heap", bei dem es sich im Wesentlichen um eine Prioritätswarteschlange mit dem größten Element zuerst handelt. Anschließend wird das größte Element der heap = priority-Warteschlange wiederholt, an das Ende des Arrays verschoben und das zuvor letzte Arrayelement hinzugefügt die Prioritätswarteschlange.

Einfügen und Entfernen von Elementen in einer Prioritätswarteschlange muss ein O (log n) -Operation sein. Das ist der springende Punkt einer Prioritätswarteschlange. Der Aufruf von "sort" beim Hinzufügen eines Elements zur Prioritätswarteschlange ist absolut absurd und führt zu total Ihrer Leistung.

Answer 2

Möglicherweise interessieren Sie sich für zwei Open-Source-Projekte, die ich geschrieben habe. Die erste ist SwiftPriorityQueue: https://github.com/davecom/SwiftPriorityQueue

Ihre Implementierung einer Prioritätswarteschlange sortiert nach Push, der O (n lg n) ist. Die meisten Implementierungen einer Prioritätswarteschlange, einschließlich SwiftPriorityQueue, verwenden einen binären Heapspeicher als Sicherungsspeicher. Sie haben Push-Operationen, die in O (lg n) arbeiten und Pops, die auch in O (lg n) arbeiten. Daher sind Ihre Vermutungen richtig - Ihre aktuelle Implementierung ist wahrscheinlich nicht sehr performant (obwohl Pops technisch schneller sind).

Die zweite ist SwiftGraph: https://github.com/davecom/SwiftGraph

SwiftGraph umfasst Algorithmus eine Implementierung von Dijkstra.

Ich bin überrascht, dass keines dieser Projekte leichter zu finden war, da sie seit über einem Jahr und mäßig populär sind, aber basierend auf aktuellen Antworten auf diese Frage im letzten Jahr scheint es, dass ich an der Auffindbarkeit arbeiten muss .

Answer 3

Sie sollten Heap Sortierung für die Priorität verwenden. Ich denke, das ist optimal! Probieren Sie es auf dem Spielplatz aus!

import Foundation 
typealias PriorityDefinition<P> = (_ p1: P, _ p2: P) -> (Bool) 
class PriorityQueue<E, P: Hashable> { 
    var priDef: PriorityDefinition<P>! 
    var elemments = [P: [E]]() 
    var priority = [P]() 
    init(_ priDef: @escaping PriorityDefinition<P>) { 
     self.priDef = priDef 
    } 
    func enqueue(_ element: E!, _ priorityValue: P!) { 
     if let _ = elemments[priorityValue] { 
      elemments[priorityValue]!.append(element) 
     } else { 
      elemments[priorityValue] = [element] 
     } 
     if !priority.contains(priorityValue) { 
      priority.append(priorityValue) 
      let lastIndex = priority.count - 1 
      siftUp(0, lastIndex, lastIndex) 
     } 
    } 
    func dequeue() -> E? { 
     var result: E? = nil 
     if priority.count > 0 { 
      var p = priority.first! 
      if elemments[p]!.count == 1 { 
       if priority.count > 1 { 
        let _temp = priority[0] 
        priority[0] = priority[priority.count - 1] 
        priority[priority.count - 1] = _temp 
        p = priority.last! 
        siftDown(0, priority.count - 2) 
       } 
       result = elemments[p]!.removeFirst() 
       elemments[p] = nil 
       priority.remove(at: priority.index(of: p)!) 
      } else { 
       result = elemments[p]!.removeFirst() 
      } 
     } 
     return result 
    } 
    func siftDown(_ start: Int, _ end: Int) { 
     let iLeftChild = 2 * start + 1 
     if iLeftChild <= end { 
      var largestChild = priDef(priority[iLeftChild], priority[start]) ? iLeftChild : start 
      let iRightChild = 2 * start + 2 
      if iRightChild <= end { 
       if priDef(priority[iRightChild], priority[iLeftChild]) { 
        largestChild = iRightChild 
       } 
      } 
      if largestChild == start { 
       return 
      } else { 
       let _temp = priority[start] 
       priority[start] = priority[largestChild] 
       priority[largestChild] = _temp 
       siftDown(largestChild, end) 
      } 
     } 
    } 
    func siftUp(_ start: Int, _ end: Int, _ nodeIndex: Int) { 
     let parent = (nodeIndex - 1)/2 
     if parent >= start { 
      if priDef(priority[nodeIndex], priority[parent]) { 
       let _temp = priority[nodeIndex] 
       priority[nodeIndex] = priority[parent] 
       priority[parent] = _temp 
       siftUp(start, end, parent) 
      } else { 
       return 
      } 
     } 
    } 
    func isEmpty() -> Bool { 
     return priority.count == 0 
    } 
} 
let Q = PriorityQueue<Int, Int> { (p1: Int, p2: Int) -> (Bool) in 
    return p1 > p2 
} 
let n = 999 
for i in 0...n - 1 { 
    let start = NSDate().timeIntervalSince1970 
    Q.enqueue(i, i) 
    let end = NSDate().timeIntervalSince1970 
    print(end - start) 
}