g********d
发帖数: 203 | 1 How to sort 1 million integers with 2MB of memory and with no external
storage?
这个怎么做啊？ |
h****n
发帖数: 1093 | 2 bitmap 1million = 2^20 bit = 2^17 byte = 2^7 KB = 1MB/8 = 0.125MB |
g********d
发帖数: 203 | 3 forgot to mention, they are 32-bit integers |
g********d
发帖数: 203 | 4 it's not integers range from 1 to million, it's 1 million of 32bit integers
【在 h****n 的大作中提到】
: bitmap 1million = 2^20 bit = 2^17 byte = 2^7 KB = 1MB/8 = 0.125MB
|
h****n
发帖数: 1093 | 5 那也得有个limit的范围啊
否则没有不需要external storage的算法
允许external storage的话你可以看看N-way sort
【在 g********d 的大作中提到】
: forgot to mention, they are 32-bit integers
|
g********d
发帖数: 203 | 6 就是没有limit范围，所以才不知道该怎么做。说明不能用external storage
【在 h****n 的大作中提到】
: 那也得有个limit的范围啊
: 否则没有不需要external storage的算法
: 允许external storage的话你可以看看N-way sort
|
h****n
发帖数: 1093 | 7 突然想起来了
1 million的数字不就刚好能装进2MB的内存吗？？
直接用quick sort 之类的inplace sorting搞定
【在 h****n 的大作中提到】
: 那也得有个limit的范围啊
: 否则没有不需要external storage的算法
: 允许external storage的话你可以看看N-way sort
|
g********d
发帖数: 203 | |
h****n
发帖数: 1093 | 9 哦，对，没啥想法了，看看别的大牛吧
我直观感觉吧，没有解法
因为你只能把int先装一半进来sort，然后总得你输出吧这就不能避免external
storage了 |
s******e
发帖数: 493 | 10 how about this:
1. sorts the first half a million using a in place sort
2. writes the sorted set back to overwrite the original memory for those
half a million ints.
3. repeat step 1 and 2 to finish the second half.
4. does the merge sort on the two sorted halves.
5. at certain point, consolidates the processed original memory from two
halves so we can write back the sorted results to the head of the original
memory. Three pointers need to be kept during the process: the current
position for sorted index; the current position for processed index from
first half, and the current position for processed index from second half.
Just a quick and rough idea. "pao zhuan yen yu". HAHA... |
|
|
h****n
发帖数: 1093 | 11 说实话，没看明白。。
OK，这里现在memory存了sorted好的另一半
你write back去那里？不允许用external storage了
【在 s******e 的大作中提到】
: how about this:
: 1. sorts the first half a million using a in place sort
: 2. writes the sorted set back to overwrite the original memory for those
: half a million ints.
: 3. repeat step 1 and 2 to finish the second half.
: 4. does the merge sort on the two sorted halves.
: 5. at certain point, consolidates the processed original memory from two
: halves so we can write back the sorted results to the head of the original
: memory. Three pointers need to be kept during the process: the current
: position for sorted index; the current position for processed index from
|
s******e
发帖数: 493 | 12 destories the original input storage. |
p****n
发帖数: 51 | 13 输出应该不算用external吧
【在 h****n 的大作中提到】
: 哦，对，没啥想法了，看看别的大牛吧
: 我直观感觉吧，没有解法
: 因为你只能把int先装一半进来sort，然后总得你输出吧这就不能避免external
: storage了
|
h****n
发帖数: 1093 | 14 显然不让用，让用external storage的限制就没有任何意义
【在 s******e 的大作中提到】
: destories the original input storage.
|
h****n
发帖数: 1093 | 15 是不算，问题是你输出前面一半之后，后面一半怎么办，你得到的只是两段sorted好的
，而不是整个sorted好的
如果允许重新读入内存做merge sort，那就又回到external storage的问题了
【在 p****n 的大作中提到】
: 输出应该不算用external吧
|
p****n
发帖数: 51 | 16 如果可以，你看怎么搞咋样
用那2MB做个堆，读一边输入，找到小的一半，然后sort输出
然后再读一边输入，找到大的一半，然后sort输出
这样两个输出应该可以接在一起
【在 h****n 的大作中提到】
: 是不算，问题是你输出前面一半之后，后面一半怎么办，你得到的只是两段sorted好的
: ，而不是整个sorted好的
: 如果允许重新读入内存做merge sort，那就又回到external storage的问题了
|
h****n
发帖数: 1093 | 17 不行的，我理解没错的话，你是切成两段，然后两边读，入堆，找小的输出
但是这种做法的前提是那两段是sorted好的
举个例子
前半段3 4 5 1 2 3
后半段7 8 9 10 11 12
你的输出会是：
3 4 5 1 2 3 7 8 9 10 11 12
【在 p****n 的大作中提到】
: 如果可以，你看怎么搞咋样
: 用那2MB做个堆，读一边输入，找到小的一半，然后sort输出
: 然后再读一边输入，找到大的一半，然后sort输出
: 这样两个输出应该可以接在一起
|
t****t
发帖数: 6806 | 18 first question is, how is the integer provided?
【在 g********d 的大作中提到】
: How to sort 1 million integers with 2MB of memory and with no external
: storage?
: 这个怎么做啊？
|
h****n
发帖数: 1093 | 19 我理解错了，如果建立起2MB的堆，貌似应该可以
【在 p****n 的大作中提到】
: 如果可以，你看怎么搞咋样
: 用那2MB做个堆，读一边输入，找到小的一半，然后sort输出
: 然后再读一边输入，找到大的一半，然后sort输出
: 这样两个输出应该可以接在一起
|
p****n
发帖数: 51 | 20 不是，我不分割输入，只是需要读两边输入
假设输入是
3 7 4 8 5 9 1 10 2 11 3 12
现在我只有存六个整数的空间
我读第一边，应该可以用最大堆找到1 2 3 4 5 6并输出吧
然后我再读一边，用最小堆找到 7 8 9 10 11 12并输出
【在 h****n 的大作中提到】
: 不行的，我理解没错的话，你是切成两段，然后两边读，入堆，找小的输出
: 但是这种做法的前提是那两段是sorted好的
: 举个例子
: 前半段3 4 5 1 2 3
: 后半段7 8 9 10 11 12
: 你的输出会是：
: 3 4 5 1 2 3 7 8 9 10 11 12
|
|
|
h****n
发帖数: 1093 | 21 知道了
应该可以吧
【在 p****n 的大作中提到】
: 不是，我不分割输入，只是需要读两边输入
: 假设输入是
: 3 7 4 8 5 9 1 10 2 11 3 12
: 现在我只有存六个整数的空间
: 我读第一边，应该可以用最大堆找到1 2 3 4 5 6并输出吧
: 然后我再读一边，用最小堆找到 7 8 9 10 11 12并输出
|
g********d
发帖数: 203 | 22 integers are provided as network stream, so there's no storage
【在 s******e 的大作中提到】
: how about this:
: 1. sorts the first half a million using a in place sort
: 2. writes the sorted set back to overwrite the original memory for those
: half a million ints.
: 3. repeat step 1 and 2 to finish the second half.
: 4. does the merge sort on the two sorted halves.
: 5. at certain point, consolidates the processed original memory from two
: halves so we can write back the sorted results to the head of the original
: memory. Three pointers need to be kept during the process: the current
: position for sorted index; the current position for processed index from
|
h****n
发帖数: 1093 | 23 楼上有人给解法了
用2MB的堆就可以了
【在 g********d 的大作中提到】
: integers are provided as network stream, so there's no storage
|
g********d
发帖数: 203 | 24 不行，因为input是一个stream，没办法先找大的一半。
其实我觉得这个问题可能是怎么把这么1 million integers compress到2MB里
【在 h****n 的大作中提到】
: 楼上有人给解法了
: 用2MB的堆就可以了
|
h****n
发帖数: 1093 | 25 人家题目也没说是个stream吧
这么多限制条件。。。面试遇到这么多限制条件估计要蛋疼了
额
【在 g********d 的大作中提到】
: 不行，因为input是一个stream，没办法先找大的一半。
: 其实我觉得这个问题可能是怎么把这么1 million integers compress到2MB里
|
c*****e
发帖数: 3226 | 26 bitsort 可以么？
【在 g********d 的大作中提到】
: How to sort 1 million integers with 2MB of memory and with no external
: storage?
: 这个怎么做啊？
|
g********d
发帖数: 203 | 27 这个的确是interviewer给的条件。是很蛋疼，估计挂了。
【在 h****n 的大作中提到】
: 人家题目也没说是个stream吧
: 这么多限制条件。。。面试遇到这么多限制条件估计要蛋疼了
: 额
|
g********d
发帖数: 203 | 28 怎么搞？
【在 c*****e 的大作中提到】
: bitsort 可以么？
|
f*****e
发帖数: 2992 | 29 先用中位数和四分数（三个数过两遍就可以找出来）或者干脆是随机选的elements，
inplace把数组平分成4个子数组，每个子数组有2^20/2^2=2^18个数,然后对每个子数
组做radix sort。radix sort需要与原数组相同大小的额外空间，还需要buckets用来
记录落入bucket里的数的数目。如果用16位counting，要记录2^16个buckets，每个
bucket 4个字节用来记录落在这个bucket的数的数目。算一算正好够了，因为2MB内存
可以存放
buckets 2^16 x 4 =256KB，加额外空间 2^18 x 4 = 2^20 = 1MB。
【在 g********d 的大作中提到】
: How to sort 1 million integers with 2MB of memory and with no external
: storage?
: 这个怎么做啊？
|
p****n
发帖数: 51 | 30 我刚才也想到压缩了，只是觉得很蛋疼。。
一个整数是32bit，比如
FF FF FF FF
现在我用44bit表示16个整数
我先用FF FF FF F表示整数的前28bit，然后用16个bit表示0到F
这样 2MB可以表示 (2MB / 44bit) * 16 大约 6M 个整数
剩下的in place sort就可以了
【在 g********d 的大作中提到】
: 不行，因为input是一个stream，没办法先找大的一半。
: 其实我觉得这个问题可能是怎么把这么1 million integers compress到2MB里
|
|
|
p****n
发帖数: 51 | 31 2MB不够装下所有的整数
【在 c*****e 的大作中提到】
: bitsort 可以么？
|
i*********7
发帖数: 348 | 32 我一直在想，所谓stream，是打算怎么表示？
难道是类似cin或者istream，然后读100万次？ |
p****n
发帖数: 51 | 33 对，只读一遍的
【在 i*********7 的大作中提到】
: 我一直在想，所谓stream，是打算怎么表示？
: 难道是类似cin或者istream，然后读100万次？
|
i***h
发帖数: 12655 | 34 可以重复读入多次的话,
用bitmap不是更有效率?
不过这样好象有点cheating,
算external storage么?
【在 p****n 的大作中提到】
: 不是，我不分割输入，只是需要读两边输入
: 假设输入是
: 3 7 4 8 5 9 1 10 2 11 3 12
: 现在我只有存六个整数的空间
: 我读第一边，应该可以用最大堆找到1 2 3 4 5 6并输出吧
: 然后我再读一边，用最小堆找到 7 8 9 10 11 12并输出
|
i*********7
发帖数: 348 | 35 而且我还有疑问，你只有两MB内存，是怎么也放不下1 million integers的。。除非你
的integer 是 旧版本的 16bit。。结果怎么存？ |
h****n
发帖数: 1093 | 36 结果直接写入storage了，不是存在memory里
【在 i*********7 的大作中提到】
: 而且我还有疑问，你只有两MB内存，是怎么也放不下1 million integers的。。除非你
: 的integer 是 旧版本的 16bit。。结果怎么存？
|
h****n
发帖数: 1093 | 37 你这方法还是改变了题目了吧，人家说好是32bit的整数
【在 p****n 的大作中提到】
: 我刚才也想到压缩了，只是觉得很蛋疼。。
: 一个整数是32bit，比如
: FF FF FF FF
: 现在我用44bit表示16个整数
: 我先用FF FF FF F表示整数的前28bit，然后用16个bit表示0到F
: 这样 2MB可以表示 (2MB / 44bit) * 16 大约 6M 个整数
: 剩下的in place sort就可以了
|
i*********7
发帖数: 348 | 38 我觉得限制条件的意思就是所有数字只能读一次，但是只能暂放一半的数字作为排序用
。是这个意思吗？ |
g********d
发帖数: 203 | 39 牛，这个应该可以。但是assumption是integers are unique对吧。如果不是，这个方
法就不行了吧。
【在 p****n 的大作中提到】
: 我刚才也想到压缩了，只是觉得很蛋疼。。
: 一个整数是32bit，比如
: FF FF FF FF
: 现在我用44bit表示16个整数
: 我先用FF FF FF F表示整数的前28bit，然后用16个bit表示0到F
: 这样 2MB可以表示 (2MB / 44bit) * 16 大约 6M 个整数
: 剩下的in place sort就可以了
|
g********d
发帖数: 203 | 40 结果直接打印出来也可以
【在 h****n 的大作中提到】
: 结果直接写入storage了，不是存在memory里
|
|
|
i*********7
发帖数: 348 | 41 这种做法明显要假设distribution吧。
理论上这种做法有可能表示最多六百万个数字。
但是最多只有600W/16大约40W个区间。
万一这1million的数字都分布在不同的区间里。明显就不够了吧。
【在 g********d 的大作中提到】
: 牛，这个应该可以。但是assumption是integers are unique对吧。如果不是，这个方
: 法就不行了吧。
|
b*******d
发帖数: 750 | 42
最终的区间不是由前28bit定下来了么？最后生成的区间不连续。一个新的integer找对
应区间不直接，并且确实uniqueness是个问题。
【在 i*********7 的大作中提到】
: 这种做法明显要假设distribution吧。
: 理论上这种做法有可能表示最多六百万个数字。
: 但是最多只有600W/16大约40W个区间。
: 万一这1million的数字都分布在不同的区间里。明显就不够了吧。
|
i*********7
发帖数: 348 | 43 已经假设没有负数了
那么0~INT_MAX里面总共可能产生的区间应该是（INT_MAX/16）个区间
那么完全有可能1million个数就分布在1million个distinct区间。
这个时候，需要的容量就是1million * 44 bit，也就是差不多5MB，比直接存数字更耗
费空间。所以我说这种压缩做法是可能假设了distribution比较密集在某些区间的情况。
当然，可能我理解错了意思。
【在 b*******d 的大作中提到】
:
: 最终的区间不是由前28bit定下来了么？最后生成的区间不连续。一个新的integer找对
: 应区间不直接，并且确实uniqueness是个问题。
|
i*********n
发帖数: 58 | 44 You only need to store the difference between sorted integers. In total
there are 2^32 = 4G integers and we are sorting 1M of them. So max
difference between two sorted integer should be around 4000 which needs 12
bits to store. Sorting 1M integer needs about 12 MBits. We have 2M RAM which
is 2 * 8 = 16 MBits. We only need to store the min integer and others just
the difference. Also, you do not need to store first and then sort. Just
sort them on the fly. The sort will be very expensive, but since there is no
constraint on that, we are OK. |
g****y
发帖数: 240 | 45 不对，max diff不是4000. 是4G - 1M。
which
just
no
【在 i*********n 的大作中提到】
: You only need to store the difference between sorted integers. In total
: there are 2^32 = 4G integers and we are sorting 1M of them. So max
: difference between two sorted integer should be around 4000 which needs 12
: bits to store. Sorting 1M integer needs about 12 MBits. We have 2M RAM which
: is 2 * 8 = 16 MBits. We only need to store the min integer and others just
: the difference. Also, you do not need to store first and then sort. Just
: sort them on the fly. The sort will be very expensive, but since there is no
: constraint on that, we are OK.
|
