php - 我怎样才能逐渐使数组稀疏？

Question

我有一个完全填充的值数组，我想从这个数组中任意删除元素，并向远端删除更多元素。

例如，给定输入(其中 . 表示填充的索引)

............................................

我想要这样的东西

....... . ...  .. .  .  ..    .          .  

我的第一个想法是对元素进行计数，然后遍历数组生成一个介于当前索引和数组总大小之间的随机数，例如:

if ( mt_rand( 0, $total ) > $total - $current_index ) 
    //remove this element

但是，由于这需要在每次循环时生成一个随机数，因此变得非常困难。

有更好的方法吗？

Answer 1

一种简单的方法是为每个条目抛一枚加权硬币，最后抛硬币的权重更大。例如，如果数组的大小为 n，对于每个条目，您可以从 0 到 n-1 中选择一个随机数，并且仅当索引小于时才保留该值或等于随机数。 (也就是说，保留每个条目的概率为 1 - index/total。)这有一个很好的优势，如果你无论如何都要压缩你的数组，并且你使用的足够好但是高效的随机数生成器(可以是随机数上的简单整数散列)，内存访问速度会相当快。

另一方面，如果您只是删除一些项目而不是重新排列数组，您可以使用某种加权随机数生成器，它更经常地选择靠近索引末尾的数字。例如，如果您有一个随机数生成器生成值 [0,1] 的 float (闭边界或开边界不太可能)，请考虑获取这样的随机 float r 并进行平方它。这将倾向于选择较低的值。您可以通过翻转它来解决此问题:1-r^2。当然，你需要它在 0 到 n - 1 的索引范围内，所以取 floor(n * (1 - r^2)) 并将 n 向下舍入为 n-1。

这两种技术实际上有无数种变体。