php - 使用概率分布对数组进行排序

Question

数组应按其值从高到低排序。

<?php
$items = array(
  1 => f(1),
  2 => f(2),
  3 => f(3),
  4 => f(4),
  5 => f(5),
);
?>

排序后，我查看第 1、2、3、4、5 项中的哪一项是第一个。我一次又一次地尝试。 之后

• 5 应该是第一个项目，是 1 的五倍
• 4 应该是第一个项目，是 1 的四倍
• 3 应该是第一个项目，是 1 的三倍
• 4 应该是第一个项目，是 2 的两倍
• ...

一个想法是

<?php
function f(key) {
  return key / random();
}
?>

1'000'000 次尝试的结果

key | times on top | ratio with key one | expected ratio
----+--------------+--------------------+---------------
 5  |      374'365 | 6.75               | 5
 4  |      267'863 | 4.83               | 4
 3  |      185'707 | i am so lazy ...   | 3
 2  |      116'618 |                    | 2
 1  |       55'447 | 1                  | 1

对我来说看起来很奇怪，但也许

• f 有一个简单的问题吗？
• 还有更好的f吗？

---

我的实现:

<?php

abstract class Test {

  private $result;

  protected abstract function f($x);

  protected function iteration() {
    $values = array(
      1 => $this->f(1),
      2 => $this->f(2),
      3 => $this->f(3),
      4 => $this->f(4),
      5 => $this->f(5),
    );

    arsort($values);

    $top = key($values);

    if (!isset($this->result[$top])) {
      $this->result[$top] = 1;
    } else {
      $this->result[$top]++;
    }
  }

  public function run($iterations) {
    $this->result = array();
    for($i = 0; $i < $iterations; $i++) {
      $this->iteration();
    }
    arsort($this->result);
    return $this->result;
  }
}

class MyTest extends Test {
  protected function f($x) {
    return $x / rand();
  }
}

$test = new MyTest();
$result = $test->run(1000 * 1000);
print_r($result);
printf("Ratio of key 5 to 1, which should be 5: %f\n", $result[5] / $result[1]);

?>

---

我已经尝试了十亿轮。但比率还是 6.75 - 重点是:为什么不是 5？

---

结果

<?php
class BetterRandomGeneratorTest extends Test {
  protected function f($x) {
    return $x / mt_rand();
  }
}
?>

是

Array
(
  [5] => 3742816
  [4] => 2674352
  [3] => 1861444
  [2] => 1168333
  [1] => 553055
)
Ratio of key 5 to 1: 6.767529

Answer 1

这里有一个简单的 f 可以做到这一点。

function f(key) {
  $x = 0;
  for($i = 0; $i < $key; $i++) {
    $y = random();
    if ($x < $y) {
      $x = $y;
    }
  }
  return $x;
}

这保证有效，因为最大值同样可能是所选的 15 个随机数中的任何一个，并且该数字有 1/3 的时间位于 f(5) 中。 ，与 f(1) 的 1/15 相比.

至于你的f出了什么问题吗？ ，这很简单。您的解决方案具有良好的对称性，恰好 80% 的时间 f(1) < f(5) 。然而f(1)往往大于 f(5)当f(1)大于平均和 f(5)小于平均水平。 f(2) 同上, f(3)和f(4) 。然而，这对于所有 f(2), ... f(5) 来说都是不寻常的。一下子变小。这会导致相关性导致 f(1)成为最大的公司的频率比你天真的想象的要少。反之亦然，相关性往往有利于 f(5)比你天真的想象的更频繁。

如果您想计算每个数字排在首位的确切概率，那么通过积分计算准确答案应该不会太难。这个想法是，如果这是 random() 的值，则将概率从 0 积分到 1。对于 f(i)那f(i)是最大值。 (例如，对于 5，您将积分 (1-x/5)(1-x/4)(1-x/3)(1-x/2)，而对于 1，您将积分一个函数，如果 random() 大于 0.2，则该函数为 0，否则为 (1-2x)(1-3x)(1-4x)(1-5x)。)表达式将很复杂，并且比率不会得出很好的答案。