arrays - 基于区域随机

Question

我有一个元素数组:

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

我想根据面积(数组值)获取随机索引。我需要更频繁地选择值(value)大的区域。
我怎样才能做到这一点？

我现在拥有的:

$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;     
    }

}

Here或 here有一些示例和帮助函数的现场演示来检查 key 的概率分布。

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