Aufzugsplanungsalgorithmen: FCFS, SSTF, SCAN und LOOK

Da ich schon seit einiger Zeit mit Go arbeite, dachte ich, es wäre eine lustige Herausforderung, ein paar klassische Low-Level-Designlösungen darin zu implementieren.

Beim Entwurf eines Aufzugssystems ist ein entscheidender Aspekt die Entscheidung, welche Etage als nächstes bedient werden soll, insbesondere wenn der Aufzug mehrere Anforderungen hat. Die unkomplizierte Syntax und Leistung von Go machen es ideal für die Modellierung solcher Systeme. Deshalb habe ich mir vorgenommen, grundlegende Implementierungen der Algorithmen FCFS (First Come First Serve), SSTF (Shortest Seek Time First), SCAN und LOOK zu erstellen.

1. Wer zuerst kommt, mahlt zuerst (FCFS)

Ich habe mit dem einfachsten Ansatz begonnen: Serviceanfragen in der Reihenfolge ihres Eingangs. Es ist einfach umzusetzen, kann aber ineffizient sein, wenn die Anfragen über mehrere Etagen verteilt sind, was zu mehr Reisezeit führt.

func FCFS(currentFloor int, requests []int) []int {
    path := []int{}
    for _, floor := range requests {
        path = append(path, floor)
    }
    return path
}

In FCFS fährt der Aufzug einfach in der angegebenen Reihenfolge zu jeder gewünschten Etage.

2. Kürzeste Suchzeit zuerst (SSTF)

SSTF versucht, den Reiseaufwand zu minimieren, indem es als nächstes die nächstgelegene gewünschte Etage auswählt. Dadurch wird die Reisezeit verkürzt, es kann jedoch zu einem „Aushungern“ weit entfernter Anfragen führen, wenn immer wieder neue nähere Anfragen eingehen.

func SSTF(currentFloor int, requests []int) []int {
    path := []int{}
    remaining := append([]int{}, requests...)

    for len(remaining) > 0 {
        closestIdx := 0
        minDistance := abs(currentFloor - remaining[0])

        for i, floor := range remaining {
            distance := abs(currentFloor - floor)
            if distance < minDistance {
                closestIdx = i
                minDistance = distance
            }
        }

        currentFloor = remaining[closestIdx]
        path = append(path, currentFloor)
        remaining = append(remaining[:closestIdx], remaining[closestIdx+1:]...)
    }
    return path
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Diese Funktion findet jedes Mal die Etage, die der aktuellen Etage am nächsten liegt, und aktualisiert die Position des Aufzugs nach jeder Bewegung.

3. SCAN (Aufzugsalgorithmus)

Beim SCAN bewegt sich der Aufzug in eine Richtung, bedient alle Anfragen in dieser Richtung, bis er das Ende erreicht, und fährt dann um. Dieser Ansatz ist fairer als SSTF, weil er den Hunger reduziert.

func SCAN(currentFloor, maxFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

Diese Funktion teilt Anfragen in Stockwerke oberhalb und unterhalb der aktuellen Position auf. Es bedient alle Etagen nach oben und dann nach unten.

4. SCHAU

LOOK ist eine leichte Variation von SCAN. Anstatt bis zum Ende zu fahren, kehrt der Aufzug bei der letzten Aufforderung in jede Richtung die Richtung um. Es spart Zeit, da dort angehalten wird, wo die Anfragen enden, und nicht an den physischen Grenzen.

func LOOK(currentFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

Ähnlich wie bei SCAN bewegt sich dieser Ansatz nur bis zur letzten Anfrage in jede Richtung.

Jeder Algorithmus hat seine Kompromisse:

• FCFS: Einfach, kann aber ineffizient sein.
• SSTF: Optimiert für nächstgelegene Stockwerke, kann aber weit entfernte Anfragen unterdrücken.
• SCAN: Gerechter und effizienter, Richtungsänderungen werden minimiert.
• SCHAUEN: Spart zusätzliche Zeit, indem bei der letzten Anfrage angehalten wird.

Die richtige Wahl hängt von den spezifischen Anforderungen an Effizienz, Fairness und Reaktionszeit im System ab.

Eine vollständige Implementierung mit dem LOOK-Algorithmus finden Sie in meinem Github-Repo:

thesaltree / Low-Level-Design-Golang

Lösungen für Low-Level-Systemdesignprobleme in Golang

Low-Level-Systemdesign in Go

Willkommen im Repository Low-Level-Systemdesign in Go! Dieses Repository enthält verschiedene Low-Level-Systemdesignprobleme und ihre in Go implementierten Lösungen. Das primäre Ziel besteht darin, den Entwurf und die Architektur von Systemen anhand praktischer Beispiele zu demonstrieren.

Inhaltsverzeichnis

• Übersicht
• Parkplatzsystem
• Aufzugssystem

Übersicht

Systemdesign auf niedriger Ebene beinhaltet das Verständnis der Kernkonzepte der Systemarchitektur und das Entwerfen skalierbarer, wartbarer und effizienter Systeme. In diesem Repository wird versucht, Lösungen für verschiedene Probleme und Szenarien mit Go abzudecken.

Parkplatzsystem

Das erste Projekt in diesem Repository ist ein Parkplatzsystem. Dieses System simuliert einen Parkplatz, auf dem Fahrzeuge ein- und ausgeparkt werden können. Es zeigt:

• Singleton-Entwurfsmuster zur Verwaltung der Parkplatzinstanz.
• Umgang mit verschiedenen Fahrzeugtypen (z. B. Pkw, Lkw).
• Parkplatzmanagement über mehrere Etagen hinweg.
• Zahlungsabwicklung für geparkte Fahrzeuge.

Funktionen

• Fahrzeuge hinzufügen und daraus entfernen...

Auf GitHub ansehen

Das obige ist der detaillierte Inhalt vonAufzugsplanungsalgorithmen: FCFS, SSTF, SCAN und LOOK. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!