java.util.PriorityQueueで取り出したデータがソートされないケース
今日研究用のプログラムをJavaで書いたときに嵌った問題のメモ。
今、研究の検証用シミュレータをJavaで書いている。簡単にアプリケーションの挙動をシミュレーションするものだけど、ネットワーク部には少し力を入れている。アプリケーション実行ノードがネットワークにメッセージを流すときにはネットワークのMTUサイズにメッセージを分割し、ネットワークスイッチでは分割されたメッセージ単位で細かくフォワーディング、タイムスタンピングをしている。
そのシミュレータ内のネットワークスイッチにおいて、同一出力ポートへのメッセージの集中状況を表すために、メッセージに送信時刻を持たせ、ポートにはバッファを持たせるようにしている。そして、出力ポートからメッセージを送り出す際には、過去のメッセージのタイムスタンプを考慮してメッセージの送信時刻を更新している。
この機能を容易に実現するために、バッファにはJava付属のPriorityQueueクラス(java.util.PriorityQueue)を用いた。要はFIFOバッファを実現する手段として、単にキューからデータをGetするだけで送信時刻順にソートされたメッセージを取得したいがため。そこで、PriorityQueueにメッセージを追加する時にはoffer(Message msg)メソッドを、データを取得する際には、Iteratorを使って繰り返し処理を行ないたかったのでiterator()メソッドでIterator
どうしてなんだろうと、ソースを確認したところ、Priorityキューからiterator()メソッドで取得したIteratorを用いてメッセージを取得してもきちんとソーティングされないことが確認された。ドキュメントにもこう書かれている。
The iterator does not return the elements in any particular order.
http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html#iterator()
日本語の方にはこんな感じ。
反復子が要素を返す特定の順序はありません。
http://java.sun.com/javase/ja/6/docs/ja/api/java/util/PriorityQueue.html#iterator()
うーん、きちんとドキュメントを読まず、フィーリングで実装していたために嵌ってしまった。なお、toArray()などでも出力される配列内ではデータはソートされていないとのこと。
Iteratorを用いるとこのようにデータがソートされないことが分かったので、プログラムの方はIteratorで取得していたところを、PriorityQueue.poll()で取得するように修正した。Iteratorを用いた方がループがきれいに書けてうれしいんだけど、ソートされないんじゃぁ、しょうがない。
ともかく、ドキュメントはきちんと読め、といういい教訓だった。実はIterator周りではもう1つ、ドキュメントを読まずに嵌った問題があるんだけど、それはまた次の機会にでも。