Obtenez 100 numéros les plus élevés d'une liste infinie

53

Cette question d'entrevue a été posée à l'un de mes amis -

"Il y a un flux constant de nombres provenant d'une liste infinie de nombres dont vous avez besoin pour maintenir une structure de données afin de renvoyer les 100 premiers nombres les plus élevés à un moment donné. Supposons que tous les nombres sont uniquement des nombres entiers."

C'est simple, vous devez conserver une liste triée par ordre décroissant et garder une trace du numéro le plus bas de cette liste. Si le nouveau nombre obtenu est supérieur au nombre le plus bas, vous devez alors supprimer ce dernier et insérer le nouveau numéro dans la liste triée, si nécessaire.

Puis la question a été prolongée -

"Pouvez-vous vous assurer que l'ordre d'insertion doit être O (1)? Est-ce possible?"

Autant que je sache, même si vous ajoutez un nouveau numéro à la liste et que vous le triez à nouveau à l'aide de n'importe quel algorithme de tri, ce serait de préférence O (logn) pour quicksort (je pense). Alors mon ami m'a dit que ce n'était pas possible. Mais il n'était pas convaincu, il a demandé de conserver une autre structure de données plutôt qu'une liste.

J'ai pensé à un arbre binaire équilibré, mais même là, vous n'obtiendrez pas l'insertion avec l'ordre de 1. Donc, la même question que j'ai aussi maintenant. Je voulais savoir s'il existe une telle structure de données pouvant faire une insertion dans l'ordre de 1 pour le problème ci-dessus ou si ce n'est pas du tout possible.

Sachin Shanbhag
la source
19
Peut-être que c'est juste parce que je comprends mal la question, mais pourquoi avez-vous besoin de garder une liste triée ? Pourquoi ne pas simplement garder une trace du nombre le plus bas, et si un nombre supérieur à celui-ci est rencontré, supprimez le nombre le plus bas et insérez le nouveau nombre sans garder la liste triée. Cela vous donnerait O (1).
EdoDodo
36
@EdoDodo - et après cette opération, comment savoir quel est le nouveau numéro le plus bas?
Damien_The_Unbeliever
19
Triez la liste [O (100 * log (100)) = O (1)] ou effectuez une recherche linéaire à travers elle pour obtenir le minimum [O (100) = O (1)] pour obtenir le nouveau nombre le plus bas. Votre liste a une taille constante, donc toutes ces opérations sont également constantes.
Random832
6
Vous n'avez pas à garder la liste complète triée. Vous ne vous souciez pas de savoir quel est le numéro le plus élevé ou le plus élevé. Vous devez juste savoir quel est le plus bas. Ainsi, après avoir inséré un nouveau numéro, il vous suffit de parcourir les 100 numéros pour voir lequel est maintenant le plus bas. C'est du temps constant.
Tom Zych
27
L' ordre asymptotique d'une opération n'est intéressant que lorsque la taille du problème peut croître sans limite. Votre question ne dit pas très bien quelle quantité croît sans limite; on dirait que vous demandez quel est l’ordre asymptotique d’un problème dont la taille est limitée à 100; ce n'est même pas une question raisonnable à poser; quelque chose doit grandir sans limite. Si la question est "pouvez-vous le faire pour conserver le n maximum, pas le top 100, en temps O (1)?" alors la question est sensible.
Eric Lippert

Réponses:

35

Disons que k est le nombre de nombres le plus élevé que vous voulez connaître (100 dans votre exemple). Ensuite, vous pouvez ajouter un nouveau numéro dans O(k)lequel est également O(1). Parce que O(k*g) = O(g) if k is not zero and constant.

duedl0r
la source
6
O (50) est O (n), pas O (1). L'insertion dans une liste de longueur N dans O (1) heure signifie que le temps ne dépend pas de la valeur de N. Cela signifie que si 100 devient 10000, 50 ne doit PAS devenir 5000.
18
@hamstergene - mais dans le cas de cette question, Nla taille de la liste triée ou le nombre d'éléments traités à ce jour sont-ils? Si vous traitez 10 000 articles et conservez les 100 premiers articles dans une liste, ou si vous traitez 1 000 000 articles et que vous conservez les 100 premiers articles dans une liste triée, les coûts d'insertion de cette liste restent les mêmes.
Damien_The_Unbeliever
6
@hamstergene: Dans ce cas, vous avez mal compris les bases. Dans votre lien wikipedia il y a une propriété ( « par une constante multiplication »): O(k*g) = O(g) if k not zero and constant. => O(50*1) = O(1).
duedl0r
9
Je pense que duedl0r a raison. Réduisons le problème et disons que vous n'avez besoin que des valeurs minimales et maximales. Est-ce que c'est O (n) parce que le minimum et le maximum sont 2? (n = 2). Le numéro 2 fait partie de la définition du problème. Est une constante, donc il est ak dans le O (k * quelque chose) qui est équivalent à O (quelque chose)
xanatos
9
@hamstergene: de quelle fonction parlez-vous? la valeur 100 me semble plutôt constante ..
duedl0r
19

Gardez la liste non triée. Déterminer s'il faut ou non insérer un nouveau numéro prendra plus de temps, mais l' insertion sera O (1).

Emilio M Bumachar
la source
7
Je pense que cela vous permettrait d'obtenir le prix smart-aleck , si rien d'autre. * 8 ')
Mark Booth
4
@ Emilio, vous avez raison sur le plan technique - et bien sûr, c'est le meilleur type de réponse correcte…
Gareth
1
Mais vous pouvez aussi garder le plus bas de vos 100 nombres, puis décider si vous devez insérer dans O (1). Dans ce cas uniquement, vous devez rechercher le nouveau numéro le plus bas. Mais cela arrive plus rarement que de décider d'insérer ou non, ce qui se produit pour chaque nouveau numéro.
Andrei Vajna II
12

C'est facile. La taille de la liste de constante, donc le temps de tri de la liste est constant. Une opération qui s'exécute en temps constant est dite O (1). Par conséquent, le tri de la liste est O (1) pour une liste de taille fixe.

Kirk Broadhurst
la source
9

Une fois que vous avez passé 100 numéros, le coût maximum que vous aurez jamais pour le prochain numéro est le coût pour vérifier si le nombre est dans les 100 plus hauts numéros ( étiquetons ce CheckTime ) plus le coût pour le saisir dans cet ensemble et éjecter le le plus bas (appelons-le EnterTime ), qui est le temps constant (au moins pour les nombres liés), ou O (1) .

Worst = CheckTime + EnterTime

Ensuite, si la distribution des nombres est aléatoire, le coût moyen diminue à mesure que vous avez plus de chiffres. Par exemple, la chance que vous deviez entrer le 101ème nombre dans le jeu maximum est 100/101, les chances pour le 1000ème nombre seraient de 1/10 et les chances pour le nième nombre seraient de 100 / n. Ainsi, notre équation pour le coût moyen sera:

Average = CheckTime + EnterTime / n

Ainsi, alors que n approche l'infini, seul CheckTime est important:

Average = CheckTime

Si les nombres sont liés, CheckTime est constant et correspond donc à O (1) .

Si les nombres ne sont pas liés, le temps de contrôle augmentera avec plus de nombres. Théoriquement, c'est parce que si le plus petit nombre du jeu maximal devient suffisamment grand, votre temps de contrôle sera plus long, car vous devrez prendre en compte plus de bits. Cela donne l’impression que ce sera légèrement supérieur au temps constant. Cependant, vous pouvez également affirmer que la probabilité que le prochain nombre se trouve dans le groupe le plus élevé s'approche de zéro lorsque n s'approche de l'infini et que, par conséquent, la chance que vous ayez besoin de considérer plus de bits s'approche également de 0, ce qui serait un argument pour O (1). temps.

Je ne suis pas positif, mais mon instinct dit qu'il est l' heure O (log (log (n))) . En effet, la probabilité que le nombre le plus bas augmente est logarithmique et que le nombre de bits à prendre en compte pour chaque vérification est également logarithmique. Je suis intéressé par d'autres peuples, parce que je ne suis pas vraiment sûr ...

Briguy37
la source
Sauf que la liste est arbitraire, que se passe-t-il si c'est une liste de nombres toujours croissants?
dan_waterworth
@dan_waterworth: Si la liste infinie est aléatoire et qu'elle augmente sans cesse (les chances étant de 1 / ∞!), cela correspondrait au pire scénario CheckTime + EnterTimepour chaque nombre. Cela n'a de sens que si le nombre est sans bornes, et ainsi , CheckTimeet EnterTimepermettra à la fois augmentation au moins logarithmiquement en raison de l'augmentation de la taille des chiffres.
Briguy37
1
Les chiffres ne sont pas aléatoires, ils sont arbitraires. Cela n'a aucun sens de parler de probabilités.
dan_waterworth
@ dan_waterworth: Vous avez dit deux fois maintenant que les chiffres sont arbitraires. D'où tirez-vous cela? De plus, je pense que vous pouvez toujours appliquer des statistiques à des nombres arbitraires commençant par le cas aléatoire et améliorer leur précision à mesure que vous en savez plus sur l'arbitre. Par exemple, si vous étiez l'arbitre, il semblerait qu'il y aurait une plus grande chance de choisir des nombres toujours croissants que si, par exemple, j'étais l'arbitre;)
Briguy37
7

celui-ci est facile si vous connaissez les arbres binaires du tas . Les tas binaires supportent l'insertion en temps constant moyen, O (1). Et vous donner un accès facile aux x premiers éléments.

monstre à cliquet
la source
Pourquoi stocker les éléments dont vous n'avez pas besoin? (les valeurs trop basses) On dirait qu'un algorithme personnalisé est plus approprié. Ne pas dire que vous ne pouvez pas "ne pas ajouter" les valeurs quand elles ne sont pas supérieures aux plus basses.
Steven Jeuris
Je ne sais pas, mon intuition me dit qu'un tas (d'une certaine saveur) pourrait très bien réussir cela. Cela ne veut pas dire qu'il devrait garder tous les éléments pour le faire. Je n'ai pas fait de recherche mais ça "se sent bien" (TM).
Rig
3
Un segment de mémoire peut être modifié pour rejeter tout ce qui se situe en dessous d'un certain niveau (pour les segments binaires et k = 100, m serait égal à 7, car le nombre de nœuds = 2 ^ m-1). Cela le ralentirait, mais il serait toujours amorti en temps constant.
Plutor
3
Si vous avez utilisé un min-tas binaire (car alors le haut est le minimum que vous vérifiez tout le temps) et que vous trouviez un nouveau nombre> min, vous devez alors supprimer l'élément du haut avant de pouvoir en insérer un nouveau. . Supprimer l’élément top (min) sera O (logN) car vous devez traverser tous les niveaux de l’arbre une fois. Il n’est donc techniquement vrai que les insertions sont en moyenne O (1) car en pratique, c’est toujours O (logN) chaque fois que vous trouvez un nombre> min.
Scott Whitlock
1
@Plutor, vous supposez certaines garanties que les tas binaires ne vous donnent pas. En le visualisant sous forme d'arborescence binaire, il se peut que chaque élément de la branche de gauche soit plus petit que tout élément de la branche de droite, mais vous supposez que les plus petits éléments sont proches de la racine.
Peter Taylor
6

Si par la question l'enquêteur voulait vraiment demander «pouvons-nous nous assurer que chaque numéro entrant est traité en temps constant», alors, comme beaucoup l'ont déjà souligné (voir la réponse de @ duedl0r, par exemple), la solution de votre ami est déjà O (1), et ce serait le cas même s'il avait utilisé une liste non triée, un tri à bulles ou autre chose. Dans ce cas, la question n'a pas beaucoup de sens, à moins que ce ne soit une question délicate ou que vous ne vous en souveniez pas.

Je suppose que la question de l'intervieweur était significative, à savoir qu'il ne demandait pas comment transformer quelque chose en O (1), ce qui est déjà très évident.

Parce que l'interrogation de la complexité de l'algorithme n'a de sens que lorsque la taille de l'entrée augmente indéfiniment et que la seule entrée susceptible de croître ici est 100: la taille de la liste; Je suppose que la vraie question était «pouvons-nous nous assurer que nous obtenons O (1) de temps par numéro (et non pas O (N) comme dans la solution de votre ami), est-ce possible?».

La première chose qui me vient à l’esprit est la sorte de comptage, qui achètera une complexité de O (1) temps par numéro pour le problème Top-N au prix d’utilisation de l’espace O (m), où m est la longueur de la plage des nombres entrants. . Alors oui, c'est possible.

hamstergene
la source
4

Utilisez une file d'attente de priorité minimale implémentée avec un segment de Fibonacci , dont le temps d'insertion est constant:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)
Gabe Moothart
la source
4
« Opérations de suppression et le travail minimum de suppression dans le O(log n)temps amorti » , donc cela entraînerait encore O(log k)kest la quantité d'articles à stocker.
Steven Jeuris
1
Ce n'est pas différent de la réponse d' Emilio qui a été surnommée le "smart-aleck award" puisque la suppression min opère dans O (log n) (selon Wikipedia).
Nicole
La réponse de @Renesis Emilio serait O (k) pour trouver le minimum, la mienne est O (log k)
Gabe Moothart
1
@Gabe Assez, je veux dire en principe. En d’autres termes, si vous ne prenez pas 100 comme une constante, cette réponse n’est pas non plus du temps continu.
Nicole
@Renesis J'ai supprimé l'énoncé (incorrect) de la réponse.
Gabe Moothart
2

La tâche est clairement de trouver un algorithme qui est O (1) de la longueur N de la liste de nombres requise. Ainsi, que vous ayez besoin des 100 premiers numéros ou des 10 000 premiers numéros, le temps d’insertion doit être O (1).

L'astuce ici est que bien que cette exigence O (1) soit mentionnée pour l'insertion de liste, la question ne disait rien sur l'ordre du temps de recherche dans l'espace entier, mais il s'avère que cela peut être fait O (1) ainsi que. La solution est alors la suivante:

  1. Organisez une table de hachage avec des nombres pour les clés et des paires de pointeurs de liste liés pour les valeurs. Chaque paire de pointeurs est le début et la fin d'une séquence de liste chaînée. Ce sera normalement juste un élément puis le suivant. Chaque élément de la liste liée va à côté de l'élément avec le prochain numéro le plus élevé. La liste chaînée contient donc la séquence triée des nombres requis. Conservez un enregistrement du nombre le plus bas.

  2. Prendre un nouveau nombre x du flux aléatoire.

  3. Est-il supérieur au dernier numéro le plus bas enregistré? Oui => Étape 4, Non => Étape 2

  4. Appuyez sur la table de hachage avec le nombre que vous venez de prendre. Y a-t-il une entrée? Oui => Étape 5. Non => Prenez un nouveau numéro x-1 et répétez cette étape (il s'agit d'une recherche linéaire descendante simple, tenez compte de moi, cela peut être amélioré et je vais expliquer comment)

  5. Avec l'élément de liste qui vient d'être obtenu à partir de la table de hachage, insérez le nouveau numéro juste après l'élément dans la liste liée (et mettez à jour le hachage)

  6. Prenez le nombre le plus bas que j'ai enregistré (et retirez-le de la liste de hachage).

  7. Appuyez sur la table de hachage avec le nombre que vous venez de prendre. Y a-t-il une entrée? Oui => Étape 8. Non => Prenez un nouveau nombre l + 1 et répétez cette étape (il s'agit d'une recherche linéaire ascendante simple)

  8. Avec un résultat positif, le nombre devient le nouveau nombre le plus bas. Aller à l'étape 2

Pour permettre les doublons, le hachage doit en fait conserver le début et la fin de la séquence d'éléments dupliqués de la liste chaînée. Ajouter ou supprimer un élément à une clé donnée augmente ou diminue donc la plage indiquée.

L'insert ici est O (1). Les recherches mentionnées sont, je suppose, quelque chose comme: O (différence moyenne entre les nombres). La différence moyenne augmente avec la taille de l'espace de nombre, mais diminue avec la longueur requise de la liste de nombres.

La stratégie de recherche linéaire est donc assez faible si l’espace numérique est grand (par exemple, pour un type int de 4 octets, 0 à 2 ^ 32-1) et N = 100. Pour contourner ce problème de performances, vous pouvez conserver des ensembles de haltables parallèles, dans lesquels les nombres sont arrondis à des magnitudes supérieures (par exemple, 1, 10, 100, 1000) pour obtenir les clés appropriées. De cette manière, vous pouvez passer à la vitesse supérieure pour effectuer les recherches requises plus rapidement. La performance devient alors un O (log numberrange), je pense, qui est constant, c’est-à-dire O (1) également.

Pour clarifier cela, imaginez que vous avez le numéro 197 à portée de main. Vous frappez la table de hachage des 10, avec «190», elle est arrondie à la dizaine la plus proche. N'importe quoi? Donc, vous descendez dans 10 secondes jusqu'à atteindre 120, puis vous pouvez commencer à 129 dans la table de hachage 1s, puis essayez 128, 127 jusqu'à ce que vous atteigniez quelque chose. Vous avez maintenant trouvé où dans la liste liée insérer le nombre 197. Tout en l'insérant, vous devez également mettre à jour la table de hachage 1s avec l'entrée 197, la table de hachage 10s avec le nombre 190, 100 avec 100, etc. 10 fois le journal de la plage de numéros.

Je me suis peut-être trompé dans certains détails, mais comme il s'agit de l'échange de programmeurs et du contexte d'interviews, j'espère que ce qui précède constitue une réponse suffisamment convaincante à cette situation.

EDIT J'ai ajouté quelques détails supplémentaires ici pour expliquer le schéma de hachage parallèle et expliquer en quoi les mauvaises recherches linéaires mentionnées précédemment peuvent être remplacées par une recherche O (1). J'ai également compris qu'il n'était bien sûr pas nécessaire de rechercher le prochain nombre le plus bas, car vous pouvez y accéder directement en cherchant dans la table de hachage avec le nombre le plus bas et en passant à l'élément suivant.

Benoît
la source
1
La recherche doit faire partie de la fonction d'insertion - ce ne sont pas des fonctions indépendantes. Puisque votre recherche est O (n), votre fonction d'insertion est également O (n).
Kirk Broadhurst
Non. En utilisant la stratégie que j'ai décrite, où davantage de hashtables sont utilisés pour parcourir l'espace des nombres plus rapidement, c'est O (1). S'il vous plaît lire ma réponse à nouveau.
Benoît
1
@ Benedict, votre réponse indique très clairement qu'il existe des recherches linéaires aux étapes 4 et 7. Les recherches linéaires ne sont pas O (1).
Peter Taylor
Oui, c'est le cas, mais je traiterai de cela plus tard. Pourriez-vous lire le reste s'il vous plaît? Si nécessaire, je modifierai ma réponse pour la rendre parfaitement claire.
Benoît
@ Benedict Vous avez raison - en excluant la recherche, votre réponse est O (1). Malheureusement, cette solution ne fonctionnera pas sans la recherche.
Kirk Broadhurst
1

Pouvons-nous supposer que les nombres sont d'un type de données fixe, tel que Integer? Si tel est le cas, tenez une liste de chaque nombre ajouté. C'est une opération O (1).

  1. Déclarez un tableau avec autant d'éléments qu'il y a de nombres possibles:
  2. Lisez chaque numéro au fur et à mesure de sa diffusion.
  3. Compter le nombre. Ignorez-le si ce nombre a déjà été calculé 100 fois, car vous n'en aurez jamais besoin. Cela empêche les débordements de le comptabiliser un nombre infini de fois.
  4. Répétez à partir de l'étape 2.

Code VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Lorsque vous retournez la liste, vous pouvez prendre aussi longtemps que vous le souhaitez. Il suffit de parcourir la fin de la liste et de créer une nouvelle liste des 100 plus hautes valeurs enregistrées. C'est une opération O (n), mais c'est irrelivant.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Edit: En fait, peu importe qu’il s’agisse d’un type de données fixe. Étant donné qu’il n’ya pas de limite imposée à la consommation de mémoire (ou de disque dur), vous pouvez le faire pour n’importe quelle plage d’entiers positifs.

Hand-E-Food
la source
1

Une centaine de nombres sont facilement stockés dans un tableau de taille 100. Toute arborescence, liste ou ensemble est excessif, compte tenu de la tâche à accomplir.

Si le nombre entrant est supérieur au plus petit (= dernier) du tableau, exécutez toutes les entrées. Une fois que vous avez trouvé le premier plus petit que votre nouveau numéro (vous pouvez utiliser des recherches sophistiquées pour le faire), parcourez le reste du tableau en poussant chaque entrée "vers le bas" de un.

Comme vous gardez la liste triée depuis le début, vous n’avez pas besoin de lancer un algorithme de tri. C'est O (1).

Jörg Z.
la source
0

Vous pouvez utiliser un binaire Max-Heap. Vous devez garder la trace d'un pointeur sur le nœud minimum (qui peut être inconnu / null).

Vous commencez par insérer les 100 premiers chiffres dans le tas. Le max sera au top. Après cela, vous garderez toujours 100 numéros.

Ensuite, lorsque vous recevez un nouveau numéro:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Malheureusement, findMinimumNodec’est O (n), et vous n’engagez ce coût qu’une fois par insertion (mais pas pendant l’insertion :). Retirer le nœud minimum et insérer le nouveau nœud sont, en moyenne, O (1) car ils tendent vers le bas du tas.

En allant dans l'autre sens avec un min-tas binaire, le min est en haut, ce qui est excellent pour trouver le min à des fins de comparaison, mais c'est nul quand vous devez remplacer le minimum par un nouveau nombre qui est> min. En effet, vous devez supprimer le nœud min (toujours O (logN)), puis insérer le nouveau nœud (moyenne O (1)). Donc, vous avez toujours O (logN) qui est meilleur que Max-Heap, mais pas O (1).

Bien sûr, si N est constant, alors vous avez toujours O (1). :)

Scott Whitlock
la source