加权随机排序

Question

我需要根据对象的权重对一组对象进行随机排序。我做了以下功能：

function weightedRandomSort($objects) {
    uasort($objects, function($a, $b) {
        $rand = rand(1, 9999) / 10000;
        $totalWeight = $a->weight + $b->weight;
        $probabilityA = $a->weight / $totalWeight;  
        if ($rand < $probabilityA) return 1; // a > b
        else return -1;
    });

    return $objects;
}

该功能可以工作，但根据我的测试，我觉得它不能正常工作。有谁注意到逻辑有问题吗？

Answer 1

我假设您想要对元素进行排序，使得每个元素成为第一个元素的几率与其权重成正比。如果他们不是第一，那么他们成为第二的几率与其权重成正比。等等。

您当前逻辑的问题在于它非常依赖于排序的实现方式。例如，如果排序在内部是 quicksort，那么选择的第一个主元会经过

O(n)

比较，而大多数元素会经过

O(log(n))

比较。连续赢得

n

比较比

O(log(n))

更难，因此元素获胜的几率既取决于它的权重，也取决于它是否被选为早期枢轴。

你想要的东西可以通过一个基于权重随机采样的函数来及时实现

O(n^2)

。首先取样，然后将其取出。第二次取样然后将其取出。等等。我认为您想要比这种幼稚的方法更有效的方法。

诀窍是使用指数分布。您可以使用 PHP 中的 stats_rand_gen_exponential 进行采样。让我解释一下它是如何工作的。

假设你有一大块放射性物质。有大量原子，每个原子都可能随时衰变，但单个原子则不太可能衰变。当它确实衰变时，您会听到“盖革计数器”的咔哒声。在整个样本中，原子以每秒 λ 的速度衰变。指数分布描述了距离下一次点击还有多长时间的分布。比

λ

越大，点击可能会越早出现。您关心的属性是

stats_rand_gen_exponential(x)

给出的数字小于

stats_rand_gen_exponential(y)

的数字的几率是

x/(x+y)

。这会扩大规模。因此，对于每个元素，记录

stats_rand_gen_exponential($element->weight)

。根据这些随机数对它们进行升序排序。您得到的随机分布正是您想要的。随机，每个元素首先出现的几率与其权重完全成正比。依此类推。至于执行此操作的代码，我们将借用

Schwartzian 变换

。这是未经测试的代码。

// decorate
array_walk($array, create_function('&$v, $k', '$v = array($v, stats_rand_gen_exponential($v->weight));'));
// sort
usort($array, create_function('$a,$b', 'return $a[1] <=> $b[1];'));
// undecorate
array_walk($array, create_function('&$v, $k', '$v = $v[0];'));