最も計算量の少ない最小値発見について

質問

大量のデータの中から最小値を発見する最も計算量の少ないプロセスを教えてください。
ハードウェア化を想定しています。そのため，できるだけ回路規模を小さくする設計をしたいと思っています。

回答No.5

kmee · ベストアンサー

ランダムに並んだ値の最小値を求めるのって、トーナメントでやっても、順番にやっても、しなければならない計算量自体は「データ数-1」なんですよ。
それ以上速くするなら、並列処理するしかないでしょう。

数値→1の個数に変換するやりかたも、16ビットの数値からの変換だと64kビットの記憶領域が必要です。変換自体はカウンタで実現できそうですが、完全な動作には64kクロック必要です。

データを同時にアクセス可能なら、おそらく、回路規模、速度ともに現実的なのは、トーナメント方式ではないでしょうか?

もし、データが順番に入ってくるのなら、頭から単純に比較するのがベストです。
データの入力終了が計算終了となるので、一番早いです。

お礼

>データを同時にアクセス可能なら、おそらく、回路規模、速度ともに
>現実的なのは、トーナメント方式ではないでしょうか?

確かに，1の個数へ変換するやり方で少し悩んでいました。
ワンステップで実現可能な方法を模索していましたが，なかなか見つかりませんでした。それに，他のモジュールでメモリを多く使っていて，今のターゲットデバイスではメモリはこれ以上増やせないので・・。

現状のシステムでは，データは同時に入力される設計となっています。
やはり，トーナメント方式を採用することがベストなのでしょうか、、

あと，2つの数の比較法ですかね。
現状は普通に （最小の数が複数ある場合，どれか一つを選択）
if(a1 > a2) windata <=a2 (dataの格納）
　　　　　 winnumber <= b2 (dataを持つ変数の格納）
else windata <= a1
　　　　　　winnumber <= b1
として，定義しています。

しかし，二進数のデータでは上からビット単位で比較を行えばデータの全てを検索しなくても動作が出来そうで，
10101001010
10010101010
この二つのデータでは，上の3ビット目で大小が決めることが出来ます。

ビット単位の比較法とif文による比較のどちらが適切でしょうか？

回答No.6

uwi

回答番号：No.3で示したのは最速の例です。現実的にはデータの分布などにあわせて変換を考えることになると思います。
例えば最上位だけ残して
a1 = 4 = 0100 変換-> 0111
a2 = 1 = 0001 変換-> 0001
a3 = 2 = 0010 変換-> 0011
a4 = 7 = 0111 変換-> 0111
とします。このやり方だと大きい数値ばかり（最悪条件）だと問題なのですが、そういうパターンが起こりえないデータであれば利用できます。上位はNo.3で下位は上のやり方とか他にもいろいろ考えられると思います。
あと、データがまばら(0～10^10の中から100個とか)の場合は単純に比較する方が殆どの場合に速くなります。

結局のところNo.3に書いたようにデータによってなので、データ分布が想定できないならトーナメント方式で数値比較が安定すると思います。

お礼

>データがまばら(0～10^10）
データ値が大きくなると,用意するビットが増える方法なので実装は難しそうです。

良いやり方ではありますが、確実に（最速で）最小値を求めるためには,まだまだ改良が考えられそうです。
また、データにによっては,こちらの方がいい場合もあるかもしれません。
総当り,二分木、クイック、マージetc　以外の新しいやり方だと思います。
回答ありがとうございます。

回答No.4

uwi

わかるとは思いますが、回答番号：No.3でORとANDを間違えてます。
最大も最小もいける例と言うことで…

ちなみにこういう考え方は、最小値探索するのには数値の比較が不可欠だと思い込むと、一生たどりつけないので柔軟な思考が大切です。

補足

データ数が増加しても，計算量が変わらず小さい回路でシステムを設計する方法は何かありませんか？
スピードを上げることより，スピードを落とさず計算量を減らす方法

回答No.3

uwi

> 現在、二分木を用いて最小値検索
二分木というかたぶんトーナメント方式で、
一回戦はa1とa2,a3とa4,…、少なかった方が勝ち上がって二回戦、同様に三回戦、…
というやり方だと思います。ただこれだと1回戦の終了をまたないと2回戦が始められないという問題があります。
で、よくある実装としては、
a1 = 4 変換-> 00001111
a2 = 5 変換-> 00011111
a3 = 2 変換-> 00000011
a4 = 7 変換-> 01111111
…
としてORをとって
00000011 逆変換-> 2
という手順で最小値を求めます。こうすることで分散しても待ちが発生しない実装になります。ただ、データの種類がわかっている場合しかできません。
ハードの方はあまり詳しくなのでどっちの実装がいいのかは知りません。

お礼

お答えありがとうございます。
この方法なら、かなりのスピードが期待できると思います。
最小の値をもつ変数の検索にはXORを使えば大丈夫そうですね。
どちらかというと、最小値そのものよりも最小値をもつ変数の方が重要なんです。（最初の説明で書くべきでした）

ハードウェア実装への難点は、データの値が1万以上（データ数は1000以上）となると，変換のために用意する変数のビットが大きくなるのと，大量のＡＮＤ回路とＸＯＲ回路を使用するため，回路規模が少し心配です。
回路規模が大きくなりすぎた場合，上位桁と下位桁の多段階に分け、最小値を発見する方法も考えてみます。
上位桁の最小の値の中で下位桁で最小の値を持つ値を探索（スピードが落ちてしまいそうですが）

かなり参考になりました。ありがとうございます

補足

今回使用するデータの種類　
全てデータは同じビット幅で、符号なし（正の）整数です。

回答No.2

doran357

データがソートされているならまだしもランダムな並びのデータだと
総当たりで比較する必要がありますよね。

そもそも質問者は二分木検索しているようだけど
これってソートされていて初めて実用になる物ですけどソートしてあるデータなの?
それと最小値ならソートされているなら最初と最後を比較すればどっちが最小値(並びが降順か昇順か)わかるから二分木検索すらする必要は無くなるけどどういう事?

補足

回答番号：Ｎo4の方の方のおっしゃるとおり、トーナメント方式を採用しています。通常の二分木のような上からの捜査でなく、下から順に比較してく構成です。

データはランダムなデータです。
比較する全てのデータのビット幅は同じで、固定です。

回答No.1

miracle3535

データーを１個ずつＡに代入します。

if A < B then B=A

これをループしデーター全てをチェックします。
Ｂの初期値に大まかな値を入れておきます。
これも自動でしたい場合は

データーをＡ1、Ａ2とします。

if A2 < A1 then B=A2

としてループして全数検索してください。

お礼

お答えありがとうございます。
しかし、その方法では比較回数（コンパレータ）がデータと同じ数分必要になりそうです。

補足

説明不足ですいません。
現在、二分木を用いて最小値検索を行っていますが、それ以上に早く、さらにデータ数に比例した回路の増加が少なく、できるだけ小さな回路で構成可能な探索法を探しています。