プログラマーの面接でよく聞かれる質問: スケジュールされたタスク スケジューラを設計し、どのようなアルゴリズムとデータ構造を使用するか

学生時代、私は Huya の面接を受けたことがあります。今でもはっきりと覚えている面接の質問がありました。スケジュールされたタスクを実装するように求められました。あなたならどうしますか? 問題を単純化するために、データの永続性ではなく、メモリ ソリューションのみを考慮する必要があります。

配列メソッド

最も簡単な方法は、すべてのタスクを配列に格納し、単位時間ごとに配列全体を走査して、現在の時間に一致するタスクがあるかどうかを確認します。一致するタスクがある場合は、配列から取り出して実行します。単位時間あたりのクエリ アルゴリズムの複雑さは O(N) です。

では、新しいタスクを追加するにはどうすればよいでしょうか。配列に要素を追加するだけで、アルゴリズムの時間計算量は O(1) です。

[[278610]]

優先キュー方式

アルゴリズムを評価するときは、クエリ アルゴリズムの複雑さと挿入アルゴリズムの複雑さの両方を考慮する必要があります。スケジュールされたタスクのシナリオでは、多くのクエリ シナリオがあることは明らかです。ほぼ毎時間ポーリングする必要があるので、アルゴリズムを最適化することは可能でしょうか?

クエリを実行するたびに、現在の時刻に最も近い時刻のみがクエリされます。現在の時刻より前の時刻は確実に破棄されます。したがって、この質問は、クエリ キュー内で最も時間が短い質問と同等です。よく知られているデータ構造である優先キューを思い浮かべずにはいられません。または、小さなルート ヒープを使用して実装することもできます。

新しいスケジュールされたタスクを挿入するたびに、タスクを優先キューに挿入します。挿入するたびに、キューを内部的に調整する必要があります。アルゴリズムの時間計算量は O(logN) です。アルゴリズムの時間計算量について議論する場合、logN は Base2 であること、つまり N が 8 の場合、logN は 3 であることに注目する価値があります。

同様に、最短時間のタスクを O(1) 時間で見つけることができますが、この要素を取り除くと、優先キューは内部調整を行う必要があり、このアルゴリズムの時間計算量も O(logN) になります。

時の輪

上記の優先キュー アルゴリズムの時間計算量は O(logN) であり、非常に効率的です。ただし、高度な同時実行が可能な分散システムでは、この速度では依然として遅すぎます。もっと効率的なアルゴリズムはありますか?

これがタイム ホイール アルゴリズムです。タイム ホイールは循環キューです。これは時間単位に分割されています。ここでは 1 秒と仮定します。各単位には、スケジュールされたタスクを格納するためのリンク リストが含まれています。

円形キュー内の要素は結局優先順位が付けられますが、長さを超えた場合はどうすればいいのでしょうか。家庭にある水道メーターを思い浮かべてください。水道メーターにも多数のホイールがあり、各ホイールには異なる単位が付いています。

タイムホイールについても同じことが言えます。時計や水道メーターと同じように、最適化のためにマルチレベルのタイムホイールを使用できます。1 つのレイヤーが円を 1 つ移動すると、次のレイヤーが 1 グリッド移動します。

では、このアルゴリズムの時間計算量はどのように計算するのでしょうか。挿入するときは、下位レイヤーから開始し、どのレイヤーにあるかを見つけて、対応するスケールを直接挿入します。タイムホイールに 5 つのレイヤーがある場合、最大 5 回検索することになります。

クエリを実行するときは、タイムホイールを毎秒押し、そのたびにキューの先頭にある要素を直接取得します。これは、アルゴリズムの時間計算量が O(1) に相当します。円を描いたら、次のレイヤーの次のグリッドを押し下げます。このようにして、要素は最大で第 5 層から第 1 層に挿入されます。合計で、要素は最大 5 回挿入されます。アルゴリズムの時間計算量を評価するときは、通常、定数を無視し、アルゴリズムの最終的な時間計算量は O(1) です。

要約する

非常に単純な面接の質問には、実のところいくつかの異なる解決策があります。これがアルゴリズムとデータ構造の魅力です。皆さん、私をフォローして、一緒に学び、一緒に進歩することを歓迎します。皆さんのサポートが、私がチャットを続けるモチベーションになっています。