a*u
发帖数: 97 | 1 朋友刚刚面的。好像之前有人讨论过类似海量数据找重复的。但是找不到了。觉得这类
题挺经典的，所以再放上来听听大家意见。
1TB data on disk with around 1KB per data record. Find duplicates using
512MB RAM and infinite disk space.
My thoughts are external sorting. The data have around the 1 million records
- 512MB can hold around 0.5 million records, so we need around 2000 rounds
of in-memory quick sort and then merge and find duplicates.
Bloomfilter may not work since 512MB memory can only spare 4 bits for each
record, which will yield a high error rate (opt |
t******e
发帖数: 1293 | 2 我觉得就如果用external sorting，那IO access可能需要很多遍。
假设现在1T分成了10000个小文件，每个里面都去重了。
把这10000个小文件合起来去重的时候，假设合了1000个的时候，
得到的新文件的大小 > 512M了，那你再想把1001个合进来的时候，
怎么办？
records
rounds
【在 a*u 的大作中提到】
: 朋友刚刚面的。好像之前有人讨论过类似海量数据找重复的。但是找不到了。觉得这类
: 题挺经典的，所以再放上来听听大家意见。
: 1TB data on disk with around 1KB per data record. Find duplicates using
: 512MB RAM and infinite disk space.
: My thoughts are external sorting. The data have around the 1 million records
: - 512MB can hold around 0.5 million records, so we need around 2000 rounds
: of in-memory quick sort and then merge and find duplicates.
: Bloomfilter may not work since 512MB memory can only spare 4 bits for each
: record, which will yield a high error rate (opt
|
t******e
发帖数: 1293 | 3 去重是否要保持原来的顺序？
records
rounds
【在 a*u 的大作中提到】
: 朋友刚刚面的。好像之前有人讨论过类似海量数据找重复的。但是找不到了。觉得这类
: 题挺经典的，所以再放上来听听大家意见。
: 1TB data on disk with around 1KB per data record. Find duplicates using
: 512MB RAM and infinite disk space.
: My thoughts are external sorting. The data have around the 1 million records
: - 512MB can hold around 0.5 million records, so we need around 2000 rounds
: of in-memory quick sort and then merge and find duplicates.
: Bloomfilter may not work since 512MB memory can only spare 4 bits for each
: record, which will yield a high error rate (opt
|
t******e
发帖数: 1293 | 4 1. 1T大小的文件，每行1K，所以有1G行
1G = 2^30，所以，我们可以对每行算一个hash值，如果哈希函数选得好，
我们只需要4 bytes，因为4 bytes能表示2^32个值 > 2^30
2. 生成一个中间文件用4 bytes存储哈希值，另外用4 bytes来保存在原文件里面的行数
一共需要1G * 8 = 8G的空间
如果要求新文件里面的每行不要求保持原文件每行的次序，可以直接建立一个长为2^32
的bitmap，扫描新文件，并且设每个bit，把bit设为1所关联的行保留，其它去掉。
结束。
如果要求保持原来的次序：
3. 把8G分成32个256M的文件，分别把每个256M的文件读到内存里面，并且去重，去重
结果写到新文件。512M内存>256M内存，这一步可以很快。
如果要求新文件里面的每行不要求保持原文件每行的次序，可以直接建立一个长为2^32
的bitmap，扫描新文件，并且设每个bit，把bit设为1所关联的行保留，其它去掉。
4. 把32个新文件，两两合在一起去重，得到新的16个新文件。（这16个新文件的大小
可能会很接近512M了）
5. ......
【在 t******e 的大作中提到】
: 我觉得就如果用external sorting，那IO access可能需要很多遍。
: 假设现在1T分成了10000个小文件，每个里面都去重了。
: 把这10000个小文件合起来去重的时候，假设合了1000个的时候，
: 得到的新文件的大小 > 512M了，那你再想把1001个合进来的时候，
: 怎么办？
:
: records
: rounds
|
a*u
发帖数: 97 | 5 应该是不需要保留原文件次序。
如果可以有one to one compact hash mapping当然好啊，1 million records map to
1G bits，只需要125MB内存了。但是这样的hashing很难找吧，bloom filter就是顺着
这个解法思路的，用多个hashing function 和更多bits per records。
行数
32
【在 t******e 的大作中提到】
: 1. 1T大小的文件，每行1K，所以有1G行
: 1G = 2^30，所以，我们可以对每行算一个hash值，如果哈希函数选得好，
: 我们只需要4 bytes，因为4 bytes能表示2^32个值 > 2^30
: 2. 生成一个中间文件用4 bytes存储哈希值，另外用4 bytes来保存在原文件里面的行数
: 一共需要1G * 8 = 8G的空间
: 如果要求新文件里面的每行不要求保持原文件每行的次序，可以直接建立一个长为2^32
: 的bitmap，扫描新文件，并且设每个bit，把bit设为1所关联的行保留，其它去掉。
: 结束。
: 如果要求保持原来的次序：
: 3. 把8G分成32个256M的文件，分别把每个256M的文件读到内存里面，并且去重，去重
|
g**t
发帖数: 49 | 6 My try:
1M records, 512MB memory
Initialize 512MB memory into 512*8M (4G) bit map
Use hash function to map each record to a value between (0~4G)
probability of being false positive is 1M / 4GB (0.00025) (still bad, maybe
we can try multi-round) |
g**t
发帖数: 49 | 7 aku is right. Sorry for HUA SHE TIAN ZU :)
the point is how to find such a good hash function :) |
g**********1
发帖数: 1113 | |
g**t
发帖数: 49 | 9 Now I think it is not too hard to find such hash function :)
Simply calculate md5 sum of the record then mod 4G and get the index
【在 g**t 的大作中提到】
: aku is right. Sorry for HUA SHE TIAN ZU :)
: the point is how to find such a good hash function :)
|
x*****g
发帖数: 5 | 10 how about this:
using a hash function f : records -> [1..N],
we can go through all data for N times, and in the i-th round,
we only update the 512x8 M bit bloom filter by those records whose hash
result is i.
in this way, duplications of the same record are always processed in the
same round.
since there are 1G records, in each round, we need to store around 1/N G
records in the bloom filter.
for example, by setting N=4, the load of our bloom filter is (1/4*1024)/(512
*8)=1/16.
we can optimize t |
|
|
m****y
发帖数: 28 | 11 我来说个比较可行的思路吧
首先人家给了disk space就是让你放些中间结果的
我的想法是用hash来先把data record粗略归类到很小的子集，然后在每个子集里面找
重复就可以了。
1. 对每个data record，我们生成一个形如的ID，假设用md5作
为hash函数，再假设record number占用4个字节，那么每个ID的大小是16+4=20字节。
2. 生成ID的时候，把它归类到一个较小的子集，写到磁盘上去。对于2^30个record，
我们根据(hash mod 2^13)的结果，把它分成2^13个子集，每个子集存成一个文件，每
个文件包含大约2^17个record的ID，这样子集文件的平均大小大概是2^17*20=2MB左右
，总共需要大约2^30*20=4GB的磁盘空间。
3. 最后就是把这么些子集文件读到内存里，然后找重复。显然重复的data record的ID
肯定属于同一个子集，简单的办法是把这2MB的数据排个序，对于重复的hash再根据
record number去读实际的data record来作比较。这样基
【在 a*u 的大作中提到】
: 朋友刚刚面的。好像之前有人讨论过类似海量数据找重复的。但是找不到了。觉得这类
: 题挺经典的，所以再放上来听听大家意见。
: 1TB data on disk with around 1KB per data record. Find duplicates using
: 512MB RAM and infinite disk space.
: My thoughts are external sorting. The data have around the 1 million records
: - 512MB can hold around 0.5 million records, so we need around 2000 rounds
: of in-memory quick sort and then merge and find duplicates.
: Bloomfilter may not work since 512MB memory can only spare 4 bits for each
: record, which will yield a high error rate (opt
|
l********i
发帖数: 115 | 12 >> 1TB data on disk with around 1KB per data record.
It means there are 1GB number of integers.
If we use bitset, one bit to represent one integer, we only need 1GB/8 =
256MB main memory. |
j********9
发帖数: 603 | 13 这样的问题是考察一个人的思考能力，但是如果实际工作中难道每个google的人都是不
管拿来一个什么样的问题都咔咔的在一个店面的时间里都能搞定？类似这样的问题难道
讨论一下不会有更好的结果？为什么非要在店面里问？本人菜鸟，出于好奇，难道
google的每个人都是算法大牛？那为什么不去学校搞算法，那个图灵什么的不更有意义
？搞得这些东西都像八股似的。。。。 一个intern本来就是学习长经验的机会，搞得
跟过去就能解决最棘手的问题似的。 |
m*****f
发帖数: 1243 | 14 我想interviewer并没有奢望在一个电面的时间内解决这个问题, 只是考察思考能力.
【在 j********9 的大作中提到】
: 这样的问题是考察一个人的思考能力，但是如果实际工作中难道每个google的人都是不
: 管拿来一个什么样的问题都咔咔的在一个店面的时间里都能搞定？类似这样的问题难道
: 讨论一下不会有更好的结果？为什么非要在店面里问？本人菜鸟，出于好奇，难道
: google的每个人都是算法大牛？那为什么不去学校搞算法，那个图灵什么的不更有意义
: ？搞得这些东西都像八股似的。。。。 一个intern本来就是学习长经验的机会，搞得
: 跟过去就能解决最棘手的问题似的。
|
j********9
发帖数: 603 | 15 弱问一下，如果两个dup相距很远，每次拿两个子集在内存里也不能遇见的时候怎么办
呢？
【在 m****y 的大作中提到】
: 我来说个比较可行的思路吧
: 首先人家给了disk space就是让你放些中间结果的
: 我的想法是用hash来先把data record粗略归类到很小的子集，然后在每个子集里面找
: 重复就可以了。
: 1. 对每个data record，我们生成一个形如的ID，假设用md5作
: 为hash函数，再假设record number占用4个字节，那么每个ID的大小是16+4=20字节。
: 2. 生成ID的时候，把它归类到一个较小的子集，写到磁盘上去。对于2^30个record，
: 我们根据(hash mod 2^13)的结果，把它分成2^13个子集，每个子集存成一个文件，每
: 个文件包含大约2^17个record的ID，这样子集文件的平均大小大概是2^17*20=2MB左右
: ，总共需要大约2^30*20=4GB的磁盘空间。
|
m*****g
发帖数: 226 | 16 这个题应该是很open的题
真的能完美解决大家就直接开店去吧
我的看法，前面的大家说的hash，用4 byte左右的空间放hash value，然后4byte放行
号。
生成的中间文件大小8GB。
把这个8GB分成32个256MB的文件，然后两两合并。碰到一样的hash value，就按照行号
检查是否dup，是的话去掉。其实这最后一步就是external sort了。
专业的做法确实是bloom filter。但是那个参数不好配。 |
