0

“列表”是指英文单词，不是必需的链表。您可以使用任何数据结构。但是，PHP 内置了对某些数据结构的支持：https ://www.php.net/manual/en/spl.datastructures.php从中最小堆似乎适合我的问题。虽然我不知道如何使用 PHP 的最小堆设施。

假设一个循环正在从数据库中读取并输出一些用户 ID，并且每个用户 ID 都会对用户名与输入单词的相似程度进行比较。循环结束后，我想按分数降序查看前 10 名用户。分数计算在循环内完成。

对我来说最简单的方法是：在计算分数时（在循环内），将所有用户 ID 及其分数存储在一个数组中。存储所有分数后，使用 PHP 的内置排序工具对数组进行排序。显示数组中的前 10 个元素。
但是，当我只想要 10 个顶级用户时，为什么还要麻烦（系统）存储和排序所有分数。那么，有什么好的方法吗？

我想象的另一个可能的解决方案是，请随意忽略：

维护一个按降序排列的分数链表。达到长度10后，接收到一个新的score时，检查它是否小于最右边节点（第10个节点）的score，如果是则丢弃它，如果不是则丢弃最右边的节点并插入新的通过检查它是否小于链表的第 5 个（中间）元素，在适当的位置得分，如果它与第 7 个（第 5 和第 9 的中间）相同，依此类推。

PS：我对前 k 个元素在全部被选中后进行排序没有问题。

4

2 回答 2

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);
于 2020-01-27T11:01:23.327 回答
0 
$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']]);
}

输出上面创建的最小堆：
检查$topMatches isEmpty()它是否count()为 0。如果是，则return;。下一个：

do{
 list($score, $userid) = $topMatches->extract();
 //echoing
}while($topMatches->valid());
于 2020-01-27T11:45:45.613 回答