ランダム・アルバイト・クイズを勝手に検証
僕のは間違いだね
昨日書いたアルゴリズムでプログラムを作って試したけど、やっぱり先に来た人のほうが有利になる傾向があった。こりゃ間違いだな。
「5人の枠に7人来た場合」を10000回繰り返したところ、
- 1人目 7228
- 2人目 7806
- 3人目 7321
- 4人目 7542
- 5人目 7544
- 6人目 6612
- 5人目 5940
期待値は714.3回なので、相当ばらついてる。（などと偉そうに言っているが、統計を知らないのでばらつき度合いを検証できない）
ただし、くじ周りの実装が正しいかどうか自信がないのであんまりアレかも。
普段「ランダムに選んで・・・」とかやらないしなあ。
こっちは正しそう
はてなブックマークがメンテナンス中なので、どこで見かけたか辿れなくなったんですが、「応募者が来たらランダムな数値を割り当てる。採用枠以上になったら、一人来るたびにその数値を比較して、一番低い人にお引取りいただく」というアルゴリズムにすると、上と同じ「5人の枠に7人来た場合」×10000回でこんな感じ。
- 1人目 7255
- 2人目 7136
- 3人目 7070
- 4人目 7093
- 5人目 7153
- 6人目 7121
- 7人目 7165
正しそうですね。（などと偉そう（ry）
（追記）お見かけしたのはこちらでした。
http://d.hatena.ne.jp/sawat/20051017#1129569459
いずれにしろ、結城さんの解説待ちですな。
検証に使ったプログラム
Eclipse3.1を入れてないパソコンでやったので（言い訳）J2SE1.4です。
採用アルゴリズム共通のインターフェイス
package orz.bakock.randompart;import java.util.List;
public interface RandomPartTimeHiring {
// 募集人数を決める
// 最初に呼ばなきゃいけないのがアレだけどまあいいや
void setHeadCountToBeHired(int i);// 応募者が来たよ
void entry(Applicant applicant);// 今待機してる人たち
List listWaitingApplicants();
}
応募者
package orz.bakock.randompart;public class Applicant {
private String name;
public Applicant(String name) {
this.name = name;
}public String toString() {
return "Applicant [" + name + "]";
}
public boolean equals(Object o) {
if (o != null && o.getClass().equals(this.getClass())) {
return this.name.equals(((Applicant) o).name);
} else {
return false;
}
}public int hashCode() {
return name.hashCode();
}public String getName() {
return name;
}
}
僕のアルゴリズム
package orz.bakock.randompart;import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;import orz.bakock.randompart.CalcAverageOdds.Kuji.KujiItem;
public class CalcAverageOdds implements RandomPartTimeHiring {
private int headCountToBeHired;
private List waitings;
private int entried;public CalcAverageOdds() {
super();
waitings = new LinkedList();
}public void entry(Applicant applicant) {
entried++;
//エントリー時にスコア設定
if (waitings.size() < headCountToBeHired) {
waitings.add(applicant);
} else {
// 新しく来た人を交えて抽選
waitings = drawing(applicant);
}
}private List drawing (Applicant newComer) {
List l = new LinkedList();
// すでに待機している人がひくくじ
Kuji kujiForWaiting = new Kuji(entried, entried - 1);
for (Iterator it = waitings.iterator(); it.hasNext();) {
Applicant waiting = (Applicant) it.next();
KujiItem itemForWaiting = kujiForWaiting.draw();
if (itemForWaiting.hit) l.add(waiting);
}// 新しく来た人がひくくじ
Kuji kujiForNewComer = new Kuji(entried, headCountToBeHired);
KujiItem itemForNewComer = kujiForNewComer.draw();
if (itemForNewComer.hit) l.add(newComer);
// 抽選した結果、選ばれた人数が採用予定人数と同じならOK
if (l.size() == headCountToBeHired) {
return l;
} else {
// ダメならやり直し
return drawing(newComer);
}
}public List listWaitingApplicants() {
return this.waitings;
}public void setHeadCountToBeHired(int headCountToBeHired) {
this.headCountToBeHired = headCountToBeHired;
}// くじ
class Kuji {
List items = new LinkedList();
int total;
// total件中 hit件があたり
Kuji(int total, int hit) {
this.total = total;
for (int i = 0; i < total; i++) {
KujiItem item = new KujiItem();
items.add(item);
}
Collections.sort(items);// ランダムな値でソートして当たりマーク付け
for (int i = 0; i < hit; i++) {
KujiItem item = (KujiItem) items.get(i);
item.hit = true;
}
}// くじが重複して引けちゃうけど、OKだと思う
KujiItem draw() {
double random = new Random().nextDouble();
int i = Math.abs((int) (random * (items.size())));
return (KujiItem) items.get(i);
}// くじの札です
class KujiItem implements Comparable{
double random = new Random().nextDouble();
boolean hit = false;
public int compareTo(Object o) {
double target = ((KujiItem) o).random;
if (random > target) return 1;
return -1;
}
}
}
}
来た人に点数をつけるアルゴリズム
package orz.bakock.randompart;import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;public class PreRandomScore implements RandomPartTimeHiring {
private int headCountToBeHired;
private List waitings;
private Random random;public PreRandomScore() {
super();
// スコアをつけるための乱数生成
random = new Random();
waitings = new LinkedList();
}public void entry(Applicant applicant) {
//エントリー時にスコア設定
ApplicantWithScore aws = new ApplicantWithScore(applicant, random.nextDouble());
if (waitings.size() < headCountToBeHired) {
waitings.add(aws);
} else {
// 今待機しているうち最小のスコアをもつ応募者より
// 新たにエントリーしてきた応募者のほうがスコアが高ければ
// 入れ替える
ApplicantWithScore lowest = this.getLowestInWaiting();
if (aws.score > lowest.score) {
waitings.remove(lowest);
waitings.add(aws);
}
}
}// 持っているスコアが一番低い応募者のデータを返す
private ApplicantWithScore getLowestInWaiting() {
ApplicantWithScore lowest = null;
for (Iterator it = waitings.iterator(); it.hasNext(); ) {
ApplicantWithScore aws = (ApplicantWithScore) it.next();
if (lowest == null) {
lowest = aws;
} else {
if (aws.score < lowest.score) lowest = aws;
}
}
return lowest;
}//現在待機している応募者
public List listWaitingApplicants() {
List ret = new ArrayList();
for (Iterator it = waitings.iterator(); it.hasNext(); ) {
ret.add(((ApplicantWithScore) it.next()).applicant);
}
return ret;
}public void setHeadCountToBeHired(int headCountToBeHired) {
this.headCountToBeHired = headCountToBeHired;
}// 応募者にスコアを付加するための内部クラス
class ApplicantWithScore {
private Applicant applicant;
private double score;
public ApplicantWithScore(Applicant applicant, double score) {
this.applicant = applicant;
this.score = score;
}
}
}
テストロジック
・・・・・
Map map = new HashMap();
for (long l = 0L; l < 10000L; l++) {
RandomPartTimeHiring rth = new CalcAverageOdds(); // テスト対象のオブジェクト
rth.setHeadCountToBeHired(5); // 募集人数
rth.entry(new Applicant("A")); // 1人目
rth.entry(new Applicant("B")); // 2人目
rth.entry(new Applicant("C")); // 3人目
rth.entry(new Applicant("D")); // 4人目
rth.entry(new Applicant("E")); // 5人目
rth.entry(new Applicant("F")); // 6人目
rth.entry(new Applicant("G")); // 7人目
List hired = rth.listWaitingApplicants(); // ここまでに待機している人（つまり採用される人）
for (Iterator it = hired.iterator(); it.hasNext();) {
Applicant hiredApplicant = (Applicant) it.next();
Count count = (Count) map.get(hiredApplicant.getName());
// 見苦しいロジックですがご勘弁。人ごとに採用された回数をカウントしてます
if (count == null) {
map.put(hiredApplicant.getName(), new Count(
hiredApplicant));
} else {
count.count++;
}
}
}
Collection c = map.values();
for (Iterator it = c.iterator(); it.hasNext();) {
Count count = (Count) it.next();
System.out.println(count.applicant.toString() + ":" + count.count);
}・・・・・
// 採用された回数をカウントするための内部クラス
class Count implements Comparable {
private Applicant applicant;private long count;
public Count(Applicant applicant) {
this.applicant = applicant;
this.count = 0L;
}
public int compareTo(Object o) {
String name = applicant.getName();
return name.compareTo(((Count) o).applicant.getName());
}
}
