b*********n
发帖数: 1258 | 1 you have a billion google searches a day, design a method which lets you
pull out the top 100 unique ones at the end of the day.
jobhunting版很多人都给的cs的方法，我有一个统计的办法
假设总共有n个记录，我可以用reservoir sampling随机取出k(k>100)个,
那么n个记录里面的top 100就应该是k个记录里面的top 100
然后在k里面找top 100就是答案了
这样的话就可以把问题的sample space减小了
不知道这种做法是否可行，2种情况下的variance分别是多少
还有，是否必须遍历n个记录来选择k个记录？
大家谈谈看法吧 |
D******n
发帖数: 2836 | 2 什么两种情况？你只说了一种。
你说的那种当然可以，不过你给出的就是estimate，不是绝对准确的。
类似sample mean 来估计population mean。
variance当然可以算，不过不知道你说的是哪个量的variance。
【在 b*********n 的大作中提到】
: you have a billion google searches a day, design a method which lets you
: pull out the top 100 unique ones at the end of the day.
: jobhunting版很多人都给的cs的方法，我有一个统计的办法
: 假设总共有n个记录，我可以用reservoir sampling随机取出k(k>100)个,
: 那么n个记录里面的top 100就应该是k个记录里面的top 100
: 然后在k里面找top 100就是答案了
: 这样的话就可以把问题的sample space减小了
: 不知道这种做法是否可行，2种情况下的variance分别是多少
: 还有，是否必须遍历n个记录来选择k个记录？
: 大家谈谈看法吧
|
b*********n
发帖数: 1258 | 3 第一种就是用cs的方法真实的算出population top 100
第二种就是用sample来estimate出population top 100
我想算的variance就是用sample top 100来估计population top 100的error的var
iance是多少
就是estimation和真实值之间的variance是多少
谢谢
【在 D******n 的大作中提到】
: 什么两种情况？你只说了一种。
: 你说的那种当然可以，不过你给出的就是estimate，不是绝对准确的。
: 类似sample mean 来估计population mean。
: variance当然可以算，不过不知道你说的是哪个量的variance。
|
D******n
发帖数: 2836 | 4 first, define error
second, since the first method is the exact method(it is always correct), wh
y would u expect to see variance?
【在 b*********n 的大作中提到】
: 第一种就是用cs的方法真实的算出population top 100
: 第二种就是用sample来estimate出population top 100
: 我想算的variance就是用sample top 100来估计population top 100的error的var
: iance是多少
: 就是estimation和真实值之间的variance是多少
: 谢谢
|
