Trouver l'élément qui se produit le plus dans un très gros fichier

J'ai entendu cette question d'interview demander beaucoup et j'espérais avoir des opinions sur les bonnes réponses: vous avez un gros fichier de 10+ Go et vous voulez savoir quel élément se produit le plus, quelle est la bonne façon pour faire ça?

Itérer et garder une trace dans une carte n'est probablement pas une bonne idée car vous utilisez beaucoup de mémoire, et garder une trace lorsque les entrées arrivent n'est pas la meilleure option car lorsque cette question est posée, le fichier existe généralement déjà.

J'ai également pensé à fractionner le fichier pour qu'il soit itéré et traité par plusieurs threads, puis que ces résultats soient combinés, mais le problème de mémoire pour les cartes est toujours là.

Lorsque vous avez un fichier très volumineux et de nombreux éléments, mais l'élément le plus courant est très courant - se produit fraction du temps - vous pouvez le trouver en temps linéaire avec des mots d'espace (le constante dans la notation est très petite, essentiellement 2 si vous ne comptez pas le stockage pour des choses auxiliaires comme le hachage). De plus, cela fonctionne très bien avec le stockage externe, car le fichier est traité en séquence un élément à la fois, et l'algorithme ne "regarde en arrière" jamais. Une façon de le faire est via un algorithme classique de Misra et Gries, voir ces notes de cours . Le problème est maintenant connu comme le problème des frappeurs lourds (les éléments fréquents étant les frappeurs lourds).O ( k ) O ( $> 1/k$$O(k)$$O()$

L'hypothèse selon laquelle l'élément le plus fréquent apparaît fraction du temps pour un petit nombre peut sembler forte mais elle est en quelque sorte nécessaire! Autrement dit, si vous aurez un accès séquentiel à votre fichier (et si le fichier est énorme, l'accès aléatoire sera trop cher), tout algorithme qui trouve toujours l'élément le plus fréquent dans un nombre constant de passages utilisera un espace linéaire dans le nombre d'éléments . Donc, si vous ne supposez rien sur l'entrée, vous ne pouvez pas battre une table de hachage. L'hypothèse selon laquelle l'élément le plus fréquent est très fréquent est peut-être le moyen le plus naturel de contourner les résultats négatifs.$> 1/k$$k$

Voici un croquis pour , c'est-à-dire lorsqu'il y a un seul élément qui se produit plus de la moitié du temps. Ce cas particulier est connu sous le nom d'algorithme de vote majoritaire et est dû à Boyer et Moore. Nous garderons un seul élément et un seul décompte. Initialisez le nombre à 1 et stockez le premier élément du fichier. Ensuite, traitez le fichier en séquence:$k = 2$

• si l'élément actuel du fichier est le même que l'élément stocké, augmentez le nombre d'un
• si l'élément actuel du fichier est différent de l'élément stocké, diminuez le nombre d'un
• si le nombre mis à jour est de 0, "supprimer" l'élément stocké et stocker l'élément actuel du fichier; augmenter le nombre à 1
• passer à l'élément suivant du fichier

Un peu de réflexion sur cette procédure vous convaincra que s'il existe un élément "majoritaire", c'est-à-dire un élément qui se produit plus de la moitié du temps, alors cet élément sera l'élément stocké après le traitement de tout le fichier.

Pour général , vous gardez éléments et compte, et vous initialisez les éléments au premier éléments distincts du fichier et les comptes au nombre de fois chacun de ces éléments apparaît avant de voir le -ème élément distinct. Ensuite, vous exécutez essentiellement la même procédure: le nombre d'un élément est augmenté chaque fois qu'il est rencontré, tous les nombres d'éléments sont diminués si un élément qui n'est pas stocké est rencontré, et lorsqu'un certain nombre est nul, cet élément est expulsé en faveur de la élément courant du fichier. Il s'agit de l'algorithme Misra-Gries.k - 1 k - 1 k $k$$k-1$$k-1$$k$$k$

Vous pouvez bien sûr utiliser une table de hachage pour indexer les éléments stockés. À la fin, cet algorithme est garanti pour retourner tout élément qui se produit plus de fraction du temps. C'est essentiellement le mieux que vous puissiez faire avec un algorithme qui effectue un nombre constant de passages sur le fichier et ne stocke que des mots .1 / k O ( k $k-1$$1/k$$O(k)$

Une dernière chose: après avoir trouvé candidats "frappeurs lourds" (c'est-à-dire des éléments fréquents), vous pouvez effectuer un autre passage sur le fichier pour compter la fréquence de chaque élément. De cette façon, vous pouvez classer les éléments entre eux et vérifier s'ils se produisent tous plus de fraction du temps (s'il y a moins de tels éléments, certains des éléments renvoyés par l'algorithme peuvent être des faux positifs ).$k$k - $1/k$$k-1$

La réponse évidente est bien sûr de conserver une carte de hachage et de stocker un compteur de l'occurrence des éléments lorsque vous vous déplacez dans le fichier comme Nejc l'a déjà suggéré. C'est (en termes de complexité temporelle) la solution optimale.

Si toutefois vos besoins en espace sont restreints, vous pouvez effectuer un tri externe sur le fichier, puis rechercher la plus longue série consécutive d'éléments égaux. Les éléments suivants doivent avoir une empreinte mémoire constante et peuvent être effectués dans$\Theta(n\log{n}).$

Si l'élément le plus courant est plus courant que l'élément commun suivant par une marge substantielle et que le nombre d'éléments différents est petit par rapport à la taille du fichier, vous pouvez échantillonner au hasard quelques éléments et renvoyer l'élément le plus courant de votre échantillon.