我有2组数据。
可以说一个是一个民族，另一个是一个群体。
一个人可以在多个组中，而一个组可以有多个人。
我的业务基本上是针对团体和人员的CRUD。
以及一种确保人员列表位于不同组中的方法(称为很多)。
现在，我正在考虑制作一个二进制0和1的表，其中水平表示所有人员，垂直表示所有组。
我可以在O(n)时间内通过添加每个二进制列表并将其与二进制列表的“和”运算进行比较来执行该方法。
例如
Group A B C D
ppl1 1 0 0 1
ppl2 0 1 1 0
ppl3 0 0 1 0
ppl4 0 1 0 0
check (ppl1, ppl2) = (1001 + 0110) == (1001 & 0110)
= 1111 == 1111
= true
check (ppl2, ppl3) = (0110 + 0010) == (0110+0010)
= 1000 ==0110
= false
我想知道是否已经有一个数据结构已经做了类似的事情，所以我不必自己编写并维护O(n)运行时。
最佳答案
我不知道您问题的所有细节，但是我的直觉是您可能在这里思考问题。您打算在此数据结构中存储多少个对象？如果您要在此处存储大量数据，我建议您使用实际的数据库而不是数据结构。您在此处描述的操作类型是关系数据库擅长的经典示例。 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
这绝对不是最快的选项，但是如果您没有足够的人员来跟踪，那么您甚至可能不会注意到任何性能问题。如果您确实有某些特殊情况会导致无法快速使用常规列表和地图，请发布它们，我们会根据这些情况提出建议。
编辑:
阅读您的评论后，看来我在第一次运行中误读了您的问题。您似乎对将组映射到人员并没有太大兴趣，而是将人员映射到组。您可能想要的更像这样:
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方法查看自定义类型，而不是字符串组。这将大大加快上面使用的contains方法。
我不太在意性能的原因是，就算法而言，您提到的数字实际上并不那么大。因为此方法在找到两个匹配的组后立即返回，所以在更糟糕的情况下，您将调用ArrayList.contains包含与存在的组数相等的次数。在最好的情况下，只需调用两次即可。如果您非常频繁地调用checkForSharedGroups，则性能可能只是一个问题，在这种情况下，最好寻找一种不经常调用它的方法，而不是优化方法本身。