- PR -

配列を検索するためのユーティリティ

1
投稿者投稿内容
カーニー
ぬし
会議室デビュー日: 2003/09/04
投稿数: 358
お住まい・勤務地: 東京
投稿日時: 2007-11-09 19:48
2つのbyte型の配列があります。

byte[] source = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
byte[] target = {4, 5, 6};

ここで、source内でtargetが最初に出現する位置のインデックスを取得したいと思っています。
上記例で言えば、得たい結果は3です。

とりあえずループを回しながらサーチする原始的なプログラムを書いたのですが、ちょっと分かりづらくなってしまいました。

お聞きしたいのは、上記のような要件を実現するのに便利なAPIやライブラリはないか? ということです。

Java標準APIにはjava.util.Arraysやjava.lang.System.arraycopy()のように、配列を便利に使うためのAPIがあるので、似たような感じで今回の問題解決に役立つものがないものかと期待しています。

[追加]
自分で書いたプログラムが分かりづらくなってしまったのは、実はもうちょい複雑な要件も絡まっているためで、必ずしも設問そのものの問題ではありません。
また、source配列サイズが巨大になる可能性があるため、パフォーマンスという観点から、System.arraycopy()がネイティブメソッドであるように、より効率の良い方法はないものかなと思っています。

[ メッセージ編集済み 編集者: カーニー 編集日時 2007-11-09 20:01 ]
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2007-11-09 20:36
引用:

カーニーさんの書き込み (2007-11-09 19:48) より:
また、source配列サイズが巨大になる可能性があるため、パフォーマンスという観点から、System.arraycopy()がネイティブメソッドであるように、より効率の良い方法はないものかなと思っています。

「BM法」あたりのアルゴリズムになると思います。
http://www.google.co.jp/search?hl=ja&ie=UTF-8&q=BM%e6%b3%95
ほかにもいくつかアルゴリズムはあるみたいですが。

なお、Java において、メモリーにアクセスする方法は、普通に a[i] でアクセスするか System#arraycopy を使うかのどちらかしかないと思います。もっとも System#arraycopy を使っても、結局はコピー先の配列には a[i] でアクセスしないといけないので、ナンセンスでしょう。

それ以外だと、結局 native メソッドを使うただの外部ライブラリーでしかないので、配列検索に限ったことではなくなってしまうし、あまり Java を使う意味がそもそもないでしょう。

標準 API には、(1要素の検索用ですが)Collections#binarySearch はなぜか存在しますが、リニアサーチすらないと思いますので、自分で作るか、人の作った(あるいはオープンソースのプロジェクトなどの)ライブラリーを使うかしかないと思います。(Java 1.4 位までの認識です。Java 6 位だと標準で付いているのかな〜、という期待もありますが、よくは知りません。)

--
unibon {B73D0144-CD2A-11DA-8E06-0050DA15BC86}
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2007-11-09 20:57
ちなみに BM というキーワードで探してみましたが、
com.sun.org.apache.xerces.internal.impl.xpath.regex#BMPattern
などというものは存在するみたいですね。

(パッケージはちょっと違いますが。)
http://xerces.apache.org/xerces2-j/javadocs/xerces2/org/apache/xerces/impl/xpath/regex/BMPattern.html

ただ、引数が String や char[] ですね。
あと、パッケージが良く分かりません。使っていいのかとかが。

一応、呼ぶのは簡単ですぐに使うことはできるみたいです。速いのかどうかは分かりません。
ご参考まで。

--
unibon {B73D0144-CD2A-11DA-8E06-0050DA15BC86}
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2007-11-09 21:51
Java の勉強がてら、ひとりでいろいろ探していましたが、
http://java.sun.com/javase/ja/6/docs/ja/api/java/util/Collections.html#indexOfSubList(java.util.List,%20java.util.List)
というのがありましたね。配列版は見当たらないですが。

--
unibon {B73D0144-CD2A-11DA-8E06-0050DA15BC86}

[ メッセージ編集済み 編集者: unibon 編集日時 2007-11-09 21:52 ]
かつのり
ぬし
会議室デビュー日: 2004/03/18
投稿数: 2015
お住まい・勤務地: 札幌
投稿日時: 2007-11-10 16:18
char配列ならStringに変換してindexOfで一発で楽なんですけどね。
unibonさんと同じく、自分ならBM法で実装するかも。
カーニー
ぬし
会議室デビュー日: 2003/09/04
投稿数: 358
お住まい・勤務地: 東京
投稿日時: 2007-11-12 10:40
unibonさん、かつのりさん、ご返答どうもありがとうございました。

恥ずかしながらBM法というものは初めて耳にしましたが、それほど難しいアルゴリズムではないんですね。
また広く知られた方法であれば、ドキュメントやコメントでいちいち細かいことを説明しなくてもよいので、標準APIやライブラリではなくともこれはありがたいです。

大変助かりました。
小僧
ぬし
会議室デビュー日: 2002/08/14
投稿数: 526
投稿日時: 2007-11-12 10:45
試してないんですけど、ASCII文字列で変換してindexOfとかできないかな？。
コード:
new String(source,"US-ASCII")

sawat
大ベテラン
会議室デビュー日: 2006/08/02
投稿数: 112
投稿日時: 2007-11-12 18:39
引用:

unibonさんの書き込み (2007-11-09 21:51) より:
Java の勉強がてら、ひとりでいろいろ探していましたが、
http://java.sun.com/javase/ja/6/docs/ja/api/java/util/Collections.html#indexOfSubList(java.util.List,%20java.util.List)
というのがありましたね。配列版は見当たらないですが。

--
unibon {B73D0144-CD2A-11DA-8E06-0050DA15BC86}

Arrays.asListと組み合わせれば参照型配列にもつかえるのですが、プリミティブ型配列にはasListが使えないので無理ですね。逆に、そういう配列のボクシングをするメソッドさえ自前で作ればOKともいえますが。
1

スキルアップ／キャリアアップ（JOB@IT）