Я ищу алгоритм (или PHP-код, я полагаю), чтобы получить 10 самых низких чисел из группы чисел. Я думал о создании массива из десяти элементов, проверяя, находится ли текущее число ниже, чем одно из чисел в массиве, и если да, то найдем наибольшее число в массиве и заменим его текущим номером.
Тем не менее, я планирую найти самые низкие 10 чисел из тысяч, и думал, что может быть более быстрый способ сделать это. Я планирую реализовать это на PHP, поэтому любые встроенные функции PHP можно использовать.
То, что вы ищете, называется алгоритмом выбора . На странице Википедии по этому вопросу есть несколько подразделов в разделе выбора k самых маленьких или самых больших элементов . Когда список достаточно велик, вы можете выиграть время, необходимое для наивного «сортировать весь список и выбирать первый 10» алгоритм.
Сортируйте массив и используйте десять первых / последних записей.
Честно говоря: сортировка массива с тысячей записей стоит меньше времени, чем требуется, чтобы мигать.
Наивный подход заключается в просто сортировке ввода. Это, скорее всего, достаточно быстро, так что просто попробуйте и профилируйте его, прежде чем делать что-то более сложное.
Потенциально быстрый подход: линейно искать входные данные, но сохраняйте сортировку выходного массива, чтобы было легче определить, принадлежит ли следующий вход в массиве или нет. псевдокод:
output[0-9] = input[0-9]; sort(output); for i=10..n-1 if input[i] < output[9] insert(input[i]) где insert (x) найдет нужное место (двоичный поиск) и выполнит соответствующее смещение.
Но серьезно, сначала попробуйте наивный подход.
Где вы получаете эту группу чисел?
Если ваш список чисел уже находится в массиве, вы можете просто сделать sort () , а затем array_slice (), чтобы получить первые 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 элементов и исцелить их вместо того, чтобы использовать первый шаг выше, который будет немного быстрее).
Однако, как отметили другие люди, за 1000 элементов просто отсортируйте список и возьмите первые 10 элементов.