高效地找到匹配的对象对
我需要一个算法来查找列表中匹配的对象对。 这是一个例子：
class Human
{
int ID;
string monthOfBirth;
string country;
string [] hobbies = {};
}
有一大堆人类，问题是找到匹配的人类对，而这需要高效地完成，因为这些清单非常庞大。
匹配标准：
由于（2）标准，我们不能做一个精确的等值比较。
我能想到的方式是：
对于散列表方法，我正在考虑以下方法：
<String, List<Human>> （或一个MultiMap）的散列集， 有一个更好的方法吗？
连接月份和国家有意义吗？ 名单会很大，所以我假设'更好'意味着存储量，而不是执行速度。
首先，你需要monthOfBirth + country将人类分为桶。 这应该是相当便宜的 - 只需遍历它们，将每一个弹入适当的桶。
请注意，追加字符串是解决这个问题的“黑客”方法。 “正确”的方法是用适当的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) {
...
}
}
请参阅：在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或其他方式。 您只需要能够通过存储桶和列表索引号合理快速地获取它们。
然后，您可以依次对每个桶应用业余爱好匹配算法，从而大幅度降低蛮力搜索的规模。
我看不出一种方法来避免将桶中的每个人与同一个桶中的其他人进行比较，但是你可以做一些工作来使比较便宜。
考虑将爱好编码为一个整数; 每个爱好一位。 长达64小时的爱好。 如果你需要更多，你将需要更多的整数或BigInteger（基准两种方法）。 当你通过人类工作并且遇到新的爱好时，你可以建立一些位置的字典来爱好业余爱好。 然后比较两组业余爱好是一个便宜的二进制“＆”，然后是Long.bitCount（）。
为了说明，第一个人有业余爱好[ "cooking", "cinema" ]
所以右边的位是“烹饪”，左边的下一位是“电影院”，这个人的编码爱好是二元{60 zeroes} 00011 == 3
下一个人喜欢[ "cooking", "fishing" ]
所以fishing会被添加到字典中，并且这种人类的编码爱好是{60 zeroes} 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.这两个人有一个共同的爱好。
为了处理你的第三个人：[“钓鱼”，“泡吧”，“国际象棋”]，你的成本是：
您需要将您的二进制编码爱好存储在真正便宜的地方。 我会试着用一个长的数组，并且有相应的人类索引：
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（n2）
如果你正在谈论真正庞大的数据集，我怀疑这种方法适合用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 - 所有的价值观 - 即在 - 汉密尔顿距离 - 根据我所理解的接受答案，这是一种方法，它将找到“非常高比例”的比赛，而不是全部，这我想这确实需要蛮力搜索。
散列通常是要走的路。 您可以作弊并将这两个值的哈希码一起添加到一起以形成组合的哈希码，而不是连接月份和国家。 这会为您节省一些处理工作量和内存使用量。 你也可以为记录定义.equals（）来实现你描述的匹配逻辑，这将使得哈希集直接检查匹配项是否存在。
这个结果假设你可以写一个蛮力方法。 有优化的余地，但通常这是正确的算法。
FindMatches (std::vector <Human> const & input, back_insert_iterator<vector> result)
{
typedef std::pair <std::string, std::string> key_type;
typedef std::vector <Human> Human_collection;
typedef std::map <key_type, Human_collection> map_type;
map_type my_map;
for (ci = input.begin(); ci != input.end(); ++ci)
{
key_type my_key(ci->monthOfBirth, ci->country);
my_map[my_key].push_back(*ci);
}
// Each value of my_map is now a collection of humans sharing the same birth statistics, which is the key.
for (ci = my_map.begin(); ci != my_map.end(); ++ci)
{
FindMatches_BruteForce (ci->second, result);
}
return;
}
这里有很多提高效率的空间，例如可以复制全部对象的指针，或者使用其他数据结构而不是地图，或者只是对输入容器进行就地排序。 但算法，我相信这是一样好。
链接地址: http://www.djcxy.com/p/70697.html