取り置きの列を借りる:公平な予約
なぜ大切か いちから作った予約のシステムは、いちばん早くクリックした人に報いがちで、ひとりの来ない人が全員をふさぐのを許しがちです。毎日人々に乏しいものを配る場所は、ずっと前にもっと良い設計に落ち着きました。
3 つのカウンター
図書館の取り置き。貸し出し中の本に予約を入れます。1 冊が戻ると、それは予約の列の最初の人に行き、その人は知らせと、受け取りに来る数日間を得ます。来なければ、その本は次の人に行き、最初の人は自分の場所を失います。
呼び出しベル付きのレストランの順番待ち。名前を伝えてベルを受け取ります。テーブルが空くと、次の組が呼ばれ、5 分以内に案内の台に着かなければテーブルは次の組に行きます。
総菜屋のカウンターの整理券。番号を取ります。自分の番号が呼ばれたときにいなければ、次の番号が呼ばれます。新しい券を、列の後ろで取れます。
コードの前に比べる
- それぞれで、列の中の場所はいつ決まる:頼んだときか、ものが空いたときか?
- 来ない人はどうなり、どれだけの時間を得る?
- 誰かが受け取りに来るのを待つ間、ものはどうなる?
- 本にもテーブルにも肉にも触れない一文で、共有する規則を述べる。
目的の問題
モバイルのチームが、テスト用の電話の小さなラボを共有しています。エンジニアは機種を頼み、その機種の電話が空くとそれが勧められ、2 時間以内にラボのアプリで受け取らなければなりません。受け取った電話は 8 時間の枠で予約され、それから自動で戻ります。今のアプリは、空いた電話を最初に「受け取る」を押した人に渡し、人々はそれを押すスクリプトを書き始めています。
stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events) # -> [("ana", "dev1", 30)] (ben is not first)loans(stock, events) を書いてください。stock は (device_id, model) を並べ、時刻 0 ではすべて空いています。events は ("request", t, person, model) か ("claim", t, person, model) で、分の時刻 t で並べてあります。規則:
- それぞれの機種には頼んだ順のキューがあります。その人がすでにその機種のキューにいるか、その機種の勧めを持っているなら、頼みは無視されます。
- 空いた電話は、その機種のキューの最初の人に勧められます(その人はキューを離れます)。誰もキューにいなければ棚で待ち、その機種の後の頼みがすぐにそれを得ます。棚にいくつかあれば、最も小さな端末の ID を勧めます。
- 時刻
oにした勧めは、t < o + 120の間受け取れます。その人と機種について生きた勧めのない受け取りは無視されます。 o + 120に、受け取られていない勧めは失効し、電話はその瞬間にまた空きます(規則 2)。- 時刻
tの受け取りで貸し出しが始まり、電話はt + 480に空きます。 - イベントの時刻以前に期限の来る失効と返却は、時刻の順、それから端末の ID の順に、それより前に起こります。
(person, device_id, claim_time) として返してください。
この演習はまもなく開きます
その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。
このブラウザは learn.floati.life の Cookie をブロックしているため、ここで修了したレッスンを順番どおりに開けません。このサイトの Cookie を許可して再読み込みしてください。