0

我想从0tosize - 1统一生成一个索引，但与给定 set 中的任何索引不同excluded。

size大约是 100。通常有 1、2 或 3 个exluded指数。中的索引excluded是唯一的且未排序。

理想情况下，标题将带有多个参数，可能是这样的：

int getRandomIndex(Random rand, int size, int... i)

或者，如果这个...多参数很慢（是吗？）我们可以传递简单的int[] excluded数组或其他东西。

如何快速完成？getRandomIndex()被称为数百万次。

4

5 回答 5

4 
static int getRandomIndex(Random rand, int size, Integer... excludes) {
    List<Integer> excludeList = Arrays.asList(excludes);
    int number;
    do {
        number = rand.nextInt(size);
    } while (excludeList.contains(number));

    return number;
}
于 2013-11-02T16:15:05.587 回答
3

您可以分配可能值 0..size-1 的数组，删除所有已知索引并从其余元素中选择随机元素。

如果索引数组已排序并且所有值都是唯一的，则无需中间值数组即可：

int getRandomIndex(Random rand, int size, int... ii)
{
  int result = rand.nextInt(size - ii.length);
  for(int i : ii) {
    if(result >= i) {
      ++result; 
    }
  }

  return result;
}

编辑：我在 if 条件中发现错误，已更正。

编辑： 

int getRandomIndex(Random rand, int size, int i) {
  int result = rand.nextInt(size - 1);
  if(result >= i) {
    result++;
  }
}

int getRandomIndex(Random rand, int size, int i, int j) {
  int result = rand.nextInt(size - 2);
  if(i > j) {
    int tmp = j;
    j = i;
    i = tmp;
  }
  if(result >= i) {
    result++;
  }
  if(result >= j) {
    result++;
  }
  return result;
}

和 (i,j,k) 的类似函数。

只调用rand.next一次的函数可能比任何要求随机数多次的函数更快。

于 2013-11-02T16:14:05.203 回答
1

我会做的有点不同。要选择小于 size 但不是 i 或 j 的随机数，您可以选择介于 0 和 size-3 之间的随机数。如果该数字为 i，则返回 size-2，如果该数字为 j，则返回 size-1。否则返回原始随机数。

存在 i 或 j 大小在 2 以内的极端情况，但我将其留给感兴趣的读者。事实上，我认为它只是工作正常。

这可以概括为选择一个小于大小且不在整数数组中的数字。选择一个小于 size 的数字 - 数组长度 - 1。

于 2013-11-02T16:21:59.793 回答
1

您可以使用Set来回快速查找

int getRandomIndex(Random rand, int size, Integer... i) {
    return getRandomIndex(rand, size, new HashSet<Integer>(Arrays.asList(i)));
}


int getRandomIndex(Random rand, int size, Set<Integer> x) {
    int result;
    do {
        result = (int) (rand.nextDouble() * size);
    } while (x.contains(result));
    return result;
}

如果所有索引的集合都是预定义的，那么您Set x final static每次调用该方法时都可以使用和备用构建它。

EIDT

好吧，如果性能是一个问题，那么我会说您的第一种方法while(r == i || r == j || r == k)既不坏也不丑陋，只需对您的方法进行三个重载并调用您需要的适当的方法，该调用看起来与使用 val-len-大批。

你不能比(r == i || r == j || r == k)

int getRandomIndex(Random rand, int size, int i)
int getRandomIndex(Random rand, int size, int i, int j)
int getRandomIndex(Random rand, int size, int i, int j, int k)
于 2013-11-02T16:25:09.767 回答
0

假设许多连续调用使用相同的大小和排除值......

  • 首先，初始化所有允许索引的数组
  • getRandomIndex调用时，只需选择此数组的随机元素

代码：

int[] indices;

void init(int size, Integer... excluded)
{
   indices = new int[size-excluded.length];
   int pos = 0;
   Set<Integer> excludedSet = new HashSet<Integer>(Arrays.asList(excluded));
   for (int i = 0; i < size; i++)
   {
      if (!excludedSet.contains(i))
      {
         indices[pos++] = i;
      }
   }
}

int getRandomIndex(Random random)
{
   return indices[random.nextInt(data.length)];
}

示例用法：

init(100, 50, 23, 10);
Random random = new Random();
for (int i = 0; i < 200; i++)
{
   System.out.println(getRandomIndex(random));
}
于 2013-11-02T17:10:14.047 回答