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

Linda Hamilton

リリース： 2024-10-27 20:31:02

オリジナル

809 人が閲覧しました

私はかなり長い間 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 と同様に、このアプローチは各方向の最後のリクエストまでしか移動しません。

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