Самый быстрый способ получить самые большие числа X из очень большого несортированного списка?

Question

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

Каков наилучший способ сортировки, чтобы получить 100 лучших результатов?

Единственный способ, о котором я могу думать до сих пор, это либо сначала сгенерировать все оценки в массивном массиве, а затем отсортировать их и взять первые 100. Или, во-вторых, сгенерировать число X, отсортировать их и обрезать 100 лучших. Затем баллы продолжают генерировать больше баллов, добавляя их в усеченный список и затем сортируя снова.

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

Наконец, какой алгоритм сортировки используется стандартной функцией sort () в c ++?

Спасибо,

-Faken

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

Я провел несколько временных испытаний до и после, и вот результаты:

Старая программа (сортировка преформ после каждой итерации внешнего цикла):

top 100 scores: 147 seconds
top  10 scores: 147 seconds
top   1 scores: 146 seconds
Sorting disabled: 55 seconds

новая программа (реализующая отслеживание только лучших результатов и использующая функцию сортировки по умолчанию):

top 100 scores: 350 seconds <-- hmm...worse than before
top  10 scores: 103 seconds 
top   1 scores:  69 seconds 
Sorting disabled: 51 seconds

новое переписывание (оптимизация хранимых данных, алгоритм сортировки от руки):

top 100 scores: 71 seconds <-- Very nice!
top  10 scores: 52 seconds
top   1 scores: 51 seconds
Sorting disabled: 50 seconds

Готово на ядре 2, 1,6 ГГц ... Я не могу дождаться, когда появится мое ядро ​​i7 860 ...

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

Спасибо eveyrone за их вклад!

Answer 1

Вы хотите абсолютные наибольшие числа X, так что я предполагаю, что вам не нужна какая-то эвристика. Насколько не отсортирован список? Если это довольно случайно, лучше всего сделать быструю сортировку по всему списку и получить лучшие результаты X.

Если вы можете фильтровать результаты во время генерации списка, это намного лучше. Сохраняйте только значения X, и каждый раз, когда вы получаете новое значение, сравнивайте его с этими значениями X. Если это меньше чем все они, выбросьте это. Если он больше одного из них, выведите новое наименьшее значение.

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