Un de mes amis a été invité à poser une question, Récupération du maximum des 100 meilleurs chiffres parmi cent millions de chiffres, lors d’un récent entretien d'embauche. Avez-vous une idée pour trouver un moyen efficace de le résoudre?
Cordialement!
Les exécuter à travers un min-tas de taille 100: pour chaque entrée nombre k, de remplacer l'actuel min m avec max(k, m). Ensuite, le tas détient 100 plus grandes entrées.
Un moteur de recherche comme Lucene pouvez utiliser cette méthode, avec des raffinements, de choisir les plus pertinentes pour la recherche de réponses.
Edit: je ne l'interview, j'ai eu les détails trompe pour la deuxième fois (après l'avoir fait avant, dans la production). Voici le code pour le vérifier; c'est presque la même que Python standard heapq.nlargest():
import heapq
def funnel(n, numbers):
if n == 0: return []
heap = numbers[:n]
heapq.heapify(heap)
for k in numbers[n:]:
if heap[0] < k:
heapq.heapreplace(heap, k)
return heap
>>> funnel(4, [3,1,4,1,5,9,2,6,5,3,5,8])
[5, 8, 6, 9]
Ok, ici, c'est vraiment une réponse stupide, mais il est valide:
Raisonnement:
C'est un ok de solution pour une sorte d'opération d'une fois. Il serait sucer l'exécutant x fois par seconde, ou quelque chose. Mais ensuite, nous avons besoin de plus de contexte - comme mclientk aussi a eu avec son simple instruction SQL - en supposant que 100 millions de numbersdo pas exister dans la mémoire est un moyen réaliste de la question, parce que... ils peuvent venir à partir d'une base de données et la plupart des fois, quand on parle de business, les chiffres pertinents.
En tant que telle, la question est vraiment difficile de répondre - efficacité doit d'abord être défini.
Si les données sont déjà dans un tableau que vous pouvez modifier, vous pouvez utiliser une variante de Hoare de sélection de l'algorithme, qui est (à son tour) une variante de Quicksort.
L'idée de base est assez simple. Dans Quicksort, la partition de la matrice en deux morceaux, l'un des éléments plus grands que le pivot, et de l'autre des éléments plus petits que le pivot. Ensuite, vous récursive trier chaque partition.
Dans la sélection de l'algorithme, vous ne l'étape de partitionnement exactement comme avant -- mais plutôt de manière récursive tri les deux partitions, vous regardez la partition qui contient les éléments que vous voulez, et de manière récursive sélectionner UNIQUEMENT dans la partition. E. g., en supposant que votre 100 millions d'articles partition de près de moitié, la première de plusieurs itérations vous allez seulement à la partie supérieure de la partition.
Finalement, vous êtes susceptible d'atteindre un point où la partie que vous voulez "ponts" deux partitions -- par exemple, vous avez une partition de ~150 numéros, et quand vous la partition que vous vous retrouvez avec deux morceaux de ~75 la pièce. À ce stade, un seul petit détail change: au lieu de rejeter une partition et de la poursuite des travaux que l'autre, vous acceptez la partie supérieure de la partition de 75 articles, et puis continuer à chercher pour le top 25 dans le bas de la partition.
Si vous faisiez cela en C++, vous pouvez le faire avec std::nth_element (qui sera normalement mis en œuvre environ comme décrit ci-dessus). En moyenne, ce qui a linéaire de la complexité, qui je crois est à peu près aussi bon que ce que vous pouvez espérer (en l'absence d'une affection préexistante de l'ordre, je ne vois pas de moyen de trouver les N premiers éléments sans les regarder, tous les éléments).
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
