Le moyen le plus rapide d'obtenir les plus grands numéros X d'une très grande liste non traitée?

Vous pouvez le faire dans HASKELLL comme ceci:

largest100 = take 100 . sortBy (flip compare)

J'ai répondu à cette question en réponse à une question d'entretien en 2008. J'ai mis en place un File d'attente prioritaire template en 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
    }
}

Voici le moyen "naturel" C ++ de faire ceci:

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

Etant donné que la vitesse est de l'essence ici, et 40 000 valeurs de hautcore possibles sont totalement maintenues par l'un des ordinateurs d'aujourd'hui, je serais recourir à Seau Seau pour la simplicité. Je suppose que cela serait surperformer l'un des algorithmes proposés jusqu'à présent. L'inconvénient est que vous devez déterminer une limite supérieure pour les valeurs de haut-agrêtes.

Donc, supposons que votre valeur maximale hautcore est 40.000:

Faites un tableau de 40.000 entrées. Boucle à travers vos valeurs de haut-agrêtes. Chaque fois que vous rencontrez des highscore X, augmentez votre réseau [x] par un. Après cela, tout ce que vous avez à faire est de compter les meilleures entrées de votre matrice jusqu'à ce que vous ayez atteint 100 hauts-types comptés.

Médiane d'algorithme de médianes.