エレベーター スケジュール アルゴリズム: FCFS、SSTF、SCAN、および LOOK

私はかなり長い間 Go を使って働いてきたので、いくつかの古典的な低レベル設計ソリューションを Go に実装するのは楽しい挑戦になるだろうと思いました。

エレベーター システムを設計する場合、特にエレベーターに複数のリクエストがある場合に、次にどの階にサービスを提供するかをどのように決定するかが重要な側面の 1 つです。 Go の単純な構文とパフォーマンスは、このようなシステムのモデリングに最適であるため、FCFS (First Come First Serve)、​​SSTF (Shortest Seek Time First)、SCAN、および LOOK アルゴリズムの基本実装を作成することにしました。

1. 先着順 (FCFS)

私は最も単純なアプローチ、つまりサービスリクエストを受信した順に開始しました。実装は簡単ですが、リクエストが複数のフロアに分散すると非効率になり、移動時間の増加につながる可能性があります。

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

FCFS では、エレベーターは指定された順序で要求された各フロアに移動するだけです。

2. 最短シーク時間優先 (SSTF)

SSTF は、次に要求された最も近いフロアを選択することで移動を最小限に抑えようとします。これにより移動時間が短縮されますが、新しい近くのリクエストが継続的に来ると、遠くのリクエストが「飢餓」になる可能性があります。

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
}

この関数は、現在のフロアに最も近いフロアを毎回検索し、移動するたびにエレベーターの位置を更新します。

3. SCAN（エレベーターアルゴリズム）

SCAN では、エレベーターは一方向に移動し、終点に到達するまでその方向のすべてのリクエストに対応し、その後逆転します。このアプローチは飢餓を減らすため、SSTF よりも公平です。

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
}

この機能は、リクエストを現在位置の上下のフロアに分割します。すべてのフロアを上向きに、次に下向きにサービスを提供します。

4.見てください

LOOK は SCAN のわずかなバリエーションです。エレベーターは最後まで進むのではなく、各方向の最後の要求で方向を反転します。物理的な限界ではなく、リクエストが終了するところで停止することで時間を節約します。

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
}

SCAN と同様に、このアプローチは各方向の最後のリクエストまでしか移動しません。

各アルゴリズムにはトレードオフがあります:

• FCFS: シンプルですが非効率になる可能性があります。
• SSTF: 最も近いフロアを最適化しますが、遠くのリクエストを枯渇させる可能性があります。
• SCAN: より公平かつ効率的で、方向の変更を最小限に抑えます。
• LOOK: 最後のリクエストで停止することで、さらに時間を節約します。

正しい選択は、システムの効率、公平性、応答時間に関する特定の要件によって異なります。

LOOK アルゴリズムを使用した完全な実装については、私の github リポジトリを参照してください:

テサルツリー / 低レベル設計-golang

Golang での低レベルのシステム設計問題の解決策

Go での低レベルのシステム設計

Go での低レベル システム設計 リポジトリへようこそ!このリポジトリには、Go で実装されたさまざまな低レベルのシステム設計の問題とその解決策が含まれています。主な目的は、実際の例を通じてシステムの設計とアーキテクチャを実証することです。

目次

• 概要
• 駐車場システム
• エレベーターシステム

概要

低レベルのシステム設計には、システム アーキテクチャの中核概念を理解し、拡張性、保守性、効率性の高いシステムを設計することが含まれます。このリポジトリは、Go を使用したさまざまな問題やシナリオの解決策をカバーしようとします。

駐車場システム

このリポジトリの最初のプロジェクトは、駐車場システムです。このシステムは、車両を駐車および駐車解除できる駐車場をシミュレートします。以下を示します:

• 駐車場インスタンスを管理するためのシングルトン設計パターン。
• さまざまな種類の車両 (乗用車、トラックなど) を扱います。
• 複数のフロアにわたる駐車スペースの管理。
• 駐車車両の支払い処理。

特徴

• 車両の追加と削除…

GitHub で表示

以上がエレベーター スケジュール アルゴリズム: FCFS、SSTF、SCAN、および LOOKの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。