Table des matières
Table des matières
Aperçu
Système de stationnement
Caractéristiques
Maison développement back-end Golang Algorithmes de planification d'ascenseur : FCFS, SSTF, SCAN et LOOK

Algorithmes de planification d'ascenseur : FCFS, SSTF, SCAN et LOOK

Oct 27, 2024 pm 08:31 PM

Comme je travaille avec Go depuis un certain temps, j'ai pensé que ce serait un défi amusant d'y implémenter quelques solutions classiques de conception de bas niveau.

Lors de la conception d'un système d'ascenseur, un aspect crucial est de savoir comment décider quel étage desservir ensuite, en particulier lorsque l'ascenseur a plusieurs demandes. La syntaxe simple et les performances de Go le rendent idéal pour modéliser de tels systèmes, j'ai donc décidé de créer des implémentations de base des algorithmes FCFS (First Come First Serve), SSTF (Shortest Seek Time First), SCAN et LOOK.

1. Premier arrivé, premier servi (FCFS)

J'ai commencé avec l'approche la plus simple : les demandes de service dans l'ordre dans lequel elles sont reçues. C'est facile à mettre en œuvre mais peut s'avérer inefficace si les demandes sont réparties sur plusieurs étages, ce qui entraîne un temps de trajet plus long.

func FCFS(currentFloor int, requests []int) []int {
    path := []int{}
    for _, floor := range requests {
        path = append(path, floor)
    }
    return path
}
Copier après la connexion

Dans FCFS, l'ascenseur se déplace simplement vers chaque étage demandé dans l'ordre donné.

2. Temps de recherche le plus court en premier (SSTF)

SSTF essaie de minimiser les déplacements en choisissant ensuite l'étage demandé le plus proche. Cela réduit le temps de trajet mais peut conduire à une « famine » pour les demandes lointaines si de nouvelles demandes plus proches continuent d'arriver.

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
}
Copier après la connexion

Cette fonction trouve à chaque fois l'étage le plus proche de l'étage actuel, mettant à jour la position de l'ascenseur après chaque déplacement.

3. SCAN (algorithme d'ascenseur)

Dans SCAN, l'ascenseur se déplace dans une direction, répondant à toutes les demandes dans cette direction jusqu'à ce qu'il atteigne la fin, puis s'inverse. Cette approche est plus juste que SSTF car elle réduit la famine.

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
}
Copier après la connexion

Cette fonction divise les demandes en étages au-dessus et en dessous de la position actuelle. Il dessert tous les étages vers le haut, puis vers le bas.

4. REGARDEZ

LOOK est une légère variation de SCAN. Au lieu d'aller jusqu'au bout, l'ascenseur inverse la direction à la dernière demande dans chaque direction. Cela permet de gagner du temps en s'arrêtant là où finissent les demandes, et non aux limites physiques.

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
}
Copier après la connexion

Semblable au SCAN, cette approche ne va que jusqu'à la dernière requête dans chaque direction.

Chaque algorithme a ses compromis :

  • FCFS : Simple mais peut être inefficace.
  • SSTF : optimise pour les étages les plus proches mais peut affamer les demandes lointaines.
  • SCAN : Plus juste et efficace, minimisant les changements de direction.
  • REGARDER : Gain de temps supplémentaire en s'arrêtant à la dernière demande.

Le bon choix dépend des exigences spécifiques en matière d'efficacité, d'équité et de temps de réponse du système.

Pour une implémentation complète à l'aide de l'algorithme LOOK, reportez-vous à mon dépôt github :

Elevator Scheduling Algorithms: FCFS, SSTF, SCAN, and LOOK l'arbre à sel / conception-golang de bas niveau

Solutions aux problèmes de conception de systèmes de bas niveau à Golang

Conception de systèmes de bas niveau dans Go

Bienvenue dans le référentiel Conception de systèmes de bas niveau dans Go ! Ce référentiel contient divers problèmes de conception de systèmes de bas niveau et leurs solutions implémentées dans Go. L'objectif principal est de démontrer la conception et l'architecture des systèmes à travers des exemples pratiques.

Table des matières

  • Aperçu
  • Système de stationnement
  • Système d'ascenseur

Aperçu

La conception de systèmes de bas niveau implique de comprendre les concepts fondamentaux de l'architecture système et de concevoir des systèmes évolutifs, maintenables et efficaces. Ce référentiel tentera de couvrir les solutions de divers problèmes et scénarios utilisant Go.

Système de stationnement

Le premier projet de ce référentiel est un Système de parking. Ce système simule un parking où les véhicules peuvent être garés et déchargés. Cela démontre :

  • Modèle de conception Singleton pour la gestion de l'instance de parking.
  • Manipulation de différents types de véhicules (par exemple, voitures, camions).
  • Gestion des espaces de stationnement sur plusieurs étages.
  • Traitement des paiements pour les véhicules stationnés.

Caractéristiques

  • Ajouter et supprimer des véhicules du…


Voir sur GitHub


Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Tutoriel Java
1653
14
Tutoriel PHP
1251
29
Tutoriel C#
1224
24
Objectif de Golang: Construire des systèmes efficaces et évolutifs Objectif de Golang: Construire des systèmes efficaces et évolutifs Apr 09, 2025 pm 05:17 PM

GO Language fonctionne bien dans la construction de systèmes efficaces et évolutifs. Ses avantages incluent: 1. Haute performance: compilé en code machine, vitesse de course rapide; 2. Programmation simultanée: simplifier le multitâche via les goroutines et les canaux; 3. Simplicité: syntaxe concise, réduction des coûts d'apprentissage et de maintenance; 4. Plate-forme multipliée: prend en charge la compilation multiplateforme, déploiement facile.

Golang et C: concurrence vs vitesse brute Golang et C: concurrence vs vitesse brute Apr 21, 2025 am 12:16 AM

Golang est meilleur que C en concurrence, tandis que C est meilleur que Golang en vitesse brute. 1) Golang obtient une concurrence efficace par le goroutine et le canal, ce qui convient à la gestion d'un grand nombre de tâches simultanées. 2) C Grâce à l'optimisation du compilateur et à la bibliothèque standard, il offre des performances élevées près du matériel, adaptées aux applications qui nécessitent une optimisation extrême.

Golang vs Python: différences et similitudes clés Golang vs Python: différences et similitudes clés Apr 17, 2025 am 12:15 AM

Golang et Python ont chacun leurs propres avantages: Golang convient aux performances élevées et à la programmation simultanée, tandis que Python convient à la science des données et au développement Web. Golang est connu pour son modèle de concurrence et ses performances efficaces, tandis que Python est connu pour sa syntaxe concise et son écosystème de bibliothèque riche.

Golang vs Python: performance et évolutivité Golang vs Python: performance et évolutivité Apr 19, 2025 am 12:18 AM

Golang est meilleur que Python en termes de performances et d'évolutivité. 1) Les caractéristiques de type compilation de Golang et le modèle de concurrence efficace le font bien fonctionner dans des scénarios de concurrence élevés. 2) Python, en tant que langue interprétée, s'exécute lentement, mais peut optimiser les performances via des outils tels que Cython.

La course de performance: Golang vs C La course de performance: Golang vs C Apr 16, 2025 am 12:07 AM

Golang et C ont chacun leurs propres avantages dans les compétitions de performance: 1) Golang convient à une concurrence élevée et à un développement rapide, et 2) C fournit des performances plus élevées et un contrôle fin. La sélection doit être basée sur les exigences du projet et la pile de technologie d'équipe.

Impact de Golang: vitesse, efficacité et simplicité Impact de Golang: vitesse, efficacité et simplicité Apr 14, 2025 am 12:11 AM

GOIMIMPACTSDEVENCEMENTSPOSITIVEMENTS INSPECT, EFFICACTION ET APPLICATION.1) VITESSE: GOCOMPILESQUICKLYANDRUNSEFFIÉMENT, IDEALFORLARGEPROROSTS.2) Efficacité: ITSCOMPEHENSIVESTANDARDLIBRARYREDUCEEXTERNEDENDENCES, EnhancingDevelovefficiency.3) Simplicité: Simplicité: Implicité de la manière

C et Golang: Lorsque les performances sont cruciales C et Golang: Lorsque les performances sont cruciales Apr 13, 2025 am 12:11 AM

C est plus adapté aux scénarios où le contrôle direct des ressources matérielles et une optimisation élevée de performances sont nécessaires, tandis que Golang est plus adapté aux scénarios où un développement rapide et un traitement de concurrence élevé sont nécessaires. 1.C's Avantage est dans ses caractéristiques matérielles proches et à des capacités d'optimisation élevées, qui conviennent aux besoins de haute performance tels que le développement de jeux. 2. L'avantage de Golang réside dans sa syntaxe concise et son soutien à la concurrence naturelle, qui convient au développement élevé de services de concurrence.

Golang et C: les compromis en performance Golang et C: les compromis en performance Apr 17, 2025 am 12:18 AM

Les différences de performance entre Golang et C se reflètent principalement dans la gestion de la mémoire, l'optimisation de la compilation et l'efficacité du temps d'exécution. 1) Le mécanisme de collecte des ordures de Golang est pratique mais peut affecter les performances, 2) la gestion manuelle de C et l'optimisation du compilateur sont plus efficaces dans l'informatique récursive.

See all articles