2008-06-08

LabVIEW で2分探索するライブラリを作りました

LabVIEW の 1D 配列検索は線形探索です。つまり配列の先頭から要素を順番に確認していって、見つかったらおわり、というアルゴリズムです。配列サイズに比例して、つまり O(n) なので、確認する要素数が増えるので、データが大きくなると破綻しがちです。



配列が昇順または降順にソートされている場合、二分探索あるいはバイナリサーチと呼ばれる方法を使えます。これは、まず真ん中を見て、探している値が配列の前半にあるか後半にあるかを特定します。で、その前半なり後半なりの真ん中を見て... というの繰り返すアルゴリズムです。O(log n) です。



で、Ruby には高林さんが作った Ruby/BSearch というライブラリがあるので、それを LabVIEW に移殖しました。



使うときには、大小比較用の VI を最初に用意します。2つのバリアント A と B を受け取って、その大小比較の結果 (A-B) で返すような VI を作ります。数値の場合は単純に引き算すればよいですし、クラスタのような複雑な型の場合には、それなりの演算をして大小比較します。一致した場合には 0 を返さないといけません。



Cmpint




これで準備ができました。ってなわけで、BinarySearch.lvlib:Range.vi を使ってみましょう。下の例では、数値配列から 2 がある要素の最初の指標と、最後の指標+1 を返します。つまり 1 と 3 を返します。



Bsearchexample




BinarySearch-0.1.zipをダウンロード