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

Вы можете сделать это за 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 элементов: 0,29 секунды
• 1000000 элементов: 2,8 секунды
• 10000000 элементов: 25,2 секунды

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

Declare an array where you can put the 100 best scores. Loop through the huge list and check for each item if it qualifies to be inserted in the top 100. Use a simple insert sort to add an item to the top list.

Something like this (C# code, but you get the idea):

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;
}

I tested it on my computer (Code 2 Duo 2.54 MHz Win 7 x64) and I can process 100.000.000 items in 369 ms.

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

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

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

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

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

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

Place the data into a balanced Tree structure (probably Red-Black tree) that does the sorting in place. Insertions should be O(lg n). Grabbing the highest x scores should be O(lg n) as well.

You can prune the tree every once in awhile if you find you need optimizations at some point.

If you only need to report the value of top 100 scores (and not any associated data), and if you know that the scores will all be in a finite range such as [0,100], then an easy way to do it is with "counting sort"...

Basically, create an array representing all possible values (e.g. an array of size 101 if scores can range from 0 to 100 inclusive), and initialize all the elements of the array with a value of 0. Then, iterate through the list of scores, incrementing the corresponding entry in the list of achieved scores. That is, compile the number of times each score in the range has been achieved. Then, working from the end of the array to the beginning of the array, you can pick out the top X score. Here is some pseudo-code:

    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;

Я ответил на этот вопрос в ответ на вопрос интервью в 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
    }
}

При использовании Visual Studio 2010 или более поздней версии вы должны использовать ключевое слово FROM , например:

Dim days = New Dictionary(Of Integer, String) From {{0, "string"}, {1, "string2"}}

См .: http : //msdn.microsoft.com/en-us/library/dd293617 (VS.100) .aspx

Если вам нужно использовать предыдущую версию Visual Studio, и вам нужно делать это часто, вы можете просто унаследовать от Класс словаря и реализовать его самостоятельно.

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

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

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

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