Coda prioritaria in swift

Question

Sto cercando di implementare una versione di Dijkstra Algorithm per trovare il percorso più breve per un autobus da percorrere dall'inizio alla fine. Sfortunatamente, non riesco a trovare una libreria o altro modo in cui swift fornisca un tipo di coda di priorità, quindi sembra che dovrò codificarmi da solo.

Detto questo, qualcuno può indicarmi la direzione giusta per farlo?

Attualmente il mio pensiero è il seguente:

scrivere una classe che conterrà la matrice di priorità. In questa classe ci sarà un metodo che riceve un valore, lo aggiunge alla matrice di priorità e poi lo ordina in base alla priorità (in questo caso, la distanza). Ci sarà anche una funzione get che restituisce l'elemento con la priorità più alta dall'array.

Mi piacerebbe sapere se sono vicino o ancora lontano dalla mia comprensione di una coda di priorità.

Grazie.

EDIT:

Questo è il mio codice finora. Sembra troppo breve e brutale ... Mi manca qualcosa in termini di concetto.

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

Controllare il codice per "heapsort". Heapsort crea un "heap" che è fondamentalmente una coda di priorità con l'elemento più grande prima, quindi espelle ripetutamente l'elemento più grande della coda heap = priority, lo sposta alla fine dell'array e aggiunge l'ultimo elemento dell'array a la coda di priorità.

L'inserimento e la rimozione di elementi in una coda di priorità devono essere un'operazione O (log n). Questo è il punto principale di una coda di priorità. Chiamare "ordina" mentre si aggiunge un elemento alla coda di priorità è assolutamente assurdo e sta andando a a uccidere completamente le prestazioni.

Answer 2

Potresti essere interessato a guardare due progetti open source che ho creato. Il primo è SwiftPriorityQueue: https://github.com/davecom/SwiftPriorityQueue

L'implementazione di una coda di priorità ordina su push che è O (n lg n). La maggior parte delle implementazioni di una coda di priorità, incluso SwiftPriorityQueue, utilizza un heap binario come backing store. Hanno operazioni push che operano in O (lg n) e pop che operano anche in O (lg n). Quindi i tuoi sospetti sono corretti - è improbabile che la tua implementazione attuale sia molto performante (anche se i pop sono tecnicamente più veloci).

Il secondo è SwiftGraph: https://github.com/davecom/SwiftGraph

SwiftGraph include un'implementazione dell'algoritmo di Dijkstra.

Sono sorpreso che nessuno di questi progetti è stato più facile da trovare poiché sono usciti da più di un anno e moderatamente popolari, ma sulla base delle risposte attuali a questa domanda nell'ultimo anno, sembra che io debba lavorare sulla rilevabilità .

Answer 3

È necessario utilizzare heap sort per la priorità. Penso che sia ottimale! Provalo nel parco giochi!

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