y****t
发帖数: 23 | 1 给一个文件
a 1 2 3 4 5
b 1 3 4 68 0
c 7 2 9 3 1
程序读完这个文件后
user输入 1 2 3 4 5
return a //因为a后面含有最多和用户输入相同的数
user输入 1
return a //因为a,b,c都含有1,return first one
user输入 1 2 3 4 68 0
return b //因为b含有最多这个数
假如文件有1百万行这种data
该怎么设计和match 最快最logical | p*****2
发帖数: 21240 | 2
Reverse Index吗？
【在 y****t 的大作中提到】
: 给一个文件
: a 1 2 3 4 5
: b 1 3 4 68 0
: c 7 2 9 3 1
: 程序读完这个文件后
: user输入 1 2 3 4 5
: return a //因为a后面含有最多和用户输入相同的数
: user输入 1
: return a //因为a,b,c都含有1,return first one
: user输入 1 2 3 4 68 0
| g*****e
发帖数: 282 | 3 这个reversed index的value数据结构怎么设计呢，set？我的想法类似，对任意一个已
知candidate，做类似bloom filter的处理，如果有0-999里的一个数，set一位，有
1000-1999里的一个数，set另一位，。。。>999999999，set最后一位（假设都是非负
整数），最终得到一个bit vector。这样可以较快根据输入（把输入map成一个bit
vector）缩小范围（hash），然后在缩小的范围里brute force。
【在 p*****2 的大作中提到】
:
: Reverse Index吗？
| y****t
发帖数: 23 | 4 对bloom filter不是很熟悉，学习了
我的方法是这样子的
读的时候建一个table
key: 1 2 3 4...., value: a b c d....
这题就是
1 a b c
2 a c
3 a b c
4 a b
如果user输入 1 2 3 4
1 先就把a b c放入一个新的lookup map(key: a b c.... , value: 1, 2, 3,4...出现
的次数)
2 把a c 在lookup map里面对应的值++
最后return出现次数最大的值
这个方法要很多memory,不知道runtime有没有比bloom filter快
【在 g*****e 的大作中提到】
: 这个reversed index的value数据结构怎么设计呢，set？我的想法类似，对任意一个已
: 知candidate，做类似bloom filter的处理，如果有0-999里的一个数，set一位，有
: 1000-1999里的一个数，set另一位，。。。>999999999，set最后一位（假设都是非负
: 整数），最终得到一个bit vector。这样可以较快根据输入（把输入map成一个bit
: vector）缩小范围（hash），然后在缩小的范围里brute force。
| s*****1
发帖数: 134 | 5 前面和楼上想的一样，但我想构造一个lookup table和priority queue 一起，lookup
table起到 找到 a 和 c 在priority queue中位置的作用，然后a和c再增加priority | m*****k
发帖数: 731 | 6 Largest common subsequence.? Use the seq u wanna compare as the key, here '
1234", a as val, iterate through all key, take the one with most match,
return the value. |
|
