通過“列表”，我的意思是英語單詞，而不是必要的鏈接列表。您可以使用任何數據結構。但是，PHP對某些數據結構具有內置支持：https://www.php.net/manual/en/spl.datastructures.php 從中最小堆似乎適合我的問題。雖然我不知道如何使用PHP的最小堆設施。假設一個循環正在從數據庫中讀取并輸出一些用戶ID，并且每個用戶ID的用戶名與輸入的單詞的相似程度。循環結束后，我想按分數的降序查看前10個用戶。分數計算在循環內完成。對我來說，最簡單的方法是：在計算分數（在循環內）時，將所有用戶ID及其分數存儲在數組中。存儲所有分數后，使用PHP的內置排序工具對數組進行排序。顯示數組中的前 10 個元素。但是，當我只想要10個頂級用戶時，為什么要打擾（系統）存儲和排序所有分數。那么，有什么好方法嗎？我想象的另一個可能的解決方案是這樣的，隨意忽略：PS：我對選擇所有元素后對頂部k元素進行排序沒有問題。
2 回答
鴻蒙傳說
TA貢獻1865條經驗 獲得超7個贊
您可以使用最小堆或最小優先級隊列（在 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);
一只甜甜圈
TA貢獻1836條經驗 獲得超5個贊
$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());
- 2 回答
- 0 關注
- 135 瀏覽
添加回答
舉報
0/150
提交
取消