java - 有效地找到匹配的对象对

Question

我需要一种算法来在列表中找到匹配的对象对。这是一个示例案例:

class Human 
{
   int ID;
   string monthOfBirth;
   string country;
   string [] hobbies = {};
}

有很多人，问题是找到匹配的人对，这需要高效地完成，因为列表很大。

匹配条件:

1. 出生月份和国家必须完全一致
2. 两人的兴趣爱好应该都超过 x%。

由于 (2) 标准，我们无法进行完全相等的比较。

我能想到的方式有:

1. 蛮力 - 将每个对象与其他所有对象进行比较。复杂度 O(n^2)
2. 哈希表

对于哈希表方法，我正在考虑以下方式:

1. 创建 <String, List<Human>> 的哈希集(或 MultiMap)
2. 将每个人的出生月份和国家连接成一个字符串
3. 使用这个连接的字符串哈希到哈希集(两个出生月份和国家相同的人必须给出相同的哈希码)
4. 如果已经有一个元素，比较x%匹配的爱好
5. 如果匹配，则这是重复的
6. 如果兴趣爱好不匹配超过x%，则添加这个人(链表方法)

有更好的方法吗？

连接月份和国家是否有意义？该列表会很大，所以我假设“更好”意味着存储量，而不是执行速度。

Answer 1

首先，您需要按monthOfBirth + country 将人类分类到桶中。这样做的成本应该相当低 - 只需遍历所有这些，将每一个放入适当的桶中。

请注意，附加字符串是解决此问题的“hacky”方法。 “正确”的方法是使用正确的 hashCode 方法创建一个键对象:

 public class MonthCountryKey {
     String monthOfBirth;
     String country;
     // <snip> constructor, setters 
     @Override public int hashCode() {
         return Arrays.hashCode(new Object[] {
            monthOfBirth, 
            country,
         });
     }
     @Override public boolean equals(Object o) {
         ...
     }
 }

参见:What is a best practice of writing hash function in java?

Map<MonthCountryKey,List<Human>> buckets = new HashMap<List<Human>>;

while(Human human = humanSource.get()) {
    MonthCountryKey key = new MonthCountryKey(human.getMonthOfBirth(), human.getCountry());
    List list = buckets.get(key);
    if(list == null) {
       list = new ArrayList<Human>();
       buckets.put(key,list);
    }
    list.add(human);
}

请注意，还有其他种类的 Set。例如，new TreeSet(monthCountryHumanComparator)——使用 Apache BeanUtils new TreeSet(new BeanComparator("monthOfBirth.country"))!

如果真的有 很多 人，那么将桶存储在数据库中可能是值得的 - SQL 或其他方式，如您认为合适。您只需要能够通过存储桶和列表索引号合理快速地获取它们。

然后您可以依次对每个桶应用爱好匹配算法，从而显着减少暴力搜索的规模。

我看不出有什么方法可以避免将桶中的每个人与同一桶中的每个其他人进行比较，但您可以做一些工作来降低比较成本。

考虑将爱好编码为整数；每个爱好一点。一个 long 给你最多 64 个爱好。如果您需要更多，您将需要更多整数或 BigInteger(基准两种方法)。当你通过人类工作并遇到新的爱好时，你可以建立位位置到爱好的字典。比较两组爱好然后是一个廉价的二进制“&”，后跟一个 Long.bitCount()。

为了说明，第一个人有爱好[“ cooking ”，“电影院”]

所以右边的位是“ cooking ”，左边的下一位是“电影院”，这个人的编码爱好是二进制 {60 零}00011 == 3

下一个人喜欢 [ "cooking", "fishing"]

所以 fishing 被添加到字典中，这个人的编码爱好是 {60 零}0101 = 5

 public long encodeHobbies(List<String> hobbies, BitPositionDictionary dict) {
      long encoded = 0;
      for(String hobby : hobbies) {
          int pos = dict.getPosition(hobby); // if not found, allocates new
          encoded &= (1 << pos)
      }
      return encoded;
 }

...与...

 public class BitPositionDictionary {
     private Map<String,Integer> positions = new HashMap<String,Integer>();
     private int nextPosition;
     public int getPosition(String s) {
         Integer i = positions.get(s);
         if(i == null) {
             i = nextPosition;
             positions.put(i,s);
             nextPosition++;
         }
         return i;
     }
 }

二进制 & 他们得到 {60 零}0001; Long.bitCount(1) == 1。这两个人有一个共同爱好。

要处理你的第三个人:[ "fishing", "clubbing", "chess"]，你的成本是:

• 添加到 hobby->bit 位置字典并编码为整数
• 与迄今为止创建的所有二进制编码的爱好字符串进行比较

您会希望将二进制编码的爱好存储在访问起来非常便宜的地方。我很想只使用一个 long 数组，并带有相应的人类索引:

  long[] hobbies = new long[numHumans];
  int size = 0;
  for(int i = 0; i<numHumans; i++) {
      hobby = encodeHobbies(humans.get(i).getHobbies(),
                             bitPositionDictionary);
      for(int j = 0; j<size; j++) {
          if(enoughBitsInCommon(hobbies[j], hobby)) {
              // just record somewhere cheap for later processing
              handleMatch(i,j); 
          }
      }
      hobbies[size++] = hobby;
  }

与...

  // Clearly this could be extended to encodings of more than one long
  static boolean enoughBitsInCommon(long x, long y) {
      int numHobbiesX = Long.bitCount(x);
      int hobbiesInCommon = Long.bitCount(x & y);
      // used 128 in the hope that compiler will optimise!
      return ((hobbiesInCommon * 128) / numHobbiesX ) > MATCH_THRESHOLD;
  }

这样，如果兴趣类型足够少，可以长期保存，则可以在 1GB 数组中保存 1.68 亿组兴趣:)

它应该非常快；我认为 RAM 访问时间是这里的瓶颈。但这是一个暴力搜索，并且继续是 O(n²)

如果您谈论的是真的巨大的数据集，我怀疑这种方法适用于使用 MapReduce 或其他任何东西进行分布式处理。

---

附加说明:您可以使用 BitSet 而不是 long(s)，并获得更多的表现力；也许以牺牲一些性能为代价。同样，基准。

  long x,y;
  ...
  int numMatches = Long.bitCount(x & y);

  ... becomes

  BitSet x,y;
  ...
  int numMatches = x.and(y).cardinality();

两个字符串不同的位置数称为汉明距离，在 cstheory.so 上有一个关于搜索具有接近汉明距离的对的已回答问题:https://cstheory.stackexchange.com/questions/18516/find-all-pairs-of-values-that-are-close-under-hamming-distance -- 根据我对已接受答案的理解，这种方法会找到“非常高比例”的匹配项，而不是全部，我想这确实需要强力搜索。