我不知道你的问题的所有细节,但我的直觉是,你可能会在这里思考的东西。您计划在此数据结构中存储多少个对象?如果你有大量的数据存储在这里,我建议你使用一个实际的数据库而不是数据结构。这里描述的操作类型是关系数据库擅长的一些经典事例。 MySQL和PostgreSQL是大型关系数据库的例子,可以在睡眠中做这种事情。如果你想要更轻便的东西SQLite可能会感兴趣。
如果你没有大量的数据需要存储在这个数据结构中,我建议保持简单,只有在你确定它不足以满足你的需求时才会优化它需要做。作为第一个镜头,我只是推荐使用内置的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
这definitly不是最快的选项可用,但如果没有人的数量庞大,以保持跟踪,你可能不会注意到任何性能问题。如果您确实有一些特殊情况会导致使用常规列表和地图的速度不可行,请发布它们,我们可以根据这些建议提出建议。
编辑:
阅读您的意见后,看来我通过误解你的问题在第一次运行。看起来你并不是很喜欢将群组映射到人群,而是将人员映射到群组。你可能想要的更多的是这样的:
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;
}
此方法在大型数据集上可能没有很好的性能,但它很容易理解。因为它被封装在自己的方法中,所以如果事实证明你需要更好的性能,它也应该很容易更新。如果你确实需要提高性能,我会看看overriding the equals method of Person,这将使联想中的查找映射更快。从那里你也可以看看一个自定义类型,而不是字符串组,也有一个重写的equals方法。这将大大加快上面使用的包含方法。
我不太关心性能的原因是您提到的数字并不像算法那么大。因为此方法一找到两个匹配组就会返回,在最糟糕的情况下,您将调用ArrayList.contains的次数等于存在的组数。在最好的情况下,它只需要被调用两次。如果您经常调用checkForSharedGroups,性能可能只会成为一个问题,在这种情况下,您最好找一种方法来减少调用它,而不是优化方法本身。
是的,OP应该采取更加面向对象的方法来解决这个问题,除非有某种其他原因(教授)以特定方式进行。使用面向对象的方法会使后面的问题变得更容易,例如 - 如果组需要一些额外的属性,例如主持人,名称,描述,该怎么办? – aglassman
感谢您的建议,我估计最多会有~100人和〜10000人。不会有太多的数据修改。 唯一会被称为最多的将是检查函数,该函数接受人员列表,如果它们都不属于同一组,则返回true,否则返回false。我想以一种只使用很少内存的方式存储数据,并且可以非常快速地执行此功能。 – user1181031
我应该提到我将存储组和其他人的所有信息(他们实际上是类),我只需要这个关系表来快速计算这1个函数。 – user1181031