苹果官网悄悄上架一部手机，售价仅四百刀 - 未名空间MITBBS历史存档

苹果官网悄悄上架一部手机，售价仅四百刀# PDA - 掌中宝

b*n2018-08-16 07:08

1 楼

关于下面贴的这道面试题
当文件巨大，所有unique的单词不足以装到内存里面，
如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
如果要实现external merge sort, 感觉复杂度就上来了
请问还有什么更好的办法吗？
====== 面试题 ======
coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
，然后反复这样做最终得到最后结果。

n*s2018-08-16 07:08

2 楼

苹果的新手机用不了多长时间就要正式的上市了，无论是在售价上还是硬件上能被爆料
的基本上都被曝出来了。
价钱确实会在七百刀左右，尺寸确实是6.1···
但我不想说新的苹果机器，而是要说一个苹果官网上最近两天悄悄的发布了一个别的新
机器，而这部手机的售价仅仅只有四百刀左右。
什么手机会那么便宜？其实是官方翻新的苹果7，也就是那些库存货和之前有问题需要
返修的机器。
现在翻新一下又拿出来卖了，但就算这样也很便宜了啊，四百多刀，比新机器便宜一半
，大家可以去官网看看。

T*U2018-08-16 07:08

3 楼

给单词编码可以省不少空间，external merge sort也没什么麻烦的，只要是按字母排
序的

a*u2018-08-16 07:08

4 楼

就是external merge的思路

关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
......

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

r*g2018-08-16 07:08

5 楼

难道不用Hadoop/spark?

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

r*g2018-08-16 07:08

6 楼

为啥要sort?只要grouping 就行了。标准的Hadoop 101

..

【在 a*****u 的大作中提到】

: 就是external merge的思路
:
: 关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
: batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
: ......

t*r2018-08-16 07:08

7 楼

hadoop mapreduce.

b*n2018-08-16 07:08

8 楼

可是，要求现场编译运行
没办法跑Hadoop Job

b*52018-08-16 07:08

9 楼

你自己可以在MAC上install hadoop，然后run pig

【在 b*********n 的大作中提到】

: 可是，要求现场编译运行
: 没办法跑Hadoop Job

s*d2018-08-16 07:08

10 楼

trie?

r*g2018-08-16 07:08

11 楼

当场运行就是
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*n2018-08-16 07:08

12 楼

像是实现个mapreduce。merge时内存装不下的话，每次batch都用hash partition一下
，再merge每个partition应该就没啥压力了。

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

c*y2018-08-16 07:08

13 楼

什么时候的题？
正解是什么呢？

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

k*a2018-08-16 07:08

14 楼

题目没有说，但是总体是要求统计词频吧
可不可以这样，
先分块，每块都能够用现有内存出，统计词频，按照字母排序，输出到一个文件。
然后中间文件两两合并，合并的时候边读边写，比如A,B，相当于磁头，读入数据A,B，
如果是同一个单词的，合并结果输出，如果不同先输出字母顺序小得，再输出大得，继
续。。这个过程用不了多少内存
可能思路上还是外部排序。

b*n2018-08-16 07:08

15 楼

关于下面贴的这道面试题
当文件巨大，所有unique的单词不足以装到内存里面，
如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
如果要实现external merge sort, 感觉复杂度就上来了
请问还有什么更好的办法吗？
====== 面试题 ======
coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
，然后反复这样做最终得到最后结果。

T*U2018-08-16 07:08

16 楼

给单词编码可以省不少空间，external merge sort也没什么麻烦的，只要是按字母排
序的

a*u2018-08-16 07:08

17 楼

就是external merge的思路

关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
......

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

r*g2018-08-16 07:08

18 楼

难道不用Hadoop/spark?

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

r*g2018-08-16 07:08

19 楼

为啥要sort?只要grouping 就行了。标准的Hadoop 101

..

【在 a*****u 的大作中提到】

: 就是external merge的思路
:
: 关于下面贴的这道面试题当文件巨大，所有unique的单词不足以装到内存里面，如果分
: batch来处理，在merge的时候，内存也还是装不下，怎么办？如果要实现external m..
: ......

t*r2018-08-16 07:08

20 楼

hadoop mapreduce.

b*n2018-08-16 07:08

21 楼

可是，要求现场编译运行
没办法跑Hadoop Job

b*52018-08-16 07:08

22 楼

你自己可以在MAC上install hadoop，然后run pig

【在 b*********n 的大作中提到】

: 可是，要求现场编译运行
: 没办法跑Hadoop Job

s*d2018-08-16 07:08

23 楼

trie?

r*g2018-08-16 07:08

24 楼

当场运行就是
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*n2018-08-16 07:08

25 楼

像是实现个mapreduce。merge时内存装不下的话，每次batch都用hash partition一下
，再merge每个partition应该就没啥压力了。

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

c*y2018-08-16 07:08

26 楼

什么时候的题？
正解是什么呢？

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

k*a2018-08-16 07:08

27 楼

题目没有说，但是总体是要求统计词频吧
可不可以这样，
先分块，每块都能够用现有内存出，统计词频，按照字母排序，输出到一个文件。
然后中间文件两两合并，合并的时候边读边写，比如A,B，相当于磁头，读入数据A,B，
如果是同一个单词的，合并结果输出，如果不同先输出字母顺序小得，再输出大得，继
续。。这个过程用不了多少内存
可能思路上还是外部排序。

l*h2018-08-16 07:08

28 楼

这样做如何：在内存里面开N个HashMap, 用来计数。每读到一个词语，做一个hash, 看
应该用哪个HashMap。任何一个HashMap的size大于某个值的时候，就把里面的结果写
到磁盘，然后HashMap清零。磁盘上面有N个文件。要查任何一个词语的词频，就算一下
Hash, 然后找到对应的文件去查。
其实思想就是map reduce.

【在 b*********n 的大作中提到】

: 关于下面贴的这道面试题
: 当文件巨大，所有unique的单词不足以装到内存里面，
: 如果分batch来处理，在merge的时候，内存也还是装不下，怎么办？
: 如果要实现external merge sort, 感觉复杂度就上来了
: 请问还有什么更好的办法吗？
: ====== 面试题 ======
: coding第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。

x*12018-08-16 07:08

29 楼

f 有1个PBytes，怎么cat？

【在 r**********g 的大作中提到】

: 当场运行就是
: cat f | awk '{for(i=1;i<=NF;i++) print $i}' | sort -T 2G | uniq -c
: 你写完程序，oneliner 说不定已经跑完了

f*r2018-08-16 07:08

30 楼

题目就是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第一面让我实现一个词频统计，但是测试文件巨大，读啊读的不同的词就超了内
: 存了。结果面试官提醒我要注意存中间结果，所以是读一批，统计一批，然后写回文件
: ，然后反复这样做最终得到最后结果。