php - 加权随机选择

Question

我有一套物品。我需要随机选择一个。问题是它们每个都有 1-10 的权重。权重为 2 表示该项目被选中的可能性是权重 1 的两倍。权重为 3 的可能性是其三倍。

我目前用每个项目填充一个数组。如果权重为 3，我将项目的三个副本放入数组中。然后，我随机选择一个项目。

我的方法很快，但使用了大量内存。我试图想出一种更快的方法，但没有想到。任何人都有解决这个问题的技巧？

编辑:我的代码...

显然，我没有说清楚。我不想使用(或改进)我的代码。这就是我所做的。

//Given an array $a where $a[0] is an item name and $a[1] is the weight from 1 to 100.
$b = array();
foreach($a as $t)
    $b = array_merge($b, array_fill(0,$t[1],$t));
$item = $b[array_rand($b)];

这要求我检查 $a 中的每个项目，并为数组使用 $a 内存的 max_weight/2*size。我想要一个完全不同的算法。

此外，我在半夜用电话问了这个问题。在手机上打代码几乎是不可能的，因为那些愚蠢的虚拟键盘简直太糟糕了。它会自动更正所有内容，破坏我输入的任何代码。

更进一步，我今天早上醒来时发现了一种全新的算法，该算法根本不使用虚拟内存，并且不需要检查数组中的每个项目。我在下面发布了它作为答案。

Answer 1

这是你的越橘。

  $arr = array(
    array("val" => "one", "weight" => 1),
    array("val" => "two", "weight" => 2),
    array("val" => "three", "weight" => 3),
    array("val" => "four", "weight" => 4)
  );

  $weight_sum = 0;
  foreach($arr as $val)
  {
    $weight_sum += $val['weight'];
  }

  $r = rand(1, $weight_sum);
  print "random value is $r\n";

  for($i = 0; $i < count($arr); $i++)
  {
    if($r <= $arr[$i]['weight'])
    {
      print "$r <= {$arr[$i]['weight']}, this is our match\n";
      print $arr[$i]['val'] . "\n";
      break;
    }
    else
    {
      print "$r > {$arr[$i]['weight']}, subtracting weight\n";
      $r -= $arr[$i]['weight'];
      print "new \$r is $r\n";
    }
  }

无需为每个权重生成包含一个项目的数组，无需为 n 的权重用 n 个元素填充数组。只需生成一个介于 1 和总重量之间的随机数，然后遍历数组，直到找到小于随机数的重量。如果它不小于该数字，则从随机数中减去该权重并继续。

示例输出:

# php wr.php
random value is 8
8 > 1, subtracting weight
new $r is 7
7 > 2, subtracting weight
new $r is 5
5 > 3, subtracting weight
new $r is 2
2 <= 4, this is our match
four

这也应该支持分数权重。

修改版本使用按权重键控的数组，而不是按项目

  $arr2 = array(
  );

  for($i = 0; $i <= 500000; $i++)
  {
    $weight = rand(1, 10);
    $num = rand(1, 1000);
    $arr2[$weight][] = $num;
  }

  $start = microtime(true);

  $weight_sum = 0;
  foreach($arr2 as $weight => $vals) {
    $weight_sum += $weight * count($vals);
  }

  print "weighted sum is $weight_sum\n";

  $r = rand(1, $weight_sum);
  print "random value is $r\n";
  $found = false;
  $elem = null;

  foreach($arr2 as $weight => $vals)
  {
    if($found) break;
    for($j = 0; $j < count($vals); $j ++)
    {
      if($r < $weight)
      {
        $elem = $vals[$j];
        $found = true;
        break;
      }
      else
      {
        $r -= $weight;
      }
    }
  }
  $end = microtime(true);

  print "random element is: $elem\n";
  print "total time is " . ($end - $start) . "\n";

使用示例输出:

# php wr2.php
weighted sum is 2751550
random value is 345713
random element is: 681
total time is 0.017189025878906

测量几乎不科学 - 并且根据元素落在数组中的位置(显然)而波动，但对于庞大的数据集来说它似乎足够快。