永井@知能.九工大です.

From: 岩崎 弘孝 <IH000667 / mb.taiyokogyo.co.jp>
Subject: [ruby-list:40939] 値の集合内の中から値の大きな数個のみを取得するには?
Date: Wed, 27 Jul 2005 13:31:40 +0900
Message-ID: <53D741AC18A5514EBA71321DAF45B4CC03132AA6 / TAIYONET.taiyokogyo.co.jp>
> 現在、具体的な利用案件としてはファイルシステム内上のファイルサイズの
> 大きい数個のファイル名のリストを出力することを想定しています。

目的が *真に* これであるなら,高度なアルゴリズムは不要かと思います.
単純に出力したい要素数の配列に,ソート状態を維持するように
ほおり込んでいく (あふれた分は捨てる) ので十分でしょう.

「ファイルサイズを取ってくる」という I/O 処理は,
配列の要素との比較および挿入操作に比べてかなり遅いと思われます.
ですので,ファイルサイズを得るごとに,そんな単純な方法で処理を
行ったとしても問題にはならないと考えます.

# なんなら,I/O 待ちの間に処理を進めるために,
# thread と queue とを使うとか.(^_^)

まぁ,出力したい要素数がある程度大きいのであれば,
現在の最小要素と比較した結果として挿入が必要となった場合には
二分探索で挿入位置を探すくらいのことはしてもいいかと思いますが.
-- 
                                       永井 秀利 (九工大 知能情報)
                                           nagai / ai.kyutech.ac.jp