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

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

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

Откуда у вас эта группа цифр?

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

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

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

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

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

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

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

Я не имею большого значения для небольшого массива, но по мере того, как он становится больше, быстрый и простой способ увеличить скорость обработки - воспользоваться преимуществами индексации ключей массива, которая составляет 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

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

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

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

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

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

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

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