Алгоритм сбора наименьших чисел

Question

Я ищу алгоритм (или, я полагаю, код PHP), чтобы в итоге получить 10 самых младших чисел из группы чисел. Я думал о создании массива из десяти элементов, проверке, чтобы видеть, является ли текущее число меньше, чем одно из чисел в массиве, и, если это так, нахождение наибольшего числа в массиве и замена его на текущее число.

Однако я планирую найти самые низкие 10 цифр из тысяч, и подумал, что может быть более быстрый способ сделать это. Я планирую реализовать это на PHP, чтобы можно было использовать любые нативные функции PHP.

Answer 1

Сортируйте массив и используйте десять первых / последних записей.

Честно говоря: сортировка массива с тысячами записей требует меньше времени, чем мигание.

Answer 2

То, что вы ищете, называется алгоритм выбора . На странице Википедии по этому вопросу есть несколько подразделов в разделе , в котором выбирается k самых маленьких или самых больших элементов . Когда список достаточно велик, вы можете разбить время, необходимое для наивного "сортировки всего списка и выбора первых 10" алгоритмов.

Answer 3

Наивный подход - просто отсортировать ввод. Вероятно, это достаточно быстро, поэтому просто попробуйте и профилируйте, прежде чем делать что-то более сложное.

Потенциально более быстрый подход: линейно ищите вход, но сохраняйте отсортированный выходной массив, чтобы было легче определить, принадлежит ли следующий вход в массив или нет. Псевдокод:

output[0-9] = input[0-9];
sort(output);
for i=10..n-1
  if input[i] < output[9]
    insert(input[i])

, где insert (x) найдет правильное место (бинарный поиск) и сделает соответствующее смещение.

А если серьезно, попробуйте сначала наивный подход.

Answer 4

Для небольшого массива я ничего не значу, но, поскольку он становится больше, быстрый и простой способ увеличить скорость обработки - воспользоваться индексацией ключа массива, которая составляет 1 мил. строки будут использовать около 40% времени. Пример:

// sorting array values

$numbers = array();
for($i = 0; $i < 1000000; ++$i)
{
    $numbers[$i] = rand(1, 999999);
}

$start = microtime(true);
sort($numbers);
$res = array_slice($numbers, 0, 10, true);
echo microtime(true) - $start . "\n";
// 2.6612658500671
print_r($res);

unset($numbers, $res, $start);


// sorting array keys

$numbers = array();
for($i = 0; $i < 1000000; ++$i)
{
    $numbers[rand(1, 999999)] = $i;
}

$start = microtime(true);
ksort($numbers);
$res = array_keys(array_slice($numbers, 0, 10, true));
echo microtime(true) - $start . "\n";
// 0.9651210308075
print_r($res);

Но если данные массива взяты из базы данных, возможно, быстрее всего просто отсортировать их там:

SELECT number_column FROM table_with_numbers ORDER BY number_column LIMIT 10

Answer 5

Где вы получаете эту группу чисел?

Если ваш Список чисел уже находится в массиве, вы можете просто сделать sort () , а затем array_slice () , чтобы получить первые 10.

Answer 6

Я бы использовал кучу с 10 элементами и наибольшим числом в корне дерева. Затем начните с начала списка номеров:

• Если в куче менее 10 элементов: добавьте номер в список
• В противном случае, если число меньше наибольшего числа в куче, удалите наибольшее число в куче, а затем добавьте текущий номер в список
• В противном случае игнорируйте его.

Вы получите 10 самых младших чисел в куче. Если вы используете массив в качестве структуры данных кучи, то вы можете просто использовать массив напрямую.

(альтернативно: вы можете вырезать первые 10 элементов и накапливать их вместо использования первого шага, который будет немного быстрее).

Однако, как отметили другие люди, для 1000 элементов просто отсортируйте список и возьмите первые 10 элементов.

Answer 7

Создайте отсортированный набор (TreeSet в Java, я не знаю о PHP) и добавьте первые 10 чисел. Теперь итерируйте по остальным номерам. Итерируйте по всем вашим номерам, добавьте новый, затем удалите самый большой номер из набора.

Этот алгоритм равен O (n), если n >> 10.