Warteschlange von Strukturen in Go

Question

Ich habe gelernt Go, und ich machte ein BFS-Puzzle mit ihm. Die Warteschlange Implementierung entschied ich mich auf ist:

//define the queue for our BFS algo as frontier. 
type frontier struct { 
    queue []*graphNode 
} 

func (F *frontier) buildFrontier() { 
    F.queue = make([]*graphNode, 0, 1000) 
} 

func (F *frontier) pop() (g *graphNode) { 
    if F.isEmpty() { 
     panic("pop on empty queue!") 
    } 
    temp := F.queue[0] 
    F.queue = F.queue[1:] 
    return temp 
} 

func (F *frontier) push(g *graphNode) { 
    F.queue = append(F.queue, g) 
} 

func (F *frontier) isEmpty() bool { 
    return len(F.queue) == 0 
} 

Ich habe 2 Fragen:

1. Ist das eine gute Umsetzung? Die Dokumentation zu Warteschlangen ist spärlich, und im Allgemeinen gibt es einige alte Einträge über Vektoren, und eine Liste scheint zu viel Overhead zu haben (nicht dass es für meinen Fall wichtig ist, aber ich versuche es so gut wie möglich zu machen) .

2. Warum muss der Aufruf eines Objekts (in diesem Fall der Strukturzeiger F * frontier) ein Zeiger sein? Es scheint, wie die Art und Weise die Syntax funktioniert, dass es ein Standard für einen Zeiger sein sollte, nicht explizit (also warum sollten Sie immer keinen Zeiger in diesen Fällen verwenden?)

KREIS VERSION MODIFIED:

//define the queue for our BFS algo as frontier. 
type frontier struct { 
    queue    []*graphNode 
    size, head, capacity int 
} 

func (F *frontier) buildFrontier() { 
    F.capacity = 1 
    F.queue = make([]*graphNode, F.capacity) 
    F.size = 0 
    F.head = 0 
} 

func (F *frontier) pop() (g *graphNode) { 
    if F.isEmpty() { 
     panic("pop on empty queue!") 
    } 
    F.size = (F.size - 1) 
    temp := F.queue[F.head] 
    F.head = (F.head + 1) % F.capacity 
    return temp 
} 

func (F *frontier) push(g *graphNode) { 
    if F.isFull() { 
     newSlice := make([]*graphNode, F.capacity*2) 
     copy(newSlice, F.queue) 
     F.queue = newSlice 
     F.capacity *= 2 
    } 
    F.queue[(F.head+F.size)%F.capacity] = g 
    F.size = (F.size + 1) 
} 

func (F *frontier) isEmpty() bool { 
    return F.size == 0 
} 
func (F *frontier) isFull() bool { 
    return F.size == F.capacity 
} 

Answer 1

1. es sieht aus wie Ihre Implementierung arbeiten, aber es wird ein wenig ineffizient am Ende wird. Zu Beginn ist queue ein Slice mit der Kapazität 1000. Das bedeutet, dass das zugrunde liegende Array 1000 Elemente enthalten kann. Jedes Mal, wenn Sie pop aufrufen, verschieben Sie den Anfang der Warteschlange um ein Element weiter unten in diesem Array und reduzieren so die Kapazität um 1. Schließlich ist die Kapazität nicht ausreichend, um ein neues Element zu speichern, wenn Sie push aufrufen nicht viele (oder irgendwelche) Elemente in der Warteschlange sein. Dies führt dazu, dass ein neues Array zugewiesen wird, wenn append aufgerufen wird. Unabhängig davon, was das Muster der Aufrufe push und pop ist, wird das Array wiederholt neu zugewiesen, auch wenn es nie 1000 Elemente enthält. Ich würde vorschlagen, dafür eine verkettete Liste zu verwenden, entweder die im Paket list oder eines Ihrer eigenen Design.

2. Der Empfänger muss ein Zeiger sein, wenn die Funktion den Wert des Empfängers ändert oder wenn das Empfängerobjekt an anderen Stellen verwendet wird und der Wert geteilt werden muss. Andernfalls muss es kein Zeiger sein. Vielleicht möchten Sie den Empfänger trotzdem zu einem Zeiger machen, wenn der Wert groß ist, damit er nicht kopiert werden muss. (Der Empfänger verhält sich wie jeder andere Funktionsparameter und die gleichen Überlegungen gelten.)