l-1

PHP笔记

主页/PHP笔记/PHP问答/数据结构/PHP算法：加权随机选择

PHP算法：加权随机选择

Bug编译狮

Bug编译狮

好的，下面是一个用PHP实现的加权随机选择算法的示例：

<?php

// 定义一个数组，其中键是权重，值是对应的选项
$choices = array(
    'option1' => 3,
    'option2' => 5,
    'option3' => 2
);

// 计算总权重
$totalWeight = array_sum($choices);

// 初始化一个累积权重变量
$cumulativeWeight = 0;

// 生成一个0到总权重之间的随机数
$randomNumber = mt_rand(1, $totalWeight);

// 遍历数组，找到第一个累积权重大于等于随机数的项
foreach ($choices as $key => $weight) {
    $cumulativeWeight += $weight;
    if ($cumulativeWeight >= $randomNumber) {
        echo "随机选择的结果是: " . $key . "n";
        break;
    }
}
?>

在这个示例中，我们首先定义了一个包含多个选项及其对应权重的数组。然后，我们计算了所有权重的总和。接着，我们使用mt_rand()函数生成一个0到总权重之间的随机数。

最后，我们遍历数组，找到第一个累积权重大于等于随机数的项，并输出该选项作为结果。

你可以根据需要修改$choices数组中的选项及其权重。希望这个示例对你有帮助！

黑板Bug讲师

黑板Bug讲师

介绍

实施随机性在应用中的使用可以带来更加动态和互动的用户体验。当涉及到随机性时，不是所有的选择都是平等的——一些选项可能需要比其他选项更频繁地被选择。这一概念与加权随机选择算法紧密相关，这是一种基于权重而不是均匀概率的选择算法。本教程将指导您如何使用PHP实现加权随机选择算法的过程。

理解加权随机选择

在加权随机选择中，集合中的每个元素都会分配一个权重，该权重代表被选中的概率。权重越高，被选中的可能性越大。普通随机选择对每种可能的等概率处理，但“加权”的方面则倾向于某些元素。

考虑一个基于加权随机算法的简单竞赛，奖品包括一辆车、一辆自行车和一套贴纸。你可以为贴纸分配更高的权重，因为它们的价值较低且有更多可供分发的，而把自行车的权重设得更低一些，因为它是最有价值的，很可能是最稀有的。这样可以确保每个人都有可能获得任何奖品，但这种分布不是完全随机的，而是控制和有意为之的。

简单随机权重示例

<?php
function simpleWeightedRandom(array $weights) {
    $totalWeight = array_sum($weights);
    $random = mt_rand(1, $totalWeight);
    foreach ($weights as $key => $weight) {
        if ($random <= $weight) {
            return $key;
        }
        $random -= $weight;
    }
}

// Define weights
$items = ['car' => 1, 'bike' => 3, 'stickers' => 10];

// Get a weighted random item
$winner = simpleWeightedRandom($items);

echo 'Winner prize: ' . $winner . "n";
?>

该基本的基于权重的选择函数通过首先汇总总重量来运作。然后，它生成一个在这个范围内的随机整数。通过迭代遍历权重集并逐步减少随机数字与每个元素的权重相乘的结果，函数得出基于权重的选择。

优化算法

上面提供的简单算法对于小集合适用，但对于较大的数据集可能效率低下，因为它的选择过程与元素的数量呈线性关系。为了提高大型数据集的性能，我们可以优化我们的方法。一种这样的方法是使用二分查找，这将选择过程的时间复杂度降低到对数级别。

构建累积权重数组。

为了准备一个更高效的算法，我们首先需要将我们的权重转换为累积数组。这会将我们的权重列表转化为一个累计总和，然后我们可以与二分查找结合使用。

<?php
function cumulativeWeights(array $weights) {
    $cumulative = [];
    $total = 0;
    foreach ($weights as $item => $weight) {
        $total += $weight;
        $cumulative[$item] = $total;
    }
    return $cumulative;
}

$items = ['car' => 1, 'bike' => 3, 'stickers' => 10];
$cumulativeWeights = cumulativeWeights($items);
?>

二分查找法用于权重随机选择。

现在我们有了累计重量数组，我们可以进行二分查找来找到我们的加权随机选择。通过反复将数据集减半，并将随机生成的数字与集合中的中间元素进行比较，我们可以高效地定位所需的权重阈值。

<?php
function binaryWeightedRandom(array $cumulativeWeights) {
    $totalWeight = end($cumulativeWeights);
    $random = mt_rand(1, $totalWeight);
    $low = 0;
    $high = count($cumulativeWeights) - 1;

    while ($low < $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($random > $cumulativeWeights[$mid]) {
            $low = $mid + 1;
        } else {
            $high = $mid;
        }
    }
    return array_keys($cumulativeWeights)[$high];
}

$winner = binaryWeightedRandom($cumulativeWeights);

echo 'Winner prize: ' . $winner . "n";
?>

优化后的加权随机选择过程将更好地处理大数据集，为您的应用提供所需的所有随机性和效率。

考虑因素及潜在风险

在实施加权随机选择算法时，确保总权重不太大以处理您的PHP运行环境至关重要，特别是对于32位系统。如果您的权重是以浮点数形式给出或存在显著差异，可能需要更高级别的方法来避免精度错误或算术溢出。

在为特定用例设计算法时，考虑边缘情况并明确定义遇到零或负权重的行为。不断测试函数以确认其行为符合预期，同时使用各种权重分布进行验证。

结论。

加权随机选择在各种应用中都有实用价值，比如游戏和负载均衡等。实现的复杂性主要取决于数据集的大小以及应用程序的需求性能要求。有了对这一基本技术的理解，PHP 开发者可以利用加权概率的力量来丰富应用程序逻辑并以有意义的方式控制随机性。

长工码奴1523

长工码奴1523

在 PHP 中实现加权随机选择（weighted random selection）是一种常见的编程问题。这种机制允许我们根据每个选项的权重来决定最终的选择。

基本概念

加权随机选择是通过给不同的选项分配不同的权重（例如，分数），然后从这些选项中随机选择一个，其结果取决于每个选项的权重之和。这样做的目的是确保更有可能选择到那些对用户来说更重要或者更有价值的选项。

实现方法

我们可以使用以下 PHP 函数来计算总权重，并从中随机选择一个元素：

function weighted_random_choice($options, $weights) {
    // 初始化总权重为0
    $totalWeight = 0;

    // 遍历所有选项及其权重
    foreach ($options as $option => $weight) {
        $totalWeight += $weight;
    }

    // 计算当前权重除以总权重得到的概率
    $probability = 1 / $totalWeight;

    // 随机生成一个在 [0, 1] 范围内的数
    $randomNumber = rand(0, 1);

    // 累加概率
    for ($i = 0; $i < count($options); $i++) {
        if ($randomNumber <= $probability * $weights[$i]) {
            return $options[$i];
        }
    }
}

示例代码

假设我们有一个名为 products 的数组，其中包含商品名和相应的评分：

$products = [
    ['name' => 'Product A', 'score' => 4],
    ['name' => 'Product B', 'score' => 5],
    ['name' => 'Product C', 'score' => 3]
];

// 使用加权随机选择函数选择产品
$selected_product = weighted_random_choice($products, [2, 3, 1]);
echo "Selected product: " . $selected_product['name'];

在这个例子中，”Product B” 是被选中的，因为它的权重（2 + 1 = 3）大于其他两个产品的权重（2 + 3 = 5）。

最新更新