Самый быстрый способ получить самые большие числа 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

1. взять первые 100 баллов и отсортировать их в массив.
2. взять следующий счет и вставить-отсортировать его в массив (начиная с «малого» конца)
3. сбросить 101-е значение
4. переходите к следующему значению, в 2, пока не будет выполнено

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

Answer 2

Вы можете сделать это за O (n) раз, без какой-либо сортировки, используя кучу:

#!/usr/bin/python

import heapq

def top_n(l, n):
    top_n = []

    smallest = None

    for elem in l:
        if len(top_n) < n:
            top_n.append(elem)
            if len(top_n) == n:
                heapq.heapify(top_n)
                smallest = heapq.nsmallest(1, top_n)[0]
        else:
            if elem > smallest:
                heapq.heapreplace(top_n, elem)
                smallest = heapq.nsmallest(1, top_n)[0]

    return sorted(top_n)


def random_ints(n):
    import random
    for i in range(0, n):
        yield random.randint(0, 10000)

print top_n(random_ints(1000000), 100)

Время на моей машине (Core2 Q6600, Linux, Python 2.6, измерено с помощью bash time встроенный):

• 100000 элементов: .29 секунд
• 1000000 элементов: 2,8 секунды
• 10000000 элементов: 25,2 секунды

Редактирование / дополнение: В C ++ вы можете использовать std::priority_queue почти так же, как здесь используется модуль Python heapq. Вы захотите использовать порядок std::greater вместо значения по умолчанию std::less, чтобы функция-член top() возвращала наименьший элемент вместо самого большого. Очередь приоритетов в C ++ не имеет эквивалента heapreplace, который заменяет верхний элемент новым, поэтому вместо этого вы захотите pop верхний (самый маленький) элемент и затем push вновь увиденное значение. Кроме этого, алгоритм довольно четко переводит с Python на C ++.

Answer 3

Вот естественный C ++ способ сделать это:

std::vector<Score> v;
// fill in v
std::partial_sort(v.begin(), v.begin() + 100, v.end(), std::greater<Score>());
std::sort(v.begin(), v.begin() + 100);

Это линейное число баллов.

Алгоритм, используемый std :: sort, не указан стандартом, но libstdc ++ (используемый g ++) использует «адаптивный интросорт», который по сути является быстрой сортировкой медианы-3 до определенного уровня, после чего следует по виду вставки.

Answer 4

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

Примерно так (код C #, но вы поняли):

Score[] toplist = new Score[100];
int size = 0;
foreach (Score score in hugeList) {
   int pos = size;
   while (pos > 0 && toplist[pos - 1] < score) {
      pos--;
      if (pos < 99) toplist[pos + 1] = toplist[pos];
   }
   if (size < 100) size++;
   if (pos < size) toplist[pos] = score;
}

Я протестировал его на своем компьютере (Code 2 Duo 2,54 МГц Win 7 x64), и я могу обработать 100 000 000 элементов за 369 мс.

Answer 5

Поскольку здесь важна скорость и 40 000 возможных значений рекордов полностью поддерживаются любым из современных компьютеров, я бы прибегнул к сортировке по категориям для простоты. Я предполагаю, что он будет превосходить любой из предложенных алгоритмов. Недостатком является то, что вам придется определить верхний предел для значений рекордов.

Итак, давайте предположим, что ваш максимальный рекорд 40.000:

Создайте массив из 40 000 записей. Переберите свои рекорды. Каждый раз, когда вы сталкиваетесь с рекордом x, увеличивайте массив [x] на единицу. После этого все, что вам нужно сделать, это подсчитать верхние записи в вашем массиве, пока вы не достигнете 100 подсчитанных рекордов.

Answer 6

Вы можете сделать это в Haskell следующим образом:

largest100 xs = take 100 $ sortBy (flip compare) xs

Это похоже на сортировку всех чисел в порядке убывания (бит "flip Compare" инвертирует аргументы стандартной функции сравнения) и затем возвращает первые 100 записей из списка. Но Haskell оценивается лениво, поэтому функция sortBy выполняет только достаточную сортировку, чтобы найти первые 100 чисел в списке, а затем останавливается.

Пуристы заметят, что вы также можете написать функцию как

largest100 = take 100 . sortBy (flip compare)

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

Answer 7

Алгоритм медианы медиан.

Answer 8

Я ответил на этот вопрос в ответ на вопрос об интервью в 2008 году. Я внедрил шаблонную очередь приоритетов в C # .

using System;
using System.Collections.Generic;
using System.Text;

namespace CompanyTest
{
    //  Based on pre-generics C# implementation at
    //      http://www.boyet.com/Articles/WritingapriorityqueueinC.html
    //  and wikipedia article
    //      http://en.wikipedia.org/wiki/Binary_heap
    class PriorityQueue<T>
    {
        struct Pair
        {
            T val;
            int priority;
            public Pair(T v, int p)
            {
                this.val = v;
                this.priority = p;
            }
            public T Val { get { return this.val; } }
            public int Priority { get { return this.priority; } }
        }
        #region Private members
        private System.Collections.Generic.List<Pair> array = new System.Collections.Generic.List<Pair>();
        #endregion
        #region Constructor
        public PriorityQueue()
        {
        }
        #endregion
        #region Public methods
        public void Enqueue(T val, int priority)
        {
            Pair p = new Pair(val, priority);
            array.Add(p);
            bubbleUp(array.Count - 1);
        }
        public T Dequeue()
        {
            if (array.Count <= 0)
                throw new System.InvalidOperationException("Queue is empty");
            else
            {
                Pair result = array[0];
                array[0] = array[array.Count - 1];
                array.RemoveAt(array.Count - 1);
                if (array.Count > 0)
                    trickleDown(0);
                return result.Val;
            }
        }
        #endregion
        #region Private methods
        private static int ParentOf(int index)
        {
            return (index - 1) / 2;
        }
        private static int LeftChildOf(int index)
        {
            return (index * 2) + 1;
        }
        private static bool ParentIsLowerPriority(Pair parent, Pair item)
        {
            return (parent.Priority < item.Priority);
        }
        //  Move high priority items from bottom up the heap
        private void bubbleUp(int index)
        {
            Pair item = array[index];
            int parent = ParentOf(index);
            while ((index > 0) && ParentIsLowerPriority(array[parent], item))
            {
                //  Parent is lower priority -- move it down
                array[index] = array[parent];
                index = parent;
                parent = ParentOf(index);
            }
            //  Write the item once in its correct place
            array[index] = item;
        }
        //  Push low priority items from the top of the down
        private void trickleDown(int index)
        {
            Pair item = array[index];
            int child = LeftChildOf(index);
            while (child < array.Count)
            {
                bool rightChildExists = ((child + 1) < array.Count);
                if (rightChildExists)
                {
                    bool rightChildIsHigherPriority = (array[child].Priority < array[child + 1].Priority);
                    if (rightChildIsHigherPriority)
                        child++;
                }
                //  array[child] points at higher priority sibling -- move it up
                array[index] = array[child];
                index = child;
                child = LeftChildOf(index);
            }
            //  Put the former root in its correct place
            array[index] = item;
            bubbleUp(index);
        }
        #endregion
    }
}

Answer 9

Если вам нужно только сообщить значение 100 лучших баллов (а не каких-либо связанных с ними данных), и если вы знаете, что все баллы будут в ограниченном диапазоне, например [0,100], то это простой способ сделать это с "подсчетом сортировки" ...

По сути, создайте массив, представляющий все возможные значения (например, массив размером 101, если оценки могут варьироваться от 0 до 100 включительно), и инициализируйте все элементы массива со значением 0. Затем выполните итерацию по списку. баллов, увеличивая соответствующую запись в списке достигнутых баллов. То есть, скомпилируйте количество достижений каждого балла в диапазоне. Затем, работая от конца массива до начала массива, вы можете выбрать верхнюю оценку Х. Вот некоторый псевдокод:

    let type Score be an integer ranging from 0 to 100, inclusive.
    let scores be an array of Score objects
    let scorerange be an array of integers of size 101.

    for i in [0,100]
        set scorerange[i] = 0

    for each score in scores
        set scorerange[score] = scorerange[score] + 1

    let top be the number of top scores to report
    let idx be an integer initialized to the end of scorerange (i.e. 100)

    while (top > 0) and (idx>=0):
        if scorerange[idx] > 0:
              report "There are " scorerange[idx] " scores with value " idx
              top =  top - scorerange[idx]
        idx = idx - 1;

Answer 10

Поместите данные в сбалансированную древовидную структуру (возможно, красно-черное дерево), которая выполняет сортировку на месте. Вставки должны быть O (LG N). Захватить наивысшие баллы за х тоже должно быть O (lg n).

Вы можете подрезать дерево время от времени, если в какой-то момент вам понадобится оптимизация.