p*****p 发帖数: 379 | 1 一个很大hashmap里存了64位的long类型hashcode,给定一个long,判断它和其他所有
hashcode是否存在hamming distance不超过3的子集,如果有,返回这些子集
最简单当然是把所有值都计算一遍,但那样太慢了
如果map是有序的,看起来只要找“附近”的值就行了,问题是如何找出这些值,我感
觉组合一下也不少了……
(注:hamming distance就是两个二进制之间不同位的数量之和,如101和110距离是2
) | l***i 发帖数: 1309 | 2 suppose you are looking for all 8-bit integer with hamming distance at most
3 with a given integer 10010010, then you can generate all possible 8-bit
integers and try each of them to see if it is in your hashmap.
For 64-bit integers, only (64 choose 3) positions can be different, for each
of the 3 positions you have at most 2^3 bit patterns, so you
only have (64 choose 3) * 2^3 = 10^6 integers to search in your hashmap,
should be
done in less than 1 sec. | p*****p 发帖数: 379 | 3 All right so that's 64*63*62*8 = 1999872
since the size of the map is not stable so seems to be better to compare the
size to that number, if it's less than that, seems the iteration method
could be faster and vice versa?
most
each
【在 l***i 的大作中提到】 : suppose you are looking for all 8-bit integer with hamming distance at most : 3 with a given integer 10010010, then you can generate all possible 8-bit : integers and try each of them to see if it is in your hashmap. : For 64-bit integers, only (64 choose 3) positions can be different, for each : of the 3 positions you have at most 2^3 bit patterns, so you : only have (64 choose 3) * 2^3 = 10^6 integers to search in your hashmap, : should be : done in less than 1 sec.
| h**6 发帖数: 4160 | 4 距离为0的数,C(64, 0) = 1个。
距离为1的数,C(64, 1) = 64个。
距离为2的数,C(64, 2) = 2016个。
距离为3的数,C(64, 3) = 41664个。
找找这43745个数在原图中是否存在即可。 | l***i 发帖数: 1309 | 5 nice counting.
【在 h**6 的大作中提到】 : 距离为0的数,C(64, 0) = 1个。 : 距离为1的数,C(64, 1) = 64个。 : 距离为2的数,C(64, 2) = 2016个。 : 距离为3的数,C(64, 3) = 41664个。 : 找找这43745个数在原图中是否存在即可。
|
|