PHP - 构建前 k 个项目的排序列表

Question

通过“列表”，我的意思是英语单词，而不是必要的链接列表。您可以使用任何数据结构。但是，PHP对某些数据结构具有内置支持：https://www.php.net/manual/en/spl.datastructures.php 从中最小堆似乎适合我的问题。虽然我不知道如何使用PHP的最小堆设施。假设一个循环正在从数据库中读取并输出一些用户ID，并且每个用户ID的用户名与输入的单词的相似程度。循环结束后，我想按分数的降序查看前10个用户。分数计算在循环内完成。对我来说，最简单的方法是：在计算分数（在循环内）时，将所有用户ID及其分数存储在数组中。存储所有分数后，使用PHP的内置排序工具对数组进行排序。显示数组中的前 10 个元素。但是，当我只想要10个顶级用户时，为什么要打扰（系统）存储和排序所有分数。那么，有什么好方法吗？我想象的另一个可能的解决方案是这样的，随意忽略：PS：我对选择所有元素后对顶部k元素进行排序没有问题。

Answer 1

您可以使用最小堆或最小优先级队列（在 PHP 中略有不同）。当该堆具有 k 个元素时，当您找到的条目的分数高于堆中该最小分数时，请交换堆的顶部元素。然后，您最终将获得k个顶部条目，得分最低的位于顶部。因此，作为最后一步，您将从堆中提取条目并反转其顺序。

以下是使用SplPriorityQueue的外观。请注意，此结构将最大优先级值放在顶部，因此我们将为其提供负分数，以便在堆/队列顶部获得最低分数：

function getTop($input, $k) {

    $q = new SplPriorityQueue();

    $q->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);

    foreach ($input as $entry) {

        if ($q->count() < $k) {

            $q->insert($entry, -$entry["score"]); // negate score to get lower scores first

        } else if ($entry["score"] > -$q->top() ) { // better score than least in queue? Exchange

            $q->extract();

            $q->insert($entry, -$entry["score"]);

        }

    }

    $q->setExtractFlags(SplPriorityQueue::EXTR_DATA);

    return array_reverse(iterator_to_array($q));

}

下面是一些示例输入数据以及如何调用上述函数：

$input = [

    ["user" => "a", "score" => 17],

    ["user" => "b", "score" =>  3],

    ["user" => "c", "score" => 10],

    ["user" => "d", "score" => 11],

    ["user" => "e", "score" =>  5],

    ["user" => "f", "score" => 19],

    ["user" => "g", "score" =>  7],

    ["user" => "h", "score" =>  2],

    ["user" => "i", "score" => 18],

    ["user" => "j", "score" => 12],

    ["user" => "k", "score" => 10],

    ["user" => "l", "score" =>  6],

    ["user" => "m", "score" =>  9],

    ["user" => "n", "score" => 15],

];

$top = getTop($input, 5);

print_r($top);

Answer 2

$topMatches = new SplMinHeap();

/* Building the list */

while($user = mysqli_fetch_assoc($users)){

 .. calculate score of the $user against the inputted word ..

 if($topMatches->count() === $k)

  if($topMatches->top()[0] < $score) //haven't && both if's cause ->top will give error when heap empty

   $topMatches->extract();

 if($topMatches->count() !== $k)

  $topMatches->insert([$score, $user['id']]);

}

输出上述创建的最小堆：

检查其是否为 0。如果是的话.下一个：$topMatchesisEmpty()count()return;

do{

 list($score, $userid) = $topMatches->extract();

 //echoing

}while($topMatches->valid());