私は Java でオブジェクトの ArrayList を持っています。オブジェクトには 4 つのフィールドがあり、そのうちの 2 つはオブジェクトが別のオブジェクトと等しいと見なすために使用します。これら 2 つのフィールドを考慮して、配列にそのオブジェクトが含まれているかどうかを確認する最も効率的な方法を探しています。
問題は、これらのクラスが XSD オブジェクトに基づいて生成されるため、クラス自体を変更して.equals.
オブジェクトごとに 2 つのフィールドをループして手動で比較し、見つかったときに中断するよりも良い方法はありますか? より良い方法を探して、それはとても面倒に思えます。
編集: ArrayList は、オブジェクトに非整列化された SOAP 応答から取得されます。
それは、物事をどれだけ効率的にする必要があるかによって異なります。特定の条件を満たす要素を探してリストを単純に反復するのは O(n) ですが、Equals メソッドを実装できれば ArrayList.Contains も同様です。ループまたは内部ループでこれを行っていない場合、このアプローチはおそらく問題ありません。
非常に効率的な検索速度がどうしても必要な場合は、次の 2 つのことを行う必要があります。
もちろん、この HashSet の構築にはまだ O(n) のコストがかかります。HashSet を構築するコストが、実行する必要があるすべての contains() チェックの総コストと比較して無視できる場合にのみ、何かを得ることができます。重複のないリストを作成しようとするのがそのようなケースです。
並べ替えとバイナリ検索のための Java の組み込みメソッドで Comparator を使用できます。次のようなクラスがあるとします。ここで、a と b は並べ替えに使用するフィールドです。
class Thing { String a, b, c, d; }
Comparator を次のように定義します。
Comparator<Thing> comparator = new Comparator<Thing>() {
public int compare(Thing o1, Thing o2) {
if (o1.a.equals(o2.a)) {
return o1.b.compareTo(o2.b);
}
return o1.a.compareTo(o2.a);
}
};
次に、リストを並べ替えます。
Collections.sort(list, comparator);
最後にバイナリ検索を実行します。
int i = Collections.binarySearch(list, thingToFind, comparator);
制約を考えると、ブルート フォース検索 (または検索が繰り返される場合はインデックスの作成) で立ち往生しています。がどのようにArrayList生成されるかについて詳しく教えてください。おそらくそこには多少の余裕があります。
探しているのがよりきれいなコードだけである場合は、Apache Commons Collections クラス、特にCollectionUtils.find()を使用して、既製のシンタックス シュガーを使用することを検討してください。
ArrayList haystack = // ...
final Object needleField1 = // ...
final Object needleField2 = // ...
Object found = CollectionUtils.find(haystack, new Predicate() {
public boolean evaluate(Object input) {
return needleField1.equals(input.field1) &&
needleField2.equals(input.field2);
}
});
リストがソートされている場合は、バイナリ検索を使用できます。そうでない場合は、これ以上の方法はありません。
これを頻繁に行う場合は、最初にリストをソートするのに時間をかける価値はほぼ間違いなくあります。クラスを変更することはできないため、 a を使用Comparatorして並べ替えと検索を行う必要があります。
equals メソッドがこれら 2 つのフィールドを比較していたとしても、論理的には、手動で行うのとまったく同じコードになります。OK、「ぐちゃぐちゃ」かもしれませんが、それでも正解です
あなたが私のForEach DSLのユーザーであれば、Detectクエリで実行できます。
Foo foo = ...
Detect<Foo> query = Detect.from(list);
for (Detect<Foo> each: query)
each.yield = each.element.a == foo.a && each.element.b == foo.b;
return query.result();
オブジェクトごとに 2 つのフィールドをループして手動で比較し、見つかったときに中断するよりも良い方法はありますか? より良い方法を探して、それはとても面倒に思えます。
あなたの懸念が保守性である場合、Fabian Steegが提案することを行うことができます（それが私がすることです）が、おそらく「最も効率的」ではありません（最初に配列をソートしてからバイナリ検索を実行する必要があるため）が、確かに最もクリーンですそしてより良いオプション。
効率性を重視する場合は、オブジェクト内のフィールドをハッシュとして使用し、HashMap をストレージとして使用するカスタム List 実装を作成できます。しかし、おそらくこれは多すぎるでしょう。
次に、データを入力する場所を ArrayList から YourCustomList に変更する必要があります。
お気に入り：
List list = new ArrayList();
fillFromSoap( list );
に：
List list = new MyCustomSpecialList();
fillFromSoap( list );
実装は次のようになります。
class MyCustomSpecialList extends AbstractList {
private Map<Integer, YourObject> internalMap;
public boolean add( YourObject o ) {
internalMap.put( o.getThatFieldYouKnow(), o );
}
public boolean contains( YourObject o ) {
return internalMap.containsKey( o.getThatFieldYouKnow() );
}
}
HashSet とほとんど同じですが、ここでの問題は、HashSet が hashCode メソッドの優れた実装に依存していることです。代わりに、あるオブジェクトを他のオブジェクトと等しくする「あなたが知っているそのフィールド」をハッシュとして使用します。
もちろん、最初から List を実装するのは、上記の私のスニペットよりもはるかにトリッキーです。そのため、Fabian Steegの提案の方が実装がより適切で簡単であると言います (ただし、このようなものの方が効率的です)。
最後に何をしたか教えてください。
キーとしてフィールド値に基づいてこれらのオブジェクトの HashMap を構築することは、パフォーマンスの観点から価値がある可能性があります。
同じリストで何度も検索する必要がある場合は、インデックスを作成することで成果が得られる場合があります。
1 回反復し、探している equals 値をキーとして、適切なノードを値として HashMap を構築します。与えられた等しい値の誰かではなくすべてが必要な場合は、マップにリストの値の型を持たせ、最初の繰り返しでリスト全体を構築します。
これを行う前に測定する必要があることに注意してください。これは、インデックスを作成するオーバーヘッドが、予想されるノードが見つかるまでのトラバースを覆い隠す可能性があるためです。
次の 3 つの基本的なオプションがあります。
1) 検索パフォーマンスが最も重要であり、それが現実的である場合は、一度作成された (リストが変更された場合に変更された) 形式のハッシュ テーブルを使用します。
2) リストが便利にソートされているか、ソートすることが実際的であり、O(log n) の検索で十分な場合は、ソートして検索します。
3) O(n) の取得が十分に高速である場合、またはデータ構造または代替を操作/維持することが実際的でない場合は、リストを反復処理します。
List に対する単純な反復よりも複雑なコードを記述する前に、いくつかの質問について考える価値があります。
なぜ違うものが必要なのですか？（タイム）パフォーマンス？優雅？メンテナンス性？再利用？これらはすべて、別々であっても一緒であっても問題ありませんが、解決策に影響を与えます。
問題のデータ構造をどの程度制御できますか? その構築方法に影響を与えることができますか? 後で管理しますか？
データ構造 (および基礎となるオブジェクト) のライフサイクルはどのようなものですか? 一度に構築され、変更されることはありませんか、それとも非常に動的ですか? あなたのコードはそのライフ サイクルを監視 (または変更) できますか?
メモリ フットプリントなど、他に重要な制約はありますか。重複に関する情報は重要ですか? 等。
最も簡単な解決策は、オブジェクトをラップし、contains 呼び出しをラップされたクラスのコレクションにデリゲートすることです。これはコンパレータに似ていますが、結果のコレクションを強制的に並べ替える必要はありません。単純に ArrayList.contains() を使用できます。
public class Widget {
private String name;
private String desc;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getDesc() {
return desc;
}
public void setDesc(String desc) {
this.desc = desc;
}
}
public abstract class EqualsHashcodeEnforcer<T> {
protected T wrapped;
public T getWrappedObject() {
return wrapped;
}
@Override
public boolean equals(Object obj) {
return equalsDelegate(obj);
}
@Override
public int hashCode() {
return hashCodeDelegate();
}
protected abstract boolean equalsDelegate(Object obj);
protected abstract int hashCodeDelegate();
}
public class WrappedWidget extends EqualsHashcodeEnforcer<Widget> {
@Override
protected boolean equalsDelegate(Object obj) {
if (obj == null) {
return false;
}
if (obj == getWrappedObject()) {
return true;
}
if (obj.getClass() != getWrappedObject().getClass()) {
return false;
}
Widget rhs = (Widget) obj;
return new EqualsBuilder().append(getWrappedObject().getName(),
rhs.getName()).append(getWrappedObject().getDesc(),
rhs.getDesc()).isEquals();
}
@Override
protected int hashCodeDelegate() {
return new HashCodeBuilder(121, 991).append(
getWrappedObject().getName()).append(
getWrappedObject().getDesc()).toHashCode();
}
}