x******u
发帖数: 259 | 1 面试中一道题是这样的。
１００ Ｇ file, everyline is a key,value comma separated , return the non-
redundant key value pairs．
我的问题是，如果我用C++答题。 面试官是否要考我 parsing file line by line?
or just I can assume input as a vector? 这题用unordered_map 成吗？有更好办法
吗？ | a******u
发帖数: 69 | 2 遇到这种题你先要问面试官，有多少G的内存可以使用。
比如说10G。
这时你就要把这个100G的文件分成10个10G的部分。
然后对每一部分由小到大排序，顺便删掉重复的key, value pair。
然后你得到了10组文件F0, F1, ..., F9。每组里面都是non-redundant的。
但组与组之间还是会有redundant。
这时你就从每组中各拿排序后最前面的1G的key, value出来，塞进内存里。
然后内存里就有了10个1G的sorted array: A[0], A[1], ..., A[9].
每次取A[0], A[1], ..., A[9]的最前面的key，value值：A[0].front(), A[1].front(
), ..., A[9].front()。然后这个10个key，value里找出最小的值。然后把该值输出。
然后把A[0].front(), A[1].front(), ..., A[9].front()跟该值相同的值pop出来。
如果某个A[i]为空，则从对应的文件Fi读取1G的key-value出来。
直到把所有文件F都读出来为止。 | p*****2
发帖数: 21240 | 3 这个做sharding也可以吧？是不是更容易？比排序要简单吧？
front(
【在 a******u 的大作中提到】
: 遇到这种题你先要问面试官，有多少G的内存可以使用。
: 比如说10G。
: 这时你就要把这个100G的文件分成10个10G的部分。
: 然后对每一部分由小到大排序，顺便删掉重复的key, value pair。
: 然后你得到了10组文件F0, F1, ..., F9。每组里面都是non-redundant的。
: 但组与组之间还是会有redundant。
: 这时你就从每组中各拿排序后最前面的1G的key, value出来，塞进内存里。
: 然后内存里就有了10个1G的sorted array: A[0], A[1], ..., A[9].
: 每次取A[0], A[1], ..., A[9]的最前面的key，value值：A[0].front(), A[1].front(
: ), ..., A[9].front()。然后这个10个key，value里找出最小的值。然后把该值输出。
| x******u
发帖数: 259 | | g********r
发帖数: 89 | 5 mark
non-
【在 x******u 的大作中提到】
: 面试中一道题是这样的。
: １００ Ｇ file, everyline is a key,value comma separated , return the non-
: redundant key value pairs．
: 我的问题是，如果我用C++答题。 面试官是否要考我 parsing file line by line?
: or just I can assume input as a vector? 这题用unordered_map 成吗？有更好办法
: 吗？
| s*****4
发帖数: 25 | 6 能不能用unordered_set这样做呢?
1. 假设有1G内存, 且unordered_set需要0.5G内存, 则把100G file分成20分, 每个0.
5G, 如此一来, 内存能装的下一个unordered_map和一个0.5G file
2. 接下一次读一个0.5G file进内存, 并把此file中所有line(key value pair)丢入
unordered_set
3. 依序处理这20个files(用他们update同一个unordered_set), 最终结果就在
unordered_set里 |
|
