根据区域随机

Question

我有一个元素数组：

$arr = array(
  '0' => 265000, // Area
  '1' => 190000,
  '2' => 30000,
  '3' => 1300
);

我想根据区域（数组值）获取随机索引。我需要更频繁地选择具有大价值的区域。我怎样才能做到这一点？

我现在拥有的：

$random_idx = mt_rand(0, count($arr)-1);    
$selected_area = (object)$arr[$random_idx];

谢谢！

Answer 1

1. 重复值

假设我们有一个数组，其中每个值都对应于其索引的相对概率。例如，给定一枚硬币，抛掷硬币的可能结果是 50% 为反面，50% 为正面。我们可以用数组来表示这些概率，例如（我将使用 PHP，因为这似乎是 OP 使用的语言）：

$coin = array(     
     'head' => 1,    
     'tails' => 1    
);

而掷两个骰子的结果可以表示为：

$dice = array( '2' => 1, '3' => 2, '4' => 3, '5' => 4, '6' => 5, '7' => 6,
               '8' => 5, '9' => 4, '10' => 3, '11' => 2, '12' => 1
);

选择概率与这些数组的值成比例（因此与底层模型一致）的随机键（索引）的一种简单方法是创建另一个数组，其元素是原始数组的键，重复指定次数值，然后返回一个随机值。例如对于dice数组：

$arr = array( 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, ...

这样做，我们确信每个密钥都会以正确的相对概率被拾取。我们可以使用构造函数将所有逻辑封装在一个类中，该构造函数构建辅助数组和使用mt_rand()返回随机索引的函数：

class RandomKeyMultiple {
    private $pool = array();
    private $max_range;

    function __construct( $source ) {
        // build the look-up array
        foreach ( $source as $key => $value ) {
            for ( $i = 0; $i < $value; $i++ ) {
                $this->pool[] = $key;
            }
        }
        $this->max_range = count($this->pool) - 1;
    }

    function get_random_key() {
        $x = mt_rand(0, $this->max_range);

        return $this->pool[$x];     
    }
}

用法很简单，只需创建一个传递源数组的类的对象，然后每次调用该函数都会返回一个随机密钥：

$test = new RandomKeyMultiple($dice);
echo $test->get_random_key();

问题是 OP 的数组包含很大的值，这会导致一个非常大（但仍然可以管理，即使不将所有值除以 100）的数组。

2. 步骤

一般来说，离散概率分布可能更复杂，浮点值无法轻松转换为重复次数。

解决该问题的另一种方法是将数组中的值视为划分所有可能值的全局范围的间隔的错误：

    +---------------------------+-----------------+-------+----+
    |                           |                 |       |    |
    |<---       265000      --->|<--   190000  -->|<30000>|1300| 
    |<-------            455000            ------>|            |
    |<----------              485000            --------->|    |
    |<----------------            486300        -------------->|

然后我们可以选择 0 到 486300（全局范围）之间的随机数并查找正确的索引（其几率与其段的长度成正比，从而给出正确的概率分布）。就像是：

$x = mt_rand(0, 486300);
if ( $x < 265000 )
    return 0;
elseif ( $x < 455000 )
    return 1;
elseif ( $x < 485000 )
    return 2;
else
    return 3;

我们可以概括该算法并将所有逻辑封装在一个类中（使用辅助数组来存储部分和）：

class RandomKey {
    private $steps = array();
    private $last_key;
    private $max_range;

    function __construct( $source ) {
        // sort in ascending order to partially avoid numerical issues
        asort($source);  

        // calculate the partial sums. Considering OP's array:
        //
        //   1300 ---->       0
        //  30000 ---->    1300
        // 190000 ---->   31300
        // 265000 ---->  221300  endind with $partial = 486300
        //
        $partial = 0;
        $temp = 0;
        foreach ( $source as $k => &$v ) {
            $temp = $v;
            $v = $partial;
            $partial += $temp;
        }

        // scale the steps to cover the entire mt_rand() range
        $factor = mt_getrandmax() / $partial;
        foreach ( $source as $k => &$v ) {
            $v *= $factor;
        }

        // Having the most probably outcomes first, minimizes the look-up of
        // the correct index
        $this->steps = array_reverse($source);

        // remove last element (don't needed during checks) but save the key
        end($this->steps);
        $this->last_key = key($this->steps);
        array_pop($this->steps);
    }

    function get_random_key() {
        $x = mt_rand();

        foreach ( $this->steps as $key => $value ) {
            if ( $x > $value ) {
                return $key;
            }
        }
        return $this->last_key;     
    }

}

这里或这里有现场演示，其中包含一些示例和辅助函数来检查键的概率分布。

对于更大的数组，也可以考虑使用二分搜索来查找索引。