Result for 20000 run:time=19999 6309 11409 16817 3088 22377 0.10515001 0.19015001 0.28028333 0.05146667 0.37295 time=19999 5758 12154 19459 3182 19447 0.09596667 0.20256667 0.32431665 0.053033333 0.32411668 public class Test { static float border[]; public static int[] getSelectedIndexes(Object[] data, float[] weight, int numToFetch) throws Exception { if (data == null || data.length == 0) throw new Exception("Empty Data"); if (data.length < numToFetch) throw new Exception("Not so many records to fetch:" + numToFetch); if (border == null) { border = new float[data.length]; if (weight == null || weight.length == 0) { // every entry has equal weight float factor = 1.0f / data.length; for (int i = 0; i < data.length; ++i) { border[i] = (i + 1) * factor; } } else { for (int i = 0; i < weight.length; ++i) { border[i] = weight[i] + ( (i != 0) ? border[i - 1] : 0); } } } Random rand = new Random(System.currentTimeMillis()); int[] result = new int[numToFetch]; for (int i = 0; i < numToFetch; i++) { float v = rand.nextFloat()*border[border.length-1]; for (int j = 0; j < border.length; ++j) { if (v <= border[j]) { result[i] = j; break; } } } return result; }
public static void main(String[] args) { int LEN=5; Object[] data = new Object[LEN]; float[] weight = new float[]{0.1f,0.2f,0.3f,0.05f,0.35f}; int[] s = new int[LEN]; try{ for(int times = 0; times < 20000; ++times) { int[] result = getSelectedIndexes(data, weight, 3); for(int i = 0; i < result.length; ++i) s[result[i]]++; System.out.print("time=" + times + " "); for (int i = 0; i < s.length; ++i) System.out.print(s[i] + " "); System.out.println(); for (int i = 0; i < s.length; ++i) System.out.print( ( (float) s[i] / (times + 1) / 3) + " "); System.out.println();
} }catch(Exception e) {e.printStackTrace();} } }
to helpall: 能否解释以下你的程序呢?谢谢
我也贴一个, 和helpall的基本类似, 思路是: 每个元素对应一个权值, 那么算出累计权值, 然后根据随即数看落在哪个区间内。 去掉重复选择。 欢迎指正! import java.util.*; public class ZmhTest {
static int SCALE = 10; Object [] data = new Object[SCALE];
public int [] getRandomResults(float [] weights, int numOfResults) throws Exception {
int [] results = null; if (data == null || data.length == 0){
throw new Exception("Empty data!"); }
if (cumulate_weights == null || cumulate_weights.length == 0){
cumulate_weights = new float[SCALE];
for (int i = 0; i < weights.length; i ++) { cumulate_weights[i] = ((i == 0 ? weights[i]: weights[i] + cumulate_weights[i -1] )); } }
if (results == null) { results = new int [numOfResults];
// get all results. Random rand = new Random(System.currentTimeMillis()); for (int result_index = 0; result_index < numOfResults; result_index ++) { float fRandom = rand.nextFloat();
boolean bFind = false; // duplicated ?
for (int j = 0; j < cumulate_weights.length; j ++){
if (fRandom < cumulate_weights[j]){
for (int k = 0; k < result_index; k ++){ // remove duplicated. if (results[k] == j) { bFind = true; break; }
System.out.println("weight[" + i + "] is " + weights[i] + " "); }
int [] results = null;
try {
results = getRandomResults(weights, 4);
for (int i = 0; i < results.length; i ++) { System.out.println("results[" + i +"] is " + results[i] + " "); }
} catch (Exception ex){ ex.printStackTrace(); }
}
public static void main(String[] args){
ZmhTest zt = new ZmhTest();
zt.getInfo(); } }
Based on the weights, calculate how much positions one element occupies.For example, if we have: a 10%, b 10%, c 30%, d 50%Then we calculate positions as: abcccdddd.Assume these belong to range 0.0-1.0, then you know how to get the index.
机率是 m ,即权重,通过预先的设置,控制其出现的概率。
不过,回过头来想想,既然是随机,就无法再控制其概率,谁能帮偶想一个好一点的方法?
即从 n 条记录中选择 m 条记录,既达到随机效果,又能控制权重呢?
如M=7%,你选100次的话,前7次都选了中了M,也取出了,那就给他置个标志, 然后再选的时候 把sql语句置换成 加一个where条件 的新sql语句。
生成一个选择随机数 x,0<=x<=99,用于在 m 条记录中选择。
生成另一个随机数 y,0<=y<=n-m-1,用于在 n-m 条记录中选择。int count = ...;
int news[];
news = new int[count];//选出现的新闻序号int m=...;//假设 n 条新闻中要选 ... 条
float v[] = { 5, 10, 15, 20, 15, 10, 5, ...};//m条的权重,总和要小于100
float va[] = {5, 15, 30, 50, 65, 75, 80, ...};//
int index[] = {.....};//m条记录对应在 n 条记录中的位置(序号)int index_n[] = {......};//n-m条记录对应在 n 条记录中的位置(序号)bool b[];
b = new bool[n];//选中状态
for(int i=0;i<n;i++) {
b[i] = false;//初始均为未选中
}bool choose_m;
int i = 0;
while(i<count) {//一共要选 count 条
int x = random(100);//偶不知道这个函数怎么写
choose_m = false;
for(int j=0;j<m;j++) {
float xmin = j==0?0:va[j-1];
if( !b[index[j]] && xmin < x && x <= va[j] ) {//该条未被选中且概率落在该区间
news[i] = index[j];
choose_m = true;
b[index[j]] = true;//
j=m;
i++;
}
}
if( !choose_m ) {//未在 m 条中选中,则在n-m中选择
int y = radom(n-m);
if( !b[y] ) {
news[i] = y;
b[y] = true;
i++;
}
}
}大概就是这样子。未经测试。
如果 5<=x<10,选第 2 条,
如果 10<=x<15,选第 3 条,
……
如果 45<=x<50,选第 10 条,否则,生成随机数 y,(0<=y<70),选择后 90 条中的第 y 条。当然要考虑当前所选的是否是前面已经被选的,如果不是则开始选下一条(i++)。
0.10515001 0.19015001 0.28028333 0.05146667 0.37295 time=19999 5758 12154 19459 3182 19447
0.09596667 0.20256667 0.32431665 0.053033333 0.32411668 public class Test {
static float border[];
public static int[] getSelectedIndexes(Object[] data, float[] weight, int numToFetch) throws
Exception {
if (data == null || data.length == 0)
throw new Exception("Empty Data");
if (data.length < numToFetch)
throw new Exception("Not so many records to fetch:" + numToFetch);
if (border == null) {
border = new float[data.length];
if (weight == null || weight.length == 0) { // every entry has equal weight
float factor = 1.0f / data.length;
for (int i = 0; i < data.length; ++i) {
border[i] = (i + 1) * factor;
}
}
else {
for (int i = 0; i < weight.length; ++i) {
border[i] = weight[i] + ( (i != 0) ? border[i - 1] : 0);
}
}
} Random rand = new Random(System.currentTimeMillis()); int[] result = new int[numToFetch];
for (int i = 0; i < numToFetch; i++) {
float v = rand.nextFloat()*border[border.length-1];
for (int j = 0; j < border.length; ++j) {
if (v <= border[j]) {
result[i] = j;
break;
}
}
}
return result;
}
public static void main(String[] args) {
int LEN=5;
Object[] data = new Object[LEN];
float[] weight = new float[]{0.1f,0.2f,0.3f,0.05f,0.35f};
int[] s = new int[LEN];
try{
for(int times = 0; times < 20000; ++times) {
int[] result = getSelectedIndexes(data, weight, 3);
for(int i = 0; i < result.length; ++i)
s[result[i]]++;
System.out.print("time=" + times + " ");
for (int i = 0; i < s.length; ++i)
System.out.print(s[i] + " ");
System.out.println();
for (int i = 0; i < s.length; ++i)
System.out.print( ( (float) s[i] / (times + 1) / 3) + " ");
System.out.println();
}
}catch(Exception e) {e.printStackTrace();}
}
}
每个元素对应一个权值, 那么算出累计权值, 然后根据随即数看落在哪个区间内。
去掉重复选择。
欢迎指正!
import java.util.*;
public class ZmhTest {
static int SCALE = 10;
Object [] data = new Object[SCALE];
float [] weights = new float[]{0.1f, 0.1f, 0.2f, 0.05f, 0.05f, 0.1f, 0.2f, 0.04f, 0.06f, 0.1f};
static float [] cumulate_weights = null;
int [] results = new int[SCALE];
public int [] getRandomResults(float [] weights, int numOfResults)
throws Exception {
int [] results = null;
if (data == null || data.length == 0){
throw new Exception("Empty data!");
}
if (cumulate_weights == null || cumulate_weights.length == 0){
cumulate_weights = new float[SCALE];
for (int i = 0; i < weights.length; i ++)
{
cumulate_weights[i] = ((i == 0 ? weights[i]: weights[i] + cumulate_weights[i -1] ));
}
}
if (results == null)
{
results = new int [numOfResults];
// get all results.
Random rand = new Random(System.currentTimeMillis());
for (int result_index = 0;
result_index < numOfResults;
result_index ++)
{
float fRandom = rand.nextFloat();
boolean bFind = false; // duplicated ?
for (int j = 0; j < cumulate_weights.length; j ++){
if (fRandom < cumulate_weights[j]){
for (int k = 0; k < result_index; k ++){
// remove duplicated.
if (results[k] == j)
{
bFind = true;
break;
}
}
if (false == bFind)
{
results[result_index] = j;
}
break;
}
}
if (bFind)
{
result_index --;
}
}
}
return results;
} void getInfo()
{
System.out.println("weights\' length is " + weights.length + " ");
for (int i = 0; i < weights.length; i ++){
System.out.println("weight[" + i + "] is " + weights[i] + " ");
}
int [] results = null;
try {
results = getRandomResults(weights, 4);
for (int i = 0; i < results.length; i ++)
{
System.out.println("results[" + i +"] is " + results[i] + " ");
}
}
catch (Exception ex){
ex.printStackTrace();
}
}
public static void main(String[] args){
ZmhTest zt = new ZmhTest();
zt.getInfo();
}
}