私はあなたの問題の詳細をすべて知っているわけではありませんが、私の本能は、あなたがここで物事を考えすぎている可能性があるということです. このデータ構造にいくつのオブジェクトを保存する予定ですか? ここに大量のデータを保存する場合は、データ構造ではなく実際のデータベースを使用することをお勧めします。ここで説明している操作の種類は、リレーショナル データベースが得意とする典型的な例です。MySQLとPostgreSQLは、この種のことをスリープ状態で実行できる大規模なリレーショナル データベースの例です。より軽量なSQLiteが必要な場合は、おそらく興味深いでしょう。
このデータ構造に大量のデータを格納する必要がない場合は、シンプルなままにして、必要な処理を行うのに十分な速度が得られないことが確実な場合にのみ最適化することをお勧めします。最初のショットとして、Java のビルトイン List インターフェイスを使用してユーザーを格納し、Map を使用してグループを格納することをお勧めします。次のようなことができます。
// Use a list to keep track of People
List<Person> myPeople = new ArrayList<Person>();
Person steve = new Person("Steve");
myPeople.add(steve);
myPeople.add(new Person("Bob"));
// Use a Map to track Groups
Map<String, List<Person>> groups = new HashMap<String, List<Person>>();
groups.put("Everybody", myPeople);
groups.put("Developers", Arrays.asList(steve));
// Does a group contain everybody?
groups.get("Everybody").containsAll(myPeople); // returns true
groups.get("Developers").containsAll(myPeople); // returns false
これは間違いなく利用可能な最速のオプションではありませんが、追跡する膨大な数の People がなければ、おそらくパフォーマンスの問題に気付かないでしょう。通常のリストとマップを使用する速度が実現不可能になる特別な条件がある場合は、それらを投稿してください。それらに基づいて提案を行うことができます。
編集：
あなたのコメントを読んだ後、最初の実行であなたの問題を読み間違えたようです. グループを人にマッピングすることにはあまり関心がないようですが、代わりに人をグループにマッピングします。おそらく必要なのは、次のようなものです。
Map<Person, List<String>> associations = new HashMap<Person, List<String>>();
Person steve = new Person("Steve");
Person ed = new Person("Ed");
associations.put(steve, Arrays.asList("Everybody", "Developers"));
associations.put(ed, Arrays.asList("Everybody"));
// This is the tricky part
boolean sharesGroups = checkForSharedGroups(associations, Arrays.asList(steve, ed));
では、checkForSharedGroups メソッドをどのように実装するのでしょうか? あなたの場合、これを取り巻く数値はかなり低いので、単純な方法を試して、そこから始めます.
public boolean checkForSharedGroups(
Map<Person, List<String>> associations,
List<Person> peopleToCheck){
List<String> groupsThatHaveMembers = new ArrayList<String>();
for(Person p : peopleToCheck){
List<String> groups = associations.get(p);
for(String s : groups){
if(groupsThatHaveMembers.contains(s)){
// We've already seen this group, so we can return
return false;
} else {
groupsThatHaveMembers.add(s);
}
}
}
// If we've made it to this point, nobody shares any groups.
return true;
}
この方法は、大規模なデータセットではおそらく優れたパフォーマンスを発揮しませんが、理解するのは非常に簡単です。独自のメソッドにカプセル化されているため、パフォーマンスの向上が必要になった場合の更新も簡単です。パフォーマンスを向上させる必要がある場合は、 Person の equals メソッドをオーバーライドすることを検討します。これにより、関連付けマップの検索が高速になります。そこから、オーバーライドされた equals メソッドを使用して、グループの String の代わりにカスタム タイプを確認することもできます。これにより、上記で使用した contains メソッドが大幅に高速化されます。
私がパフォーマンスについてあまり気にしていない理由は、アルゴリズムに関する限り、あなたが言及した数値が実際にはそれほど大きくないからです。このメソッドは、一致するグループが 2 つ見つかるとすぐに戻るため、最悪の場合、ArrayList.contains を存在するグループの数だけ呼び出すことになります。最良のシナリオでは、2 回呼び出すだけで済みます。checkForSharedGroups を非常に頻繁に呼び出す場合にのみパフォーマンスが問題になる可能性があります。