回答編集履歴
1
追記
test
CHANGED
@@ -23,3 +23,43 @@
|
|
23
23
|
なぜ優先度3のリストに優先度2のリストをつなげなければならないかの意義がわかりません。それがわからないのは、上に書いたように「エントリーを取り出す機能の詳細な動作仕様」を書ききれていないからだと思います。例えば「指定優先度のエントリーが存在してなければ次の優先度のエントリーを取り出す仕様」だったりするのでしょうか?
|
24
24
|
|
25
25
|
もしそうだとしても優先度が異なるリストを接続するかどうかはアルゴリズムの実装に依存することであって仕様ではないようにも思えます。リストを接続するのが「課題の条件=仕様」であればそうしなければなりませんが、あなたがイメージした実装のようにも見えました。どちらなのかはっきりしないとアドバイスもしにくいと思います。
|
26
|
+
|
27
|
+
|
28
|
+
|
29
|
+
---
|
30
|
+
|
31
|
+
追記:
|
32
|
+
|
33
|
+
なんとなく仕様が想像できるようになりました。作成すべき機能をscehdule関数、それが管理するものをタスクと呼ぶことにすると・・・
|
34
|
+
|
35
|
+
|
36
|
+
|
37
|
+
1. ディスパッチした後のタスクは優先度が高いものが高頻度でスケジュールされるようにする
|
38
|
+
|
39
|
+
2. 優先度が高いものを高頻度で呼び出すための仕様は
|
40
|
+
|
41
|
+
2.1 sceduleの呼び出し毎に優先度2~1の先頭タスクだけ1つ上の優先度キューへ昇格させる
|
42
|
+
|
43
|
+
2.2 ディスパッチ後に最高優先度以外のタスクは自身の優先度キューへ戻す
|
44
|
+
|
45
|
+
1. schedule関数は1回の呼び出しで必ず1つのタスクを取り出す(そしてディスパッチする?)
|
46
|
+
|
47
|
+
1. 2のキューの並べ替えをした上で3~1の中で空でない一番優先度の高いキューからタスクを取り出す
|
48
|
+
|
49
|
+
|
50
|
+
|
51
|
+
自分が質問者さんの説明をよく読んでれば最初からわかってたかもしれません。失礼しました。
|
52
|
+
|
53
|
+
上に書いたのは私なりに表現した仕様ですが、このとおりでよいならそれを素朴に実装できそうな気がします。実装にあたっては主としてキューを実現するところだけ若干面倒があるかも知れません。
|
54
|
+
|
55
|
+
|
56
|
+
|
57
|
+
- キュー
|
58
|
+
|
59
|
+
出来合いのクラスを利用するのでもかまわないなら簡単ですが、自前で実装するならキューの実現方法を理解しておく必要があります。もし曖昧なのであれば「アルゴリズム キュー」で検索してみると考え方や実装のサンプルが載っているものが見つかると思います。キューが先頭と末尾のエントリーを保持していて要素自体は双方向のチェーンでリンクされた構造や内部的に配列を用い双方向のリンクを必要としないリングバッファのようなものなどいくつかの考え方が見つかると思います。
|
60
|
+
|
61
|
+
いずれにせよ必要なのは「空かどうかの判定」「先頭からの取り出し」「末尾への追加」という3つの機能ですね。
|
62
|
+
|
63
|
+
|
64
|
+
|
65
|
+
|