j**********3
发帖数: 3211 | 1 这个题150题里有，用2个heap做，
可是如果memory不够大，放不下数据，要怎么做？ |
r*******k
发帖数: 1423 | 2 heap就是2个数组
如果连这个都装不下，又怎么算中值？
至少得遍历一遍吧？
除非知道数的范围，碰到最大最小值可以删一对
否则没办法减少空间要求吧
要不用bucket统计一下，能猜出中值在哪个bucket里
然后等于是求那个bucket的第k个值
要遍历数组2遍
【在 j**********3 的大作中提到】
: 这个题150题里有，用2个heap做，
: 可是如果memory不够大，放不下数据，要怎么做？
|
j**********3
发帖数: 3211 | 3 哎呀妈呀终于有人看了，谢谢！
我看一下回复哈。。。
【在 r*******k 的大作中提到】
: heap就是2个数组
: 如果连这个都装不下，又怎么算中值？
: 至少得遍历一遍吧？
: 除非知道数的范围，碰到最大最小值可以删一对
: 否则没办法减少空间要求吧
: 要不用bucket统计一下，能猜出中值在哪个bucket里
: 然后等于是求那个bucket的第k个值
: 要遍历数组2遍
|
j**********3
发帖数: 3211 | 4 就是装不下这2个数组，
举例：4GB的data， memory 100mb
我想到的方法，和你说的一样，bucket的，但我总觉得有更好的方法。
我自己遇到过这个题，朋友被面过。前2天面镜貌似也出现过。不知道有什么好的方法
。。。
【在 r*******k 的大作中提到】
: heap就是2个数组
: 如果连这个都装不下，又怎么算中值？
: 至少得遍历一遍吧？
: 除非知道数的范围，碰到最大最小值可以删一对
: 否则没办法减少空间要求吧
: 要不用bucket统计一下，能猜出中值在哪个bucket里
: 然后等于是求那个bucket的第k个值
: 要遍历数组2遍
|
s******c
发帖数: 99 | 5 Heap不是把所有的数据都放下，只维持内存能放下大小的heap,每次从文件里读数据进
内存，不断做heapify |
j**********3
发帖数: 3211 | 6 可是一个heap，只能方下内存大小的数据，那咋找中值阿？每次进来一个新的data，要
把以前读过的data再读一遍？
【在 s******c 的大作中提到】
: Heap不是把所有的数据都放下，只维持内存能放下大小的heap,每次从文件里读数据进
: 内存，不断做heapify
|
w****k
发帖数: 755 | 7 一次取一片，求取中值。
然后这些中值再取中值。
可以肯定，如果一个片段的中值Ki小于这个中值K，那片段中小于Ki的必不包含中值，
可以扔掉。
反之Kj大于K的话，大于Kj的片段也可以扔掉，
你只要保证扔掉的大头和小头数量一样，那中值就不会变。
就这么做下去就行。 |
j**********3
发帖数: 3211 | 8 嗯。。。让偶考虑一下。。。
这个方法比bucket好？
【在 w****k 的大作中提到】
: 一次取一片，求取中值。
: 然后这些中值再取中值。
: 可以肯定，如果一个片段的中值Ki小于这个中值K，那片段中小于Ki的必不包含中值，
: 可以扔掉。
: 反之Kj大于K的话，大于Kj的片段也可以扔掉，
: 你只要保证扔掉的大头和小头数量一样，那中值就不会变。
: 就这么做下去就行。
|
S******1
发帖数: 216 | 9
histogram, 你不是会做吗
【在 j**********3 的大作中提到】
: 嗯。。。让偶考虑一下。。。
: 这个方法比bucket好？
|
j**********3
发帖数: 3211 | 10 会做咋了？
【在 S******1 的大作中提到】
:
: histogram, 你不是会做吗
|
|
|
j**********3
发帖数: 3211 | 11 我需要更好的办法。。。
【在 S******1 的大作中提到】
:
: histogram, 你不是会做吗
|
c*******y
发帖数: 98 | 12 bucket神马的感觉靠谱，不同bucket存到不同机器上去，估计最好用平衡二叉树做一个
可以O lgn 插入，Olgn 查找第k个元素的结构。节点结构至少要包括node左边几个元素
，右边几个元素。每次插入还有平衡都得把这个也考虑一下。
【在 r*******k 的大作中提到】
: heap就是2个数组
: 如果连这个都装不下，又怎么算中值？
: 至少得遍历一遍吧？
: 除非知道数的范围，碰到最大最小值可以删一对
: 否则没办法减少空间要求吧
: 要不用bucket统计一下，能猜出中值在哪个bucket里
: 然后等于是求那个bucket的第k个值
: 要遍历数组2遍
|
T*****u
发帖数: 7103 | 13 借个只能估计了。以前看过一篇paper，stream超大数据的情况下。我给你找找。 |
T*****u
发帖数: 7103 | 14 先给你来2gb大的，再给你来2gb小的。
【在 w****k 的大作中提到】
: 一次取一片，求取中值。
: 然后这些中值再取中值。
: 可以肯定，如果一个片段的中值Ki小于这个中值K，那片段中小于Ki的必不包含中值，
: 可以扔掉。
: 反之Kj大于K的话，大于Kj的片段也可以扔掉，
: 你只要保证扔掉的大头和小头数量一样，那中值就不会变。
: 就这么做下去就行。
|
d******5
发帖数: 42 | 15 我也遇到过这个问题，用双heap和bucket都做了，然后面试官说还有更好的办法。。
后来想到如果有好多个machine也许可以这么做，把这堆数字分堆放到machine里，对每
个machine的数字进行排序，同时计算出有多少个数字，假设为N。然后做一个heap，每
次都往里面push和pop数字，做N/2次，就能算出来的。
实在不行，就mapreduce吧 |
y****n
发帖数: 743 | 16 使用BST作，可以容纳更大的数据量。
BST的每个结点包含value和value出现的次数。
代码再循环过程中保存当前中数，比当前值大的个数，和比当前值小的个数。
如果当前值已经不是中数，使用BST的（前值结点）和(后值结点)的算法移动中数。 |
p*********e
发帖数: 303 | |
j**********3
发帖数: 3211 | 18 我敢脚，可能是比较简单的方法，偶们都忽视了？
【在 T*****u 的大作中提到】
: 借个只能估计了。以前看过一篇paper，stream超大数据的情况下。我给你找找。
|
T*****u
发帖数: 7103 | 19 算上统计背景的话不太简单。它那个方法基本不用空间。
【在 j**********3 的大作中提到】
: 我敢脚，可能是比较简单的方法，偶们都忽视了？
|
c*******y
发帖数: 98 | 20 大哥review一下我的思路？
【在 j**********3 的大作中提到】
: 我敢脚，可能是比较简单的方法，偶们都忽视了？
|
|
|
j**********3
发帖数: 3211 | 21 哪个方法？就是你提paper里的？
【在 T*****u 的大作中提到】
: 算上统计背景的话不太简单。它那个方法基本不用空间。
|
j**********3
发帖数: 3211 | 22 好的好的，有问题没看懂的话我问你哈！
【在 c*******y 的大作中提到】
: 大哥review一下我的思路？
|
f******s
发帖数: 659 | 23 one approach to squeeze the space is to use a bit array or bit set: instead
of saving each number as an integer in the memory, use bit 1 to represent
this number's existence, and use bit 0 to represent a number's non-existence
.
For instance, to represent a set of numbers in range [0.. 10] : { 2, 4, 5, 7
, 8}, you can use a bit vector: 00101101100.
If the range of the data is all the integer (32 bits), then the space needed
to store this big bit vector will be 2^32 bits or 128 MB, which fits the
required 200MB memory.
Then find the median by counting 1's from both ends of the vector, until you
reach the center 1, or pair of 1's, and from its/their index in the vector,
you can find the number/numbers represented and get the median. |
s******t
发帖数: 229 | 24
instead
existence
7
needed
you
不对吧，您这是默认没有重复数字啊？要是有100万个1，一个100000，median是啥啊。
数字大小跟median无关，主要是每个不同数字的个数，得想法把这个记下来
【在 f******s 的大作中提到】
: one approach to squeeze the space is to use a bit array or bit set: instead
: of saving each number as an integer in the memory, use bit 1 to represent
: this number's existence, and use bit 0 to represent a number's non-existence
: .
: For instance, to represent a set of numbers in range [0.. 10] : { 2, 4, 5, 7
: , 8}, you can use a bit vector: 00101101100.
: If the range of the data is all the integer (32 bits), then the space needed
: to store this big bit vector will be 2^32 bits or 128 MB, which fits the
: required 200MB memory.
: Then find the median by counting 1's from both ends of the vector, until you
|
w*******y
发帖数: 64 | |
m****v
发帖数: 780 | 26 用hadoop，map到小的interval，count, 找出哪个interval
再来一边，重复，直到最后足够小，单机扫
【在 j**********3 的大作中提到】
: 这个题150题里有，用2个heap做，
: 可是如果memory不够大，放不下数据，要怎么做？
|
m******e
发帖数: 82 | |
c********r
发帖数: 107 | |
m**p
发帖数: 189 | 29 这题还是很简单的。你们确定是学CS的？
hint:
没有要你做stream, 不用 heap.
一台机器足够。 |
b*******d
发帖数: 750 | 30 不会吧 这个题居然这么多讨论啦？
【在 m**p 的大作中提到】
: 这题还是很简单的。你们确定是学CS的？
: hint:
: 没有要你做stream, 不用 heap.
: 一台机器足够。
|
|
|
U***A
发帖数: 849 | 31 我觉得这个思路靠谱。
【在 y****n 的大作中提到】
: 使用BST作，可以容纳更大的数据量。
: BST的每个结点包含value和value出现的次数。
: 代码再循环过程中保存当前中数，比当前值大的个数，和比当前值小的个数。
: 如果当前值已经不是中数，使用BST的（前值结点）和(后值结点)的算法移动中数。
|
f******s
发帖数: 659 | 32 yeah, you are right. I assumed each number's unique, which is wrong.
【在 s******t 的大作中提到】
:
: instead
: existence
: 7
: needed
: you
: 不对吧，您这是默认没有重复数字啊？要是有100万个1，一个100000，median是啥啊。
: 数字大小跟median无关，主要是每个不同数字的个数，得想法把这个记下来
|
l******e
发帖数: 54 | 33 多个 machine 就是不一样的做法了 如果还用 heap 一个一个的读就太慢了 |
