t**********g
发帖数: 3388 | 1 streaming data coming in, 要求sample data，按照1/K的概率sample.应该怎么做 |
u*****o
发帖数: 1224 | |
a*****u
发帖数: 1712 | 3 wiki了一下，这个方法不错啊
【在 u*****o 的大作中提到】
: Reservior sampling?
|
c********p
发帖数: 1969 | |
z****e
发帖数: 54598 | 5 每次看到这个我就想起了河马
总是想过去调戏丫的
【在 u*****o 的大作中提到】
: Reservior sampling?
|
y*****h
发帖数: 97 | 6
Reservior sampling是取k个sample， 这个题是以1/k去sample，也就是说总共有n个数
的话最后会有n/k个sample。
【在 u*****o 的大作中提到】
: Reservior sampling?
|
k*******s
发帖数: 134 | |
y*****h
发帖数: 97 | 8
你引用的这个是估计海量数据中的top k frequent items
lz指的题目是在海量数据中以1/k的概率sample item
【在 k*******s 的大作中提到】
: 没太看明白什么意思，但是是下面这个意思吗
: http://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
|
v***n
发帖数: 562 | |
t******i
发帖数: 483 | |
|
|
b***r
发帖数: 4186 | 11 mark
【在 t**********g 的大作中提到】
: streaming data coming in, 要求sample data，按照1/K的概率sample.应该怎么做
|
a******e
发帖数: 710 | 12 那顺序读一遍，每个元素以1/k的概率记下来不就可以了么？
【在 y*****h 的大作中提到】
:
: 你引用的这个是估计海量数据中的top k frequent items
: lz指的题目是在海量数据中以1/k的概率sample item
|
t**********g
发帖数: 3388 | 13 streaming data coming in, 要求sample data，按照1/K的概率sample.应该怎么做 |
u*****o
发帖数: 1224 | |
a*****u
发帖数: 1712 | 15 wiki了一下，这个方法不错啊
【在 u*****o 的大作中提到】
: Reservior sampling?
|
c********p
发帖数: 1969 | |
z****e
发帖数: 54598 | 17 每次看到这个我就想起了河马
总是想过去调戏丫的
【在 u*****o 的大作中提到】
: Reservior sampling?
|
y*****h
发帖数: 97 | 18
Reservior sampling是取k个sample， 这个题是以1/k去sample，也就是说总共有n个数
的话最后会有n/k个sample。
【在 u*****o 的大作中提到】
: Reservior sampling?
|
k*******s
发帖数: 134 | |
y*****h
发帖数: 97 | 20
你引用的这个是估计海量数据中的top k frequent items
lz指的题目是在海量数据中以1/k的概率sample item
【在 k*******s 的大作中提到】
: 没太看明白什么意思，但是是下面这个意思吗
: http://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
|
|
|
v***n
发帖数: 562 | |
t******i
发帖数: 483 | |
b***r
发帖数: 4186 | 23 mark
【在 t**********g 的大作中提到】
: streaming data coming in, 要求sample data，按照1/K的概率sample.应该怎么做
|
a******e
发帖数: 710 | 24 那顺序读一遍，每个元素以1/k的概率记下来不就可以了么？
【在 y*****h 的大作中提到】
:
: 你引用的这个是估计海量数据中的top k frequent items
: lz指的题目是在海量数据中以1/k的概率sample item
|
p******d
发帖数: 63 | 25 data stream怎么知道n的？
【在 y*****h 的大作中提到】
:
: 你引用的这个是估计海量数据中的top k frequent items
: lz指的题目是在海量数据中以1/k的概率sample item
|
l*****a
发帖数: 14598 | 26 读一个counter++
【在 p******d 的大作中提到】
: data stream怎么知道n的？
|
g*****g
发帖数: 212 | 27 说的没错，觉得的是问的有问题。
【在 a******e 的大作中提到】
: 那顺序读一遍，每个元素以1/k的概率记下来不就可以了么？
|
p******d
发帖数: 63 | 28 如果用reservoir sampling的话需要预先知道sample的数量，需要扫两遍data stream
：第一遍算总数n；第二遍用reservoir sampling取n/k个sample。但问题是data
stream一般只能扫一遍吧？
直接以概率1/k决定是否保留当前sample听着更合理，但好像又太简单了。
【在 l*****a 的大作中提到】
: 读一个counter++
|
i**h
发帖数: 424 | 29 I think OP misstated the problem. 1/k sampling only requires 1/k randomized
probability per sample, which is too easy as an interview problem.
做过一个类似的问题，稍难一些：从stream data中提取k个sample，要求每个数据有相
同的机率被提取。难在stream长度未知。需要动态决定取舍。 |
x*****p
发帖数: 1707 | 30 Exactly
【在 a******e 的大作中提到】
: 那顺序读一遍，每个元素以1/k的概率记下来不就可以了么？
|
