Écrire un programme pour trouver les 100 plus grands nombres d'un tableau de 1 milliards de chiffres

Vous pouvez garder une file d'attente prioritaire de les 100 plus grand nombre, l'itération à travers les milliards de chiffres, chaque fois que vous rencontrez un nombre plus grand que le plus petit numéro dans la file d'attente (la tête de la file d'attente), de supprimer la tête de la file d'attente et ajouter le nouveau numéro de la file d'attente.

EDIT:
en tant que Dev a noté, avec une file d'attente de priorité mis en œuvre par un segment de mémoire, la complexité de l'insertion pour la file d'attente est O(logN)

Dans le pire des cas, vous obtenez billionlog2(100) ce qui est mieux que billionlog2(billion)

En général, si vous avez besoin le plus grand K nombres à partir d'un ensemble de N nombres, la complexité est O(NlogK) plutôt que O(NlogN), cela peut être très important lorsque K est très faible en comparaison des N.

EDIT2:

Le temps de cet algorithme est assez intéressant, car à chaque itération une insertion peut ou peut ne pas se produire. La probabilité de la i-ième nombre pour être inséré dans la file d'attente est la probabilité d'une variable aléatoire est supérieure à au moins i-K variables aléatoires à partir de la même distribution (les k premiers nombres sont automatiquement ajoutés à la file d'attente). Nous pouvons utiliser les statistiques d'ordre (voir lien) pour calculer cette probabilité. Par exemple, supposons les nombres ont été choisis au hasard uniformément de {0, 1}, la valeur attendue de (i-K), le nombre (de je numéros) est (i-k)/i, et la probabilité d'une variable aléatoire étant plus grande que cette valeur est 1-[(i-k)/i] = k/i.

Ainsi, le nombre d'insertions est:

Et de la durée d'exécution peut être exprimé comme:

(k temps de génération de la file d'attente avec le premier k éléments, puis n-k comparaisons, et le nombre d'insertions, comme décrit ci-dessus, chacun prend une moyenne log(k)/2 temps)

Noter que lorsque N est très grand en comparaison des K, cette expression est beaucoup plus proche de n plutôt que NlogK. C'est un peu intuitif, comme dans le cas de la question, même après 10000 itérations (ce qui est très faible comparer à un milliard de dollars), les chances d'un certain nombre pour être inséré dans la file d'attente est très faible.

Vous pouvez effectuer une itération sur les numéros qui prend O(n)

Chaque fois que vous trouvez une valeur plus grande que le minimum actuel, ajouter la nouvelle valeur à une circulaire de la file d'attente à la taille 100.

Le min de file d'attente circulaire est votre nouvelle valeur de comparaison. Maintenir sur l'ajout de la file d'attente. Si complet, extraire le minimum de la file d'attente.

Ma réaction immédiate pour ce qui serait d'utiliser un segment, mais il y a moyen d'utiliser QuickSelect sans garder toutes les valeurs d'entrée à portée de main à tout moment.

Créer un tableau de taille 200 et de le remplir avec les 200 premières valeurs d'entrée. Exécuter QuickSelect et jetez le bas 100, vous laissant avec 100 places de parking libres. Lire dans les 100 prochaines valeurs d'entrée et exécuter QuickSelect de nouveau. Continuer jusqu'à ce que vous avez exécuté si l'ensemble de l'entrée en lots de 100.

À la fin vous avez le top 100 des valeurs. Pour N valeurs que vous avez exécuté QuickSelect à peu près N/100 fois. Chaque Quickselect coût d'environ 200 fois une constante, de sorte que le coût total est 2N fois une constante. Cela ressemble linéaire en la taille de l'entrée, pour moi, quelle que soit la taille de paramètre que je suis brancher à 100 dans cette explication.

Bien que les autres quickselect solution a été downvoted, le fait demeure que quickselect trouverez la solution plus rapide que l'utilisation d'une file d'attente de taille 100. Quickselect a prévu un temps de course de 2n + o(n), en termes de comparaisons. Très simplement la mise en œuvre serait

array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
  if(array[i]>r)
     add array[i] to result

Cela va prendre 3n + o(n) comparaisons en moyenne. En outre, il peut être plus efficace en utilisant le fait que quickselect va laisser la plus grande de 100 articles dans la matrice de dans la de 100 la droite-la plupart des endroits. Donc, en fait, le temps de fonctionnement peut être amélioré à 2n+o(n).

Il y a le problème que cela est prévu, la durée, et pas le pire des cas, mais en utilisant un décent de pivot de la stratégie de sélection (par exemple, choisir de 21 éléments au hasard, et choisir la médiane de ces 21 comme pivot), puis le nombre de comparaisons peuvent être garanties avec une forte probabilité d'être au plus (2+c)n pour un arbitrairement petite constante c.

En effet, en utilisant un échantillonnage optimisé stratégie (par exemple, l'échantillon sqrt(n) éléments au hasard, et choisir le 99e percentile), le temps d'exécution peut être obtenu vers le bas (1+c)n + o(n) pour arbitrairement petite c (en supposant que K, le nombre d'éléments à sélectionner o(n)).

Sur l'autre main, à l'aide d'une file d'attente de taille 100 exigera O(log(100)n) comparaisons, et le logarithme de base 2 de 100 est approximativement égale à 6,6.

Si nous pensons à ce problème dans les plus abstraits sens de choisir le plus grand K éléments d'un tableau de taille N, où K=o(N) mais les deux K et N va à l'infini, alors le temps d'exécution de la quickselect version sera en O(N) et la file d'attente de la version O(N log K), donc dans ce sens quickselect est aussi asymptotiquement supérieur.

Dans les commentaires, il a été mentionné que la file d'attente de solution sera exécuté dans le délai prévu N + K log N aléatoires d'entrée. Bien sûr, le hasard d'entrée hypothèse n'est jamais valide, à moins que la question des états explicitement. La file d'attente de solution pourrait être fait pour parcourir le tableau dans un ordre aléatoire, mais cela devra assumer le coût supplémentaire de N appels à un générateur de nombre aléatoire comme permutant l'ensemble de l'entrée de tableau ou d'autre allouer un nouveau tableau de longueur N contenant au hasard des indices.

Si le problème n'est pas de vous permettre de déplacer les éléments dans le tableau d'origine, et le coût de l'allocation de mémoire est élevée, afin de dupliquer le tableau n'est pas une option, c'est une question différente. Mais strictement en termes de temps d'exécution, c'est la meilleure solution.

Deux options:

(1) Tas (priorityQueue)

Maintenir un min-tas avec une taille de 100. Parcourir le tableau. Une fois que l'élément est plus petit que le premier élément dans le tas, il faut le remplacer.

InSERT ELEMENT INTO HEAP: O（log100）
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)

(2) Carte-réduction de modèle.

Ceci est très similaire à word count exemple dans hadoop.
La carte de l'emploi: compter chaque élément de la fréquence ou de temps est apparu.
Réduire: Obtenir le meilleur K de l'élément.

Habituellement, je donnerais le recruteur deux réponses. Leur donner ce qu'ils veulent. Bien sûr, la carte de réduire le codage serait de main-certains parce que vous devez connaître tous les paramètres exacts. Pas de mal à le pratiquer.
Bonne Chance.

Inspiré par @ron de guichets de la réponse, voici un barebones programme C de faire ce que vous voulez.

#include <stdlib.h>
#include <stdio.h>

#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100

int 
compare_function(const void *first, const void *second)
{
    int a = *((int *) first);
    int b = *((int *) second);
    if (a > b){
        return 1;
    }
    if (a < b){
        return -1;
    }
    return 0;
}

int 
main(int argc, char ** argv)
{
    if(argc != 2){
        printf("please supply a path to a binary file containing 1000000000"
               "integers of this machine's wordlength and endianness\n");
        exit(1);
    }
    FILE * f = fopen(argv[1], "r");
    if(!f){
        exit(1);
    }
    int top100[N_TOP_NUMBERS] = {0};
    int sorts = 0;
    for (int i = 0; i < TOTAL_NUMBERS; i++){
        int number;
        int ok;
        ok = fread(&number, sizeof(int), 1, f);
        if(!ok){
            printf("not enough numbers!\n");
            break;
        }
        if(number > top100[0]){
            sorts++;
            top100[0] = number;
            qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
        }

    }
    printf("%d sorts made\n"
    "the top 100 integers in %s are:\n",
    sorts, argv[1] );
    for (int i = 0; i < N_TOP_NUMBERS; i++){
        printf("%d\n", top100[i]);
    }
    fclose(f);
    exit(0);
}

Sur ma machine (core i3 avec une rapide SSD), il prend 25 secondes, et 1724 sortes.
J'ai généré un fichier binaire avec dd if=/dev/urandom/count=1000000000 bs=1 pour cette course.

Évidemment, il y a des problèmes de performances avec la lecture de seulement 4 octets à la fois - à partir du disque, mais c'est pour l'exemple du saké. Sur le côté positif, très peu de mémoire est nécessaire.

 Although in this question we should search for top 100 numbers, I will 
 generalize things and write x. Still, I will treat x as constant value.

Algorithme Plus x des éléments de n:

J'appelle la valeur de retour LISTE. C'est un ensemble de x éléments (à mon avis, que devrait être liée liste)

• X premiers éléments sont prises à partir de la piscine ", comme ils viennent" et classés dans la LISTE (ce qui est fait en temps constant puisque x est considérée comme constante O( x log(x) ) temps)
• Pour chaque élément qui vient ensuite, nous vérifions si il est plus grand que le plus petit élément dans la LISTE et si nous avons de la pop la plus petite et insérer l'élément courant de la LISTE. Depuis que est liste ordonnée de chaque élément doit trouver sa place en temps logarithmique (binaire de recherche) et depuis c'est la liste ordonnée d'insertion n'est pas un problème. Chaque étape est également fait en temps constant ( O(log(x) ) de temps ).

Alors, quel est le pire scénario?

x log(x) + (n-x)(log(x)+1) = nlog(x) + n - x

C'est donc O(n) fois pour le pire des cas. Le +1 est de vérifier si le nombre est plus grand que le plus petit dans la LISTE. Le temps prévu pour la moyenne des cas dépendra de mathématique de la distribution de ces n éléments.

Améliorations possibles

Cet algorithme peut être légèrement améliorée pour les pires scénarios, mais à mon humble avis (je ne peux pas prouver cette affirmation) que va se dégrader comportement moyen. Comportement asymptotique sera le même.

Amélioration de cet algorithme que nous n'allons pas vérifier si un élément est plus grand que le plus petit. Pour chaque élément, nous allons essayer de l'insérer et si elle est plus petite que la plus petite que nous allons en faire abstraction. Bien que cela semble absurde si l'on considère seulement le pire des cas on aura

x log(x) + (n-x)log(x) = nlog(x)

opérations.

Pour ce cas d'utilisation je ne vois pas d'autres améliorations. Pourtant, vous devez vous demander que faire si j'ai à le faire plus que log(n) fois et pour différents x-es? Évidemment, nous permettrait de trier ce tableau en O(n log(n)) et prendre notre x de l'élément chaque fois que nous en avons besoin.

La solution la plus simple serait d'utiliser une file d'attente de priorité, en ajoutant les 100 premiers numéros de la file d'attente et de maintenir le plus petit numéro dans la file d'attente, puis une itération à travers les milliards d'autres numéros, et à chaque fois que nous en trouver un qui est plus grand que le plus grand nombre dans la file d'attente de priorité, nous avons supprimer le plus petit nombre, ajouter le nouveau numéro, et encore conserver la trace du plus petit numéro dans la file d'attente.

Si les numéros ont été dans un ordre aléatoire, ce beau parce que nous parcourir un milliard de nombres aléatoires, il est très rare que le prochain numéro est parmi les 100 plus importantes à ce jour. Mais le nombre ne peut pas être le hasard. Si le tableau est déjà trié dans l'ordre croissant puis nous toujours insérer un élément à la file d'attente de priorité.

Nous choisissons donc dire 100 000 aléatoire numéros à partir du tableau en premier. Pour éviter d'accès aléatoire qui peut être lente, nous ajoutons dire 400 groupes aléatoires de 250 numéros consécutifs. Avec que la sélection aléatoire, nous pouvons être tout à fait sûr que très peu de numéros restants sont dans le top cent, de sorte que le temps d'exécution sera très proche de celui d'une simple boucle de comparaison d'un milliard de dollars certaine valeur maximale.

J'ai rédigé une solution simple en Python dans le cas où quelqu'un est intéressé. Il utilise le bisect module et un retour temporaire de la liste qu'il garde triés. Ceci est similaire à une file d'attente de priorité de mise en œuvre.

import bisect

def kLargest(A, k):
    '''returns list of k largest integers in A'''
    ret = []
    for i, a in enumerate(A):
        # For first k elements, simply construct sorted temp list
        # It is treated similarly to a priority queue
        if i < k:
            bisect.insort(ret, a) # properly inserts a into sorted list ret
        # Iterate over rest of array
        # Replace and update return array when more optimal element is found
        else:
            if a > ret[0]:
                del ret[0] # pop min element off queue
                bisect.insort(ret, a) # properly inserts a into sorted list ret
    return ret

Utilisation avec 100 000 000 d'éléments et les pires cas, l'entrée qui est une liste triée:

>>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
 99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
 99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
 99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
 99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
 99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
 99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
 99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
 99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
 99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
 99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
 99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
 99999996, 99999997, 99999998, 99999999]

Il a fallu environ 40 secondes pour calculer ce pour 100 000 000 d'éléments, donc je suis peur de le faire pour 1 milliard de dollars. Pour être juste bien, j'ai été nourrir le pire des cas, l'entrée (ironiquement, un tableau est déjà trié).

Time ~ O(100 * N)
Space ~ O(100 + N)

1. Créer une liste vide de 100 logement vide

2. Pour chaque nombre dans la liste:

   • Si le nombre est plus petit que le premier, passez

   • Sinon le remplacer avec ce numéro

   • Ensuite, poussez le nombre adjacentes swap; jusqu'à ce qu'il est plus petit que le prochain

3. Retour la liste

---

Remarque: si le log(input-list.size) + c < 100, alors la meilleure façon est de trier les entrées-liste, puis divisés en premier 100 articles.

Un autre algorithme O(n) -

L'algorithme recherche les 100 plus par élimination

pensez à tous les millions de numéros dans leur représentation binaire. Commencer à partir de l'octet le plus significatif. Si le bit de poids fort est à 1 peut être fait par une opération booléenne de multiplication avec un nombre approprié. Si il y a plus de 100 1 dans ces millions d'éliminer les autres chiffres avec des zéros. Maintenant le reste des numéros de procéder à la prochaine most significant bit. tenir le compte du nombre de numéros restants après l'élimination et continuer tant que ce nombre est plus grand que 100.

La principale opération booléenne peut être un rapprochement effectué sur les Gpu

Vous pouvez le faire dans O(n) temps. Juste parcourir la liste et de garder trace des 100 plus grand nombre vous avez vu à un moment donné et la valeur minimale de ce groupe. Lorsque vous trouvez un nouveau numéro plus grand que le plus petit de vos dix, puis le remplacer et mettre à jour votre nouvelle valeur min de l'100 (cela peut prendre un temps constant de 100 à déterminer ce à chaque fois que vous faites, mais cela n'affecte pas l'analyse globale).

1. Utilisation nième élément pour obtenir le 100 ième élément de O(n)
2. De réitérer la deuxième fois, mais une seule fois et de sortie de chaque élément qui est plus grand que cet élément spécifique.

Veuillez noter esp. la deuxième étape pourrait être facile à calculer en parallèle! Et il sera également efficace lorsque vous avez besoin d'un million de plus grands éléments.

j'ai fait mon propre code,vous ne savez pas si sa ce que "l'enquêteur" il est à la recherche

private static final int MAX=100;
 PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
        queue.add(array[0]);
        for (int i=1;i<array.length;i++)
        {

            if(queue.peek()<array[i])
            {
                if(queue.size() >=MAX)
                {
                    queue.poll();
                }
                queue.add(array[i]);

            }

        }

Prendre d'abord les éléments de 1000 et ajoutez-les dans un tas max. Maintenant, prenez le premier maxi de 100 éléments et de les stocker quelque part. Choisissez maintenant à côté de 900 éléments du dossier et les ajouter dans le tas avec la dernière 100 plus élevé de l'élément.

Continuez à répéter ce processus de la cueillette jusqu'à 100 éléments dans le tas et l'ajout de 900 éléments du dossier.

Le choix final de 100 éléments vont nous donner le maximum de 100 éléments d'un milliard de dollars de chiffres.

Je sais que cela pourrait se faire enterrer, mais voici mon idée pour une variation sur un radix MSD.

pseudo-code:

//billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];

for number in billion
    putInTop100Array(number)

function putInTop100Array(number){
    //basically if we got past all the digits successfully
    if(number == null)
        return true;
    msdIdx = getMsdIdx(number);
    msd = getMsd(number);
    //check if the idx above where we are is already full
    if(mynums[msdIdx][msd+1] > 99) {
        return false;
    } else if(putInTop100Array(removeMSD(number)){
        mynums[msdIdx][msd]++;
        //we've found 100 digits here, no need to keep looking below where we are
        if(mynums[msdIdx][msd] > 99){
           for(int i = 0; i < mds; i++){
              //making it 101 just so we can tell the difference
              //between numbers where we actually found 101, and 
              //where we just set it
              mynums[msdIdx][i] = 101;
           }
        }
        return true;
    }
    return false;
}

La fonction getMsdIdx(int num) serait de retour à l'index des chiffres plus importantes (non-nulle). La fonction getMsd(int num) aurait le plus de chiffre significatif. Le d'une fonction removeMSD(int num) permettrait de supprimer les plus importants chiffres d'un nombre et renvoie le nombre (ou de retourner la valeur null si il n'y avait rien à gauche, après le retrait de la plupart chiffre significatif).

Une fois cela fait, tout ce qui est à gauche, traverse mynums de saisir le top 100 des chiffres. Ce serait quelque chose comme:

int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
    int timesAdded = 0;
    for(int j = 16; j >=0 && timesAdded < 100; j--){
        for(int k = mynums[i][j]; k > 0; k--){
            nums[idx] += j;
            timesAdded++;
            idx++;
        }
    }
}

Je note que, bien que le ci-dessus ressemble, il est grand temps de la complexité, il va vraiment être autour de O(7*100).

Une rapide explication de ce que c'est d'essayer de faire:
Essentiellement de ce système est d'essayer d'utiliser tous les chiffres dans un 2d-tableau basé sur l'indice du chiffre dans le nombre, et le chiffre de la valeur. Il les utilise comme index de garder une trace de la façon dont de nombreux numéros de cette valeur ont été insérés dans le tableau. Lorsque 100 a été atteint, il ferme toutes les "branches".

Le temps de cet algorithme est quelque chose comme O(billion*log(16)*7)+O(100). Je peux me tromper à ce sujet. C'est très probablement ce qui nécessite une mise au point comme elle est un peu complexe et j'ai juste écrit sur le haut de ma tête.

EDIT: Downvotes sans explication ne sont pas utiles. Si vous pensez que cette réponse est incorrecte, veuillez laisser un commentaire pourquoi. Assez sûr que StackOverflow vous dit même à le faire lorsque vous downvote.

Récemment que j'ai adapté une théorie que tous les problèmes dans le monde pourrait être résolu en O(1). Et même celui-ci. Il n'était pas clair à partir de la question de savoir quelle est la gamme de nombres. Si les chiffres sont il varie de 1 à 10, puis probablement le top 100 des plus grands nombres de groupe de 10. La chance que le nombre le plus élevé sera pris sur les 1 milliards de chiffres lorsque le plus grand nombre est très faible, à comparer à 1 milliard sont très grands. Je voudrais donc donner cela comme une réponse dans cette interview.