b*********n
发帖数: 1258 | 1 关于下面贴的这道面试题
当文件巨大，所有unique的单词不足以装到内存里面，
如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
如果要实现external merge sort, 感觉 复杂度就上来了
请问还有什么更好的办法吗？
====== 面试题 ======
coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
，然后反复这样做最终得到最后结果。 |
T****U
发帖数: 3344 | 2 给单词编码可以省不少空间，external merge sort也没什么麻烦的，只要是按字母排
序的 |
a*****u
发帖数: 1712 | 3 就是external merge的思路
关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
......
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
r**********g
发帖数: 22734 | 4 难道不用Hadoop/spark?
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
r**********g
发帖数: 22734 | 5 为啥要sort?只要grouping 就行了。标准的Hadoop 101
..
【在 a*****u 的大作中提到】
: 就是external merge的思路
:
: 关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
: batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
: ......
|
t**r
发帖数: 3428 | |
b*********n
发帖数: 1258 | 7 可是，要求现场编译运行
没办法跑Hadoop Job |
b**********5
发帖数: 7881 | 8 你自己可以在MAC上install hadoop， 然后run pig
【在 b*********n 的大作中提到】
: 可是，要求现场编译运行
: 没办法跑Hadoop Job
|
s********d
发帖数: 36 | |
r**********g
发帖数: 22734 | 10 当场运行就是
cat f | awk '{for(i=1;i<=NF;i++) print $i}' | sort -T 2G | uniq -c
你写完程序，oneliner 说不定已经跑完了
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
|
|
l*n
发帖数: 529 | 11 像是实现个mapreduce。merge时内存装不下的话，每次batch都用hash partition一下
，再merge每个partition应该就没啥压力了。
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
c*****y
发帖数: 62 | 12 什么时候的题？
正解是什么呢？
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
k******a
发帖数: 44 | 13 题目没有说，但是总体是要求统计词频吧
可不可以这样，
先分块，每块都能够用现有内存出，统计词频，按照字母排序，输出到一个文件。
然后中间文件两两合并，合并的时候边读边写，比如A,B，相当于磁头，读入数据A,B，
如果是同一个单词的，合并结果输出，如果不同先输出字母顺序小得，再输出大得，继
续。。 这个过程用不了多少内存
可能思路上还是外部排序。 |
b*********n
发帖数: 1258 | 14 关于下面贴的这道面试题
当文件巨大，所有unique的单词不足以装到内存里面，
如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
如果要实现external merge sort, 感觉 复杂度就上来了
请问还有什么更好的办法吗？
====== 面试题 ======
coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
，然后反复这样做最终得到最后结果。 |
T****U
发帖数: 3344 | 15 给单词编码可以省不少空间，external merge sort也没什么麻烦的，只要是按字母排
序的 |
a*****u
发帖数: 1712 | 16 就是external merge的思路
关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
......
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
r**********g
发帖数: 22734 | 17 难道不用Hadoop/spark?
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
r**********g
发帖数: 22734 | 18 为啥要sort?只要grouping 就行了。标准的Hadoop 101
..
【在 a*****u 的大作中提到】
: 就是external merge的思路
:
: 关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
: batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
: ......
|
t**r
发帖数: 3428 | |
b*********n
发帖数: 1258 | 20 可是，要求现场编译运行
没办法跑Hadoop Job |
|
|
b**********5
发帖数: 7881 | 21 你自己可以在MAC上install hadoop， 然后run pig
【在 b*********n 的大作中提到】
: 可是，要求现场编译运行
: 没办法跑Hadoop Job
|
s********d
发帖数: 36 | |
r**********g
发帖数: 22734 | 23 当场运行就是
cat f | awk '{for(i=1;i<=NF;i++) print $i}' | sort -T 2G | uniq -c
你写完程序，oneliner 说不定已经跑完了
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
l*n
发帖数: 529 | 24 像是实现个mapreduce。merge时内存装不下的话，每次batch都用hash partition一下
，再merge每个partition应该就没啥压力了。
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
c*****y
发帖数: 62 | 25 什么时候的题？
正解是什么呢？
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
k******a
发帖数: 44 | 26 题目没有说，但是总体是要求统计词频吧
可不可以这样，
先分块，每块都能够用现有内存出，统计词频，按照字母排序，输出到一个文件。
然后中间文件两两合并，合并的时候边读边写，比如A,B，相当于磁头，读入数据A,B，
如果是同一个单词的，合并结果输出，如果不同先输出字母顺序小得，再输出大得，继
续。。 这个过程用不了多少内存
可能思路上还是外部排序。 |
l**h
发帖数: 893 | 27 这样做如何：在内存里面开N个HashMap, 用来计数。每读到一个词语，做一个hash, 看
应该用哪个HashMap。 任何一个HashMap的size大于某个值的时候，就把里面的结果写
到磁盘，然后HashMap清零。磁盘上面有N个文件。要查任何一个词语的词频，就算一下
Hash, 然后找到对应的文件去查。
其实思想就是map reduce.
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
x*******1
发帖数: 28835 | 28 f 有1个PBytes， 怎么cat？
【在 r**********g 的大作中提到】
: 当场运行就是
: cat f | awk '{for(i=1;i<=NF;i++) print $i}' | sort -T 2G | uniq -c
: 你写完程序，oneliner 说不定已经跑完了
|
f*******r
发帖数: 976 | 29 题目就是external sort的思想。统计单词的次数，明显用map。注意文
件很大，要用long，以免溢出。
在你读文件并且增加这个map时，内存不够用，这是你要把临时结果写入临时文件。你
可以设计一个threshold，比如1 billion，当map的size达到这个值时，你就把map和临
时文件merge到另一个临时文件里。最后再把这个文件rename到原来的临时文件。再把
map清空，继续读原文件直到结束。 C++代码如下：
// Split the string into words that consists of a..z and A..Z.
void split(const string &s, vector &res) {
int beg = -1;
for (int i = 0, e = s.size(); i < e; ++i) {
if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
if (beg == -1) beg = i;
} else {
if (beg != -1) {
res.push_back(s.substr(beg, i-beg));
beg = -1;
}
}
}
if (beg != -1) res.push_back(s.substr(beg));
}
// split the string according to the delimiters.
void split(const string &s, vector &res, string delim) {
int beg = -1;
for (int i = 0, e = s.size(); i < e; ++i) {
if (delim.find(s[i]) == string::npos) {
if (beg == -1) beg = i;
} else {
if (beg != -1) {
res.push_back(s.substr(beg, i-beg));
beg = -1;
}
}
}
if (beg != -1) res.push_back(s.substr(beg));
}
// Merge the map with the counts in filename.
bool merge(const char *filename, map &m) {
ifstream in(filename);
ofstream os("tmp.txt");
if (!os.good()) return false;
string line;
map::const_iterator it = m.begin();
vector v;
getline(in, line);
split(line, v, ":");
while (in.good() && it != m.end()) {
if (v[0].compare((*it).first) == 0) {
os << v[0] << ":" << (atol(v[1].c_str()) + (*it).second) << "n";
getline(in, line);
v.resize(0);
split(line, v, ":");
++it;
} else if (v[0].compare((*it).first) < 0) {
os << v[0] << ":" << v[1] << "n";
getline(in, line);
v.resize(0);
split(line, v, ":");
} else {
os << (*it).first << ":" << (*it).second << "n";
++it;
}
}
// If there are still entries left in the map, write them to
// the new temporary file.
while (it != m.end()) {
os << (*it).first << ":" << (*it).second << "n";
++it;
}
// If the file is not finished, write the rest to the new temporary file.
while (in.good()) {
os << v[0] << ":" << v[1] << "n";
getline(in, line);
v.resize(0);
split(line, v, ":");
}
// close the temporary files.
in.close();
os.close();
m.clear();
// we rename the new temporary file back to the original temporary file.
if (rename("tmp.txt", filename) != 0) {
return false;
}
return true;
}
// Assume that there is not enough memory on the machine. We only store part
// of the final map in the memory and the rest is written into a temporary
file.
void writeBackToFile(const char *filename, const char *outfile) {
ifstream in(filename);
if (!in.good()) {
std::cerr << "Failed to open file " << filename << "n";
exit(1);
}
string s;
vector words;
map m;
while (in.good()) {
getline(in, s);
words.resize(0);
split(s, words);
for (int i = 0, e = words.size(); i < e; ++i) {
m[words[i]]++;
}
if (m.size() >= 10000) {
// Persist the data to the disk.
if (!merge(outfile, m)) {
std::cerr << "Error: " << __LINE__ << "n";
exit(1);
}
}
}
if (!merge(outfile, m)) {
std::cerr << "Errorn";
exit(1);
}
}
关于下面贴的这道面试题
当文件巨大，所有unique的单词不足以装到内存里面，
如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
如果要实现external merge sort, 感觉 复杂度就上来了
请问还有什么更好的办法吗？
====== 面试题 ======
coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
，然后反复这样做最终得到最后结果。
【在 b*********n 的大作中提到】
: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉 复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。
|
