>我有一个在接受文件的服务器上运行的企业应用程序。用户每天提交数以万计的文件。客户希望每天自动选择其中的 50 个文件进行审核。
要求是：
- 文件必须在进入时选择(我们不能等待所有文件都进来，然后在一天结束时选择 50 (
- 选择的文件必须满足其他一些标准，他们还没有告诉我，但我确信仍然会有成千上万的文件符合这些标准
- 系统不得是"可游戏的"。也就是说 - 他们不希望提交文件的用户意识到，如果他们等到下午或其他时间，他们的文件永远不会被审核。这意味着我们不能只选择前 50 个，所选文件必须在一天中随机分布。
- 我们必须有 50 个文件。或者他们说。但我很确定，如果碰巧有一天中午之后没有用户提交符合标准的文件，而我们只有 25 个文件，他们会同意的。因此，我可以假设我感兴趣的文件类型在一天中以合理的规则频率提交。
然后我想，我需要一些函数来计算选择文件的概率，该函数使用当前选择的文件数量和一天中的时间作为输入。
我创建了一个测试工具。请原谅狡猾的代码。在这种情况下，"pushTask"线程通过将文件添加到堆栈来模拟进入的文件。此测试中的"文件"只是末尾带有随机数的字符串。
"pullTask"线程模拟从堆栈中提取的文件。它询问 requirementsFunction(( "文件"是否满足所需的额外要求(在这个测试中，它只是 - 它是否以零结尾(，并询问 probabilityFunction(( 是否应该选择该文件。如果选择了某个文件，则会将其打印到 System.out。
真的，我需要一些关于在 probabilityFunction(( 中放入什么的帮助，因为目前那里的东西是垃圾(我已经把它留了下来，所以你可以看到我尝试过的内容(。或者，如果有人知道使用项目/时间的数学概率函数，那也很棒。
package com.playground;
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Random;
public class ProbabilisticSelection {
private static int TOTAL_FILES = 1000;
private static int AUDIT_QUANTITY = 10;
private static int TIME_IN_SECONDS_FOR_ALL_FILES = 10;
private Random random = new Random();
private Deque<String> stack = new ArrayDeque<String>();
private boolean finished;
public static void main(String[] args) throws InterruptedException {
new ProbabilisticSelection().test();
}
private void test() throws InterruptedException {
Instant begin = Instant.now();
Runnable pushTask = () -> {
while (!finished) {
int next = random.nextInt(TOTAL_FILES);
String item = "File: " + next;
stack.push(item);
if (Duration.between(begin, Instant.now()).getSeconds() >= TIME_IN_SECONDS_FOR_ALL_FILES) {
finished = true;
}
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
Runnable pullTask = () -> {
int itemNumber = 1;
while (itemNumber <= AUDIT_QUANTITY && !finished) {
String poll = stack.poll();
if (requirementsFunction(poll) &&
probabilityFunction(itemNumber, Duration.between(begin, Instant.now()))) {
System.out.println(itemNumber++ + ": "+ poll);
}
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
finished = true;
Duration delta = Duration.between(begin, Instant.now());
System.out.println();
System.out.println("Retrieved files: " + (itemNumber - 1) + ", should be, " + AUDIT_QUANTITY);
System.out.println("Time taken: " + delta.getSeconds() + ", should be, " + TIME_IN_SECONDS_FOR_ALL_FILES);
};
new Thread(pullTask).start();
new Thread(pushTask).start();
}
private boolean requirementsFunction(String item) {
return item != null && item.endsWith("0");
}
private boolean probabilityFunction(int itemNumber, Duration delta) {
double limit = ((double)(AUDIT_QUANTITY-itemNumber)/(double)AUDIT_QUANTITY + 1); // probability goes down as number of items goes up
double tension = (double)TIME_IN_SECONDS_FOR_ALL_FILES/((double)delta.getSeconds() + 1); // probablity goes up as time nears the end
if (tension == 1) {
return true;
}
double prob = limit * tension * 100;
int rand = random.nextInt(1000);
return prob > rand;
}
}
算法被称为Reservoir_sampling，它保证从一些大型和未知N中公平地抽取k项目。这是Java代码