PHP：优化数组迭代

Question

我正在研究一种基于最高得分的团队排序算法。团队是从玩家列表中生成的。创建团队的条件是：

• 必须有6名球员。
• 6名球员的总薪水必须小于或等于50K。
• 团队是根据最高集体预测值生成的。

为了得到这个结果，我生成了所有可能的团队，然后对它们进行检查，排除那些薪水超过50K的团队，然后根据预测值对其余团队进行排序。但是生成所有可能性需要很长时间，有时会消耗所有内存。对于160名球员的列表，需要大约90秒。以下是代码：

$base_array = array();
$query1 = mysqli_query($conn, "SELECT * FROM temp_players  ORDER BY projection DESC");
while($row1 = mysqli_fetch_array($query1))
{
    $player = array();
    $mma_id = $row1['mma_player_id'];
    $salary = $row1['salary'];
    $projection = $row1['projection'];
    $wclass = $row1['wclass'];

    array_push($player, $mma_id);
    array_push($player, $salary);
    array_push($player, $projection);
    array_push($player, $wclass);

    array_push($base_array, $player);
}


$result_base_array = array();
$totalsalary = 0;

for($i=0; $i<count($base_array)-5; $i++)
{
    for($j=$i+1; $j<count($base_array)-4; $j++)
    {
        for($k=$j+1; $k<count($base_array)-3; $k++)
        {
            for($l=$k+1; $l<count($base_array)-2; $l++)
            {
                for($m=$l+1; $m<count($base_array)-1; $m++)
                {
                    for($n=$m+1; $n<count($base_array)-0; $n++)
                    {
                        $totalsalary = $base_array[$i][1]+$base_array[$j][1]+$base_array[$k][1]+$base_array[$l][1]+$base_array[$m][1]+$base_array[$n][1];
                        $totalprojection = $base_array[$i][2]+$base_array[$j][2]+$base_array[$k][2]+$base_array[$l][2]+$base_array[$m][2]+$base_array[$n][2];
                        if($totalsalary <= 50000)
                        {
                            array_push($result_base_array, 
                            array($base_array[$i], $base_array[$j], $base_array[$k], $base_array[$l], $base_array[$m], $base_array[$n],
                            $totalprojection, $totalsalary)
                            );

                        }
                    }
                }
            }
        }

    }
}

usort($result_base_array, "cmp");

还有cmp函数

function cmp($a, $b) {
    if ($a[6] == $b[6]) {
        return 0;
    }
    return ($a[6] < $b[6]) ? 1 : -1;
}

有没有任何方法可以缩短完成这项任务的时间，或者有没有其他解决方案来获得所需数量的团队？

此致

- Junaid Noor

---

为什么你要用PHP来做这件事？你可以使用条件查询来获取结果。 - Aabir Hussain

你的代码有点疯狂。请发布你的表模式，看看是否可以通过更合理的SQL查询来解决问题。 - yivi

这是一个非常有趣的问题.. 你能提供数据集吗？（如果它不包含个人信息的话） - John Mc Murray

假设一些条件：SELECT wclass, SUM(sallary) AS total_sallary, SUM(projection) AS total_projection FROM temp_players GROUP BY wclass HAVING total_sallary <= 50000 ORDER BY total_projection DESC - Santa's helper

@Junaid Noor，你需要所有的团队结果还是只需要前10-20个团队就可以了？ - Arnial

Answer 1

由于数组中的元素数量可能非常大（例如100个球员可以生成1.2 * 10 ^ 9个团队），您无法将其保存在内存中。尝试通过部分方式将结果数组保存到文件中（在每次保存后截断数组）。然后使用外部文件排序。

这样做会很慢，但至少不会因为内存而崩溃。

如果您需要前n个团队（例如具有最高投影值的10个团队），则应将生成result_base_array的代码转换为Generator，以便它可以yield下一个团队而不是将其推入数组中。然后迭代此生成器。在每次迭代中，将新项添加到排序后的结果数组中并剪切冗余元素。

- Arnial

Answer 2

根据薪资是否经常导致排除的原因，您也可以在其他循环中对此进行测试。如果在选择4名球员后，他们的总薪资已经超过50K，那么就没有必要选择剩下的2名球员。这可以节省一些迭代。

通过记住包中最低的6个薪水，可以进一步改进，并检查在选择4个成员后，如果添加2个最低的现有薪水仍然保持在50K以下。如果不可能，则再次尝试添加另外两名球员是没有意义的。当然，这可以在每个选择阶段（选择1名球员、2名球员等）进行。

另一个相关的改进是在按升序薪资排序数据时发挥作用。如果在选择第4名球员后，上述逻辑使您得出结论，即通过添加2名球员无法保持在50K以下，那么替换数据系列中的第4名球员也没有意义：该球员的薪水更高，因此总薪资也会超过50K。因此，这意味着您可以立即回溯并处理第3个球员的选择。

正如其他人所指出的那样，潜在解决方案的数量是巨大的。对于160个团队和每个团队6名成员的情况，组合数为：

160 . 159 . 158 . 157 . 156 . 155
--------------------------------- = 21 193 254 160
        6 . 5 . 4 . 3 . 2

21亿个条目对于内存来说是一个挑战，而且对你来说可能也没有用：你真的会对第4 432 456 911^th名的团队感兴趣吗？

你可能对前十名团队（按照预测排名）感兴趣。你可以通过保持一个最佳团队的列表来实现这一点，当你获得一个薪水可接受的新团队时，将其添加到该列表中，并保持排序（通过二分搜索），并从前十名中剔除预测最低的条目。

以下是你可以使用的代码：

$base_array = array();
// Order by salary, ascending, and only select what you need
$query1 = mysqli_query($conn, "
     SELECT   mma_player_id, salary, projection, wclass 
     FROM     temp_players 
     ORDER BY salary ASC");
// Specify with option argument that you only need the associative keys:
while($row1 = mysqli_fetch_array($query1, MYSQLI_ASSOC)) {
    // Keep the named keys, it makes interpreting the data easier:
    $base_array[] = $row1;
}

function combinations($base_array, $salary_limit, $team_size) {
    // Get lowest salaries, so we know the least value that still needs to
    // be added when composing a team. This will allow an early exit when
    // the cumulative salary is already too great to stay under the limit.
    $remaining_salary = [];
    foreach ($base_array as $i => $row) {
        if ($i == $team_size) break;
        array_unshift($remaining_salary, $salary_limit);
        $salary_limit -= $row['salary'];
    }

    $result = [];
    $stack = [0];
    $sum_salary = [0];
    $sum_projection = [0];
    $index = 0;
    while (true) {
        $player = $base_array[$stack[$index]];
        if ($sum_salary[$index] + $player['salary'] <= $remaining_salary[$index]) {
            $result[$index] = $player;
            if ($index == $team_size - 1) {
                // Use yield so we don't need to build an enormous result array:
                yield [
                    "total_salary" => $sum_salary[$index] + $player['salary'],
                    "total_projection" => $sum_projection[$index] + $player['projection'],
                    "members" => $result
                ];
            } else {
                $index++;
                $sum_salary[$index] = $sum_salary[$index-1] + $player['salary'];
                $sum_projection[$index] = $sum_projection[$index-1] + $player['projection'];
                $stack[$index] = $stack[$index-1];
            }
        } else {
            $index--;
        }
        while (true) {
            if ($index < 0) {
                return; // all done
            }
            $stack[$index]++;
            if ($stack[$index] <= count($base_array) - $team_size + $index) break;
            $index--;
        }
    }
}

// Helper function to quickly find where to insert a value in an ordered list
function binary_search($needle, $haystack) {
    $high = count($haystack)-1;
    $low = 0;
    while ($high >= $low) {
        $mid = (int)floor(($high + $low) / 2);
        $val = $haystack[$mid];
        if ($needle < $val) {
            $high = $mid - 1;
        } elseif ($needle > $val) {
            $low = $mid + 1;
        } else {
            return $mid;
        }
    }
    return $low;
}

$top_team_count = 10; // set this to the desired size of the output
$top_teams = []; // this will be the output
$top_projections = [];
foreach(combinations($base_array, 50000, 6) as $team) {
    $j = binary_search($team['total_projection'], $top_projections);
    array_splice($top_teams, $j, 0, [$team]);
    array_splice($top_projections, $j, 0, [$team['total_projection']]);
    if (count($top_teams) > $top_team_count) {
        // forget about lowest projection, to keep memory usage low
        array_shift($top_teams);
        array_shift($top_projections);
    }
}
$top_teams = array_reverse($top_teams); // Put highest projection first

print_r($top_teams);

看一下eval.in上的演示, 它只是生成了12个具有随机薪资和预测数据的球员。

最后的话

即使进行了上述优化，对160支队伍进行此操作仍可能需要大量迭代。薪资总额超过50K的次数越多，性能就会越好。如果从未发生这种情况，算法就无法避免必须查看21亿个组合中的每一个。如果您事先知道50K限制不起任何作用，那么您当然会像最初一样按降序排序数据。

另一个优化方法是，如果您将到目前为止第10高的团队预测反馈到组合函数中。该函数可以消除导致较低总预测的组合。您可以首先取6个最高的球员预测值，并使用它来确定通过添加缺少的球员可以增加多高的部分团队预测。可能会发现，在选择了一些球员之后，这变得不可能，然后您可以跳过一些迭代，就像基于薪资所做的那样。

- trincot