PHP - Создайте отсортированный список лучших k предметов

Question

Под «списком» я подразумеваю слово Engli sh, необязательный связанный список. Вы можете использовать любую структуру данных. Однако PHP имеет встроенную поддержку некоторых структур данных: https://www.php.net/manual/en/spl.datastructures.php, из которых минимальная куча кажется мне подходящей для моей проблемы. Хотя я не знаю, как использовать средство минимальной кучи PHP.

Скажите, что oop читает из базы данных и выводит некоторые идентификаторы пользователей, а с каждым идентификатором пользователя оценка того, насколько похож имя пользователя сравнивается с введенным словом. После окончания l oop я хочу просмотреть 10 лучших пользователей в порядке убывания баллов. Расчет баллов выполняется внутри l oop.

Самый простой способ сделать это: вычисляя баллы (внутри l oop), сохраните все идентификаторы пользователей с их баллами в массиве. , После сохранения всех результатов отсортируйте массив с помощью встроенной функции сортировки 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']]);
}

Вывод созданной выше минимальной кучи:
Проверьте, является ли $topMatches isEmpty() или его count() равным 0. Если это тогда return;. Далее:

do{
 list($score, $userid) = $topMatches->extract();
 //echoing
}while($topMatches->valid());