浏览 1083 次
锁定老帖子 主题:Random sampling
该帖已经被评为隐藏帖
|
|
---|---|
作者 | 正文 |
发表时间:2010-11-10
public static List<Node> randonSampleIter(Iterator<Node> items, int sampleSize) Luckily, I got a similar question, which is kind of the special case for this one on a phone screen. That question is like, given a byte stream which you cannot randomly access, how can you return a random byte from it. Here is the idea, if the byte stream only has 1 byte, you return it. If it has 2 bytes, each of them has 50% to be returned, if it has 3 bytes, each of them share 33%. So we can generalize that for the kth byte, the chances that we return it is 1/k, so the problem get solved. Now back to this question, you may noticed that we can just replace 1 with sample size (m). We get the first m elements for our temp result, and then for every element we iterate through, it has m/k chances to be included in our result. this can be easily done by generate a random number from 0-k and then to see if the number falls within the range 0-m. public static List<Node> randonSampleIter(Iterator<Node> items, int sampleSize) { int count = 0; List<Node> result = new ArrayList<Node>(); while (count < sampleSize && items.hasNext()) { result.add(items.next()); count++; } if (count < sampleSize) { //the source given is less than sampleSize, we just return how many we get return result; } Random rand = new Random(); while (items.hasNext()) { Node element = items.next(); int r = rand.nextInt(count); if (r < sampleSize) { result.set(r, element); } count++; } return result; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |