微信首页出现自己怎么弄的？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

微信首页出现自己怎么弄的？

微信首页出现自己怎么弄的？# PDA - 掌中宝

s*x2015-01-14 08:01

1 楼

【以下文字转载自 SanFrancisco 讨论区】
发信人: microbe (天涯思君不可忘), 信区: SanFrancisco
标题: New solution for iPhone 4 antenna problem
发信站: BBS 未名空间站 (Tue Jun 29 21:39:46 2010, 美东)

s*a2015-01-14 08:01

2 楼

If you have a 2 GB file with one string per line, which sorting algorithm
would you use to sort the file and why?
书里给出的解法是：
1. Divide the file into K chunks, where X * K = 2 GB. Bring each chunk into
memory and sort the lines as usual using any O(n log n) algorithm. Save the
lines back to the file.
2. Now bring the next chunk into memory and sort.
3. Once we’re done, merge them one by one.
其中一个假定是每次不使用超过X的memory,但是最后一步怎么能满足这个条件呢？

i*a2015-01-14 08:01

3 楼

Thanks

u*p2015-01-14 08:01

4 楼

rt，谢谢。

p*e2015-01-14 08:01

5 楼

M*62015-01-14 08:01

6 楼

这个是external sorting吧
merge阶段的buffer是不超过memory的

s*s2015-01-14 08:01

7 楼

why not bear-put spread?

x*u2015-01-14 08:01

8 楼

突然觉得自己语文没学好。。。
[发表自未名空间手机版 - m.mitbbs.com]

l*d2015-01-14 08:01

9 楼

比如说有 9G 的 file, 但是内存只有 1G。
首先分成 9段，每段 1G。分段读入内存排序，写到临时的文件。
归并阶段，对每个排好序的小段，读入 100M，总共 900 M，然后用剩下的 100M 作为
buffer。
每次 buffer 满了就写入到最终的文件。

i*a2015-01-14 08:01

10 楼

how? Can you give me detail order?

u*p2015-01-14 08:01

11 楼

我意思是通讯录可以看见自己，微信首页应该看见你的朋友，不应该看见自己才对吧？

M*62015-01-14 08:01

12 楼

merge的时候每当output buffer满就输出写一次，每当input buffer空就从相应input
读一次

s*s2015-01-14 08:01

13 楼

google "bear put spread" and you will find a lot of examples.
YMYD
with that, at least you know your maximum loss and gain.

l*s2015-01-14 08:01

14 楼

还是没懂

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

: 我意思是通讯录可以看见自己，微信首页应该看见你的朋友，不应该看见自己才对吧？

s*c2015-01-14 08:01

15 楼

最后一步是multi-way merge，这时每一行已经是排好序的，分别取每行的第一个data
（最小），拿到内存里，所以是K个data在内存，只要k < x 就没有问题。整个merge过
程建一个heap,每次找到最小的元素，写到output里，同时最小的元素从哪一行来的，
就从那一行再取下一个元素，然后maintain这个heap，再找到最小的继续写到output。
最后直到这个heap空了为止

u*p2015-01-14 08:01

16 楼

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

: 我意思是通讯录可以看见自己，微信首页应该看见你的朋友，不应该看见自己才对吧？