D'abord Voir les questions:
Comment trouver la même URL dans un grand nombre d'URL? (Baidu)
Comment trouver des mots à haute fréquence de plusieurs données? (Baidu)
Comment puis-je trouver le site Web le plus sur la propriété intellectuelle de Baidu dans un certain jour? (Baidu)
Comment trouver un entier ne pas répéter avec un grand nombre de données? (Baidu)
Comment puis-je déterminer s'il existe une grande quantité de données? (Tencent)
Comment puis-je interroger la chaîne de requête la plus populaire? (Tencent)
Comment puis-je compter un nombre différent de numéros de téléphone? (Baidu)
Comment trouver un peu de neutre à partir de 500 millions? (Baidu)
Comment organiser en fonction de la fréquence de la requête? (Baidu)
Comment puis-je découvrir le nombre de 500 meilleurs? (Tencent)
Quelle est la réponse? Regarder en bas
a donné deux fichiers A, B, chaque fichier stocké 5 milliards d'URL, MURL de fin, chaque URL occupe 64b et la mémoire limitée est de 4g. Veuillez trouver l'URL générale d'A, B.
2. L'idée de solution
Chaque URL occupe environ 64B, puis 5 milliards d'URL représentent environ 320 distance GB.
5 000 000 000 * 64B ≈ 5GB * 64 = 320GB
Parce que la taille de la mémoire n'est que 4G, nous ne pouvons pas télécharger toutes les URL dans la mémoire dans la mémoire. Pour ce type de thème, il est souvent nécessaire d'appliquer la politique accordée, à savoir: diviser plusieurs petits fichiers dans un fichier dans un fichier, de sorte que chaque petite taille de fichier ne dépasse pas 4G, de sorte que vous pouvez lire ce petit fichier, il est donc possible de lire ce petit fichier. traité en mémoire.
Idées: Fichier Travers d'abord A, à l'URL de l'URL Parcourir via (URL)% 1000, stockée L'URL est déplacée vers A0, A1, A2, .. suivez les résultats de calcul. A999, de sorte que chaque taille est d'environ 300 Mo. Utilisez la même méthode pour traverser le fichier B, stocker les URL dans les fichiers B sur les fichiers B0, B1, B2, .. B999. Après traitement, toutes les URL peuvent être dans de petits fichiersg, cela signifie que A0 correspond à B0, .. A999 correspond à B999, de petits fichiers qui ne correspondent pas à avoir la même URL. Alors, ensuite, nous devons juste demander à ce 1000 avec la même URL dans le petit fichier.
Après cela, passez par l'AI (I ∈ [0, 999]), enregistrez l'URL dans la collection HASHSET. Ensuite, parcourez chaque URL dans la balle, voyez s'il existe dans la collection HASHSET, s'il s'agit d'une URL populaire, vous pouvez enregistrer cette URL dans un fichier distinct.
3. Résumé de la méthode
Séparatage, fonction de hachage de la fonction de hachage
pour chaque sous-fichier
1. DESCRIPTION THUMICS
Il existe des fichiers taille 1 Go, chaque ligne du fichier est un mot, la taille de chaque mot ne dépasse pas 16b, la taille de la limite de mémoire est de 1 Mo, demande 100 mots avec le fréquence la plus élevée (100 top 100).
2. L'idée de solution
en raison des limites de mémoire, nous ne pouvons toujours pas lire tous les mots de tous les mots de la mémoire. Par conséquent, il peut également être utilisé pour les cessionnairesCh Un fichier volumineux dans plusieurs petits fichiers pour vous assurer que le petit fichier est lu directement dans la mémoire chaque fichier.
Idées: First Traverse Grand Fichier, effectuez la fonction de hachage (X)% 5000 par mot X a disparu et définit le résultat du résultat dans un fichier AI. Après la fin de la transmission, nous pouvons obtenir 5 000 petits fichiers. Chaque fichier est d'environ 200 Ko. S'il reste encore plus de 1 Mo de petite taille de fichier, il continuera de se décomposer de la même manière.
Trois mots ont la fréquence la plus fréquente dans chaque petit fichier. Le moyen le plus simple est d'utiliser HASHMAP. Les touches de cas sont des mots, la valeur est la fréquence du mot. Les méthodes spécifiques sont les suivantes: pour le mot X passant, sans existence sur la carte, map.put (x, 1) est exécuté; Si oui, map.put (x, map.get (x) +1), ajoutez une fréquence de ceci à 1.
Top Nous comptons la fréquence de chaque petit fichier. Ensuite, nous pouvons trouver 10 fréquentes fréquentes dans tous les mots en maintenant une petite pile.0. Des méthodes spécifiques suivent chaque petite session de fichier, xConstruit une petite pile, la taille du tas est de 100. Si le nombre de mots passe plus dépassé le nombre de fois du haut du haut, remplacez les mots situés en haut de la pile, puis être ajusté dans de petites piles menant, après La fin de la transmission, les mots sur les petites piles sont la fréquence la plus élevée. Un mot.
3. RÉSUMÉ DE LA MÉTHODE
Au minimum de l'aptitude distincte, utilisez le gros tas
Les données de journal de grande taille stockées dans un fichier volumineux ne peuvent pas lire directement dans la mémoire, demandez IP du nombre d'accès aux Nadians.
2. Idées de solutions
Cette question ne se soucie que du nombre d'IP dans un certain jour, de sorte que vous parcourez d'abord le fichier précédent et votre tour Visitez Yahoo ce jour-là. Les informations associées de la propriété intellectuelle sont enregistrées dans un fichier grand séparé. Ensuite, la méthode est la même que le problème précédent et la cartographie IP IP, suivie du nombre de statistiques IP et enfin tCalculer le nombre de répétitions. IP.
Remarque: Ici, il vous suffit de trouver le nombre d'IP avec le nombre de fois, vous pouvez utiliser un tas pour utiliser une variable maximale.
3. Résumé de la méthode
sur les taux bruts 2,5] pour trouver des entiers non répétés. Remarque: la mémoire ne suffit pas à contenir ces 250 millions d'entiers.
2. Idées de solution
Semblable à la méthode thème précédente, sera divisée en 250 millions dans de nombreux petits fichiers, trouvez l'entier. Dans chaque petit fichier, puis consolidez chaque dépendance, qui est le résultat final.
[Méthode 2: Bitchart]
Bitmap marque la valeur correspondant à un élément avec un ou plusieurs bits et la clé en tant qu'élément. En utilisant des bits comme unité pour stocker des données, il peut économiser beaucoup d'espace de stockage.
Bitmap démontre l'existence de certains facteursComment utiliser un groupe de séries. Il peut être utilisé pour trouver rapidement, planifier, tri, v.v. Pas très clair? Je vais d'abord donner un petit exemple.
Supposons que nous soyons disposés en 5 éléments (6, 4, 2, 1, 5) dans [0, 7] et la méthode bitmap peut être utilisée. Il y a 8 chiffres à moins de 0 ~ 7, seulement 8 bits, 1 octet. Tout d'abord, mettre tous les 0 bits:
0 0 0 0 0 0 0 0
Parcourez 5 éléments, première réunion 6, puis l'enregistrement 0 est défini sur 1; Ensuite rencontré 4, un peu d'un peu de l'indice de 4 est 1: 0 0 0 1 0 1 0
Après la fin de la fin, après la fin , le nombre de bits est comme celui-ci: 0 1 1 1 0 1 1 0
Méthode Bitmap est un algorithme très pratiqueRésoudre l'algorithme lié aux entiers. Supposons que l'intégrité int prend 4b, c'est-à-dire 32 bits, puis nous pouvons représenter le nombre d'entiers à 232.
Donc, nous utilisons 2 bits pour exprimer le statut de chaque numéro:
00 signifie que ce nombre n'a pas encore été apparu
01 signifie que ce nombre est apparu une fois (c'est-à-dire que l'entier non répété est trouvé pour les threads du propriétaire)
10 signifie que ce nombre a répété
Après cela, la mémoire totale est 232 * 2B = 1 Go. Par conséquent, lorsque la mémoire dépasse 1 Go, une méthode bitmap peut être utilisée. Supposons que la mémoire répond au besoin de bitmap, effectuant les éléments suivants:
Passez 250 millions d'entiers, vérifiez le bit correspondant dans Bitmap si 00, il devient 01, et s'il est 01, il deviendra 10 et si Il est encore 10, toujours inchangé. Une fois que la transmission se termine, vérifiez le bitmap et exporter le nombre d'entiers de 01.
3. Résumé de la méthode
Revue Voir le numéro répété, PhuongBitmap Ewake est un moyen très efficace. ont donné 4 milliards de dollars en ordre non répété dans l'ordre, alors pour certains, pour certains, pour certains, Comment ce nombre peut-il dans ces 4 tarifs bruts?
2. Idées de solution
Méthode 1: Division
peut toujours être résolue par des modes de capture, des modes similaires à l'avant, il ne sera pas décrit à nouveau.
Méthode 2: Méthode bitmap
4 milliards Pas de répétition, nous utilisons 4 milliards de bits pour indiquer que le bit d'origine est égal à 0, puis les besoins de mémoire totale: 4 000 000 000 milliards de dollars
Nous avons lu ces 4 milliards d'entiers pour définir le bit correspondant. Il lit le numéro à la requête, vérifiez si le bit correspondant est 1, si 1 signifie Cela peut exister, si 0 signifie qu'il n'existe pas.
3. Résumé de
Voir Si ce numéro est présent ou non, il en est unLa méthode est très efficace pour déterminer si le nombre est répété ou non.
Le moteur de recherche passera les utilisateurs une fois accessible dans le fichier journal. Toutes les requêtes utilisées des chaînes sont enregistrées, chacune d'au plus 255 octets.
En supposant que cela a actuellement un enregistrement de 1000W (relativement élevé, bien que le total soit de 1000W, mais si la répétition est supprimée, pas plus de 300W). Veuillez compter les 10 chaînes de requête les plus courantes et la mémoire requise pour une utilisation ne peut dépasser 1g. (Plus la répétition de la chaîne de requête est élevée, plus vous l'interrogez, vous serez plus populaire.)
2. Idées de solution
Chaque chaîne tracé jusqu'à la String de 255B, 1000W prend environ 2,55 g de mémoire, nous ne pouvons donc pas lire toutes les cordes pour le traitement de la mémoire.
Méthode 1: Méthode de retournement
La méthode d'octroi d'une éventuelle est toujours une méthode très pratique
Divisé en plusieurs fichiersM Dites à la chaîne dans un petit fichier directement téléchargé dans la mémoire, puis prend 10 chaînes dans chaque fichier dans chaque fichier; Il y a jusqu'à 10 chaînes dans tous les fichiers sur une petite pile.
La méthode est réalisable, mais pas la meilleure, décrite ci-dessous.
Méthode 2: Méthode HASHMAP
Bien que le nombre total de chaînes soit plus, il ne dépasse pas 300W après la pesée, peut donc être considéré comme épargnant toutes les cordes et toutes les cordes d'apparence. Dans un hachema, l'espace occupé est de 300W * (255 + 4) ≈777m (où 4 signifie 4 octets entier). On peut voir que 1g suffit assez.
Idées: First, Traverse String, sinon disponible sur la carte, veuillez enregistrer directement la carte, la valeur est 1; Si dans la carte, ajoutez la valeur correspondante à 1, la complexité de l'heure de l'étape O (n). Après cela, la carte est déplacée et une petite pile de 10 plus grands éléments construits. Si le nombre d'apparences est parcouru par la chaîne plus grande que le nombre d'apparitionsLe haut, le remplacement est effectué et le tas est ajusté dans une petite pile. Après avoir passé, 10 cordes dans la pile sont les cordes les plus susceptibles. Cette complexité est O (Nlog10).
Méthode 3: PROCÉDÉ DE PRÉFIX DE COLLAGE
Méthode 2 Utilisation de HASHMAP aux statistiques, lorsque ces chaînes ont un grand nombre de préfixes, envisagez d'envisager d'utiliser l'arborescence de préfixe pour compter le nombre de Les chaînes apparaissent, le bouton du numéro d'arbre de sauvegarde apparaît et 0 indique qu'il n'y a pas d'apparence.
Lorsque vous traversez le fil, regardez dans l'arborescence de préfixe, si vous avez trouvé, ajoutez le nombre de chaînes enregistrées dans le bouton 1, sinon, créez un nouveau bouton pour cette chaîne, construite après l'achèvement, le numéro Les cordes du nœud de feuille sont réglées sur 1.
Enfin, les petites piles supérieures sont toujours triées par le nombre de séquences de chaînes.
3. Résumé de la méthode
L'arborescence de préfixe est souvent utilisée pour statistiques du nombre de séquences. Une autre grande utilisation deC'est une recherche de chaîne définie s'il existe une chaîne répétée.
Un fichier contenant plusieurs numéros de téléphone, chaque nombre est de 8 mots, statistiques de différents nombres.
2. L'idée de solution
Cette question résoudra toujours le problème en répétant les données. Pour de tels problèmes, la méthode bitmap est généralement envisagée.
Pour cette question, le nombre de numéros de téléphone 8 bits peut être exprimé en 108, soit 100 millions. Chaque numéro indiqué par un peu, compte un total de 100 millions de bits et de mémoire représentent environ 100 m.
Idées: Appliquer pour un réseau bitmap d'une longueur de 100 millions, qui est initialisé à 0. puis passez à travers tous les numéros de téléphone, placez la position dans le bitmap correspondant à la ville numéro 1. Une fois la transmission terminée, si le bit est 1, ce numéro de téléphone existe dans le fichier, sinon elle n'existe pas. La quantité de valeur de bit est 1 est le nombre de numéros de téléphone différents.
3. Abstrait Phuong TEffet
Résoudre les incidents de données répétitifs, n'oubliez pas de prendre en compte la méthode bitmap.
1. DESCRIPTION SUJET
Trouvez des nombres médians de 500 millions. Une fois que les données sont disposées, le nombre de positions dans le plus intermédiaire est médiane. Lorsque le nombre d'échantillons est étrange, la médiane est le subordonné (N + 1) / 2; Lorsque le nombre d'échantillons même, la médiane est le nombre de chiffres et le premier numéro + N / 2 ..
2. Idées de solution
Si cette question n'a pas la règle de mémoire limite Vous pouvez lire tous les numéros en mémoire. Mais le meilleur algorithme de classification a la complexité de O (nlogn). D'autres méthodes ici sont utilisées ici.
Méthode 1: Double Bund
Maintenir deux piles, une grande pile supérieure, une petite pile. Le plus grand nombre de piles principales est plus grande que la plus petite quantité de petites piles; Assurez-vous que la différence entre les éléments de ces deux piles ne dépasse pas 1.
si la quantité totale de données est une partieMême après la construction des deux piles, la médiane est la moyenne de deux éléments de pile. Lorsque la totalité des données est impair, en fonction de la taille des deux piles, la médiane doit être dans la pile de données.
MedianFinder {
Private PROSITYQUE & LT; Integer & GT; Maxheap;
PriorityQueee & lt; Integer & GT; Minheap;
/ ** Initialisez votre structure de données ici. * /
MEDIANFinder () {
MaxHeap = Nouvelle priorityeeUe & Lt; & Gt; (Comparer.Reversonorder ());
MINHEE = Nouvelle priorityeeUee & lt; & Gt; (Integer :: Comparaison); }
Addnum (int Num) {
Si (maxhaeap.isemony () | | Maxhaeap.peek ()) & gt; num) {
maxhaeap.offer (Num);
{
Minheap (Num);
}
int size1 = maxheap.size ();
int size2 = minheap.size ();
Si (taille1 - Taille2 & gt;{
Minheap.offer (maxhaeap.poll ());
} Autre si (Taille2 - Taille1 & GT; 1) {
Maxhaeap.offer (Minheap.Poll ());
}
}
Dual FindMedian () {
int size1 = maxhaeap.size ();
INT TAILLE2 = MINHEAP.SIZE ();
Renvoyer la taille1 == Taille2
(Maxhaeap.peek () * 1.0 / 2
: (taille1 & gt; taille2? Maxhaeap.peek (): Peek ());
Méthode sur la nécessité de télécharger Toutes les données en mémoire. Lorsque la quantité de données est grande, elle est impossible, cette méthode est donc appliquée à la petite quantité de capacité de données. 500 millions, chacun occupé 4b et le se souvient 2G est requis. Si la mémoire est inférieure à 2G Cette méthode ne peut pas être utilisée et d'autres méthodes sont décrites ci-dessous.
Méthode 2: Méthode de tige
L'idée de la méthode est accordée pour convertir progressivement un gros problème en un problème plus faible.
pour cCet Européen demande, ces 500 millions de chiffres sont lus dans l'ordre, pour le nombre de numéros de lecture, s'il correspond au bit le plus élevé de 1, écrivez ce numéro à F1 sinon, écrivez à F0. Avec cette étape, ces 500 millions de numéros peuvent être divisés en deux parties et chiffres en F0 supérieurs au nombre de la F1 (le plus haut de symbolisation).
Après la division, il peut être très facile de savoir que le numéro du milieu en F0 ou F1. En supposant qu'il y ait 100 millions de chiffres en F1, la moyenne doit être en F0 et est en F0, d'un petit nombre à un grand nombre de 150 millions de dollars de sa quantité.
Astuce: la moyenne de 500 millions est le nombre moyen de 20,5 ratios consécutifs. Si F1 compte 100 millions, la médiane est la moyenne des deux chiffres à partir du début de 150 millions.
Pour F0, le fichier peut être divisé en deux, divisés en deux, jusqu'à ce que le fichier soit divisé en mémoire et télécharge des données directement dans la mémoire. Organiser de manière médiane.
Remarque: lorsque le nombre total de données est un nombre égal, si les données des deux fichiers ont le même numéro après la division, la médiane est GILa pharmacie maximale des données plus petites de données est grande. La valeur moyenne de la valeur minimale dans le fichier.
3. Résumé de la méthode
Méthode de division, fragrance réel!
Sujet 9
Il existe 10 fichiers, chaque taille de fichier est 1G et chaque ligne de chacun Le fichier est stocké toutes les requêtes d'utilisateur, requêtes pour chaque fichier. Il peut être répété. Demande selon la fréquence de requête.
2. L'idée de solution
Si la requête est relativement grande, vous pouvez envisager de manipuler toutes les requêtes dans la mémoire en même temps; Si la requête n'est pas élevée, la mémoire n'est pas suffisante pour contenir toutes les requêtes, à ce stade, une méthode est nécessaire pour être utilisée ou d'autres méthodes pour résoudre.
Si la vitesse répétée de requête répétée, le nombre total de requêtes différentes est relativement faible et que vous pouvez considérer que toutes les traces sont chargées dans HASHMAP. en mémoire .. Suivant, vousPeut organiser dans des requêtes.
Méthode 2: Différences
La méthode de la division doit être déterminée en fonction de la taille de la quantité de données et de la taille de la mémoire disponible. Pour cette question, vous pouvez parcourir les requêtes d'accès dans 10 fichiers et diviser ces requêtes en 10 petits fichiers via une fonction de hachage de hachage (requête)% 10. Après chaque petit fichier, le nombre de fois où la question est apparue, arrangée et enregistrée dans un autre fichier séparé. selon le nombre de fois.
Ensuite, tous les fichiers sont triés par requête Quantité, dans lequel la fusion peut être utilisée (car toutes les requêtes ne peuvent pas être lues en mémoire, doivent utiliser un tri à l'extérieur).
3. RÉSUMÉ DE LA MÉTHODE
Si la mémoire est suffisante, la lecture directe est disposée
la mémoire n'est pas suffisante, divisée d'abord en petits fichiers, après que le petit fichier est la séquence, Trié par colonne
1. DESCRIPTION THUNICS
Il y a 20 tableaux, chaque réseau a 500 éléments etTrié de manière ordonnée. Comment trouver le plus haut numéro supérieur dans cette 20 * 500?
2. Idées de solution
Pour les problèmes de Topk, la méthode la plus courante consiste à utiliser une pile. Pour cette question, supposons que l'ordre en baisse des matrices soit arrangé et peut utiliser les méthodes suivantes:
Définit d'abord les grandes piles supérieures, la taille du tas de taille correspond au nombre de chiffres, ce qui est 20 et stocke la valeur maximale de chaque tableau dans le tas. L'élément de pile suivant est supprimé, sauvegardé sur un tableau d'autres 500 tailles, puis insère l'élément suivant de la matrice d'élément supprimé dans le grand plateau en tas. Répétez l'étape ci-dessus jusqu'à ce que le 500e élément soit supprimé, les 500 numéros maximaux sont trouvés.
Pour supprimer les données dans le tas, il peut savoir quelles matrices sont supprimées à partir de laquelle une valeur peut être supprimée de ce tableau, ce qui peut stocker le pointeur du tableau dans le tas. Ce pointeur fournit une méthode de taille relative.
Entrez Lombok.Data;
Entrez Java.util.araies;
Entrez Java.Util.PeriorityQueQueue;
/ **
* @Author https://github.com/yanglbme
* /
DatawithSource de classe publique faite de la comparaison & LT; Datawsource & GT; {
*
* /
Valeur int Int;
/ **
* Enregistrer le tableau de valeur
* /
Source Int privé;
/ **
* Indice d'enregistrement dans le tableau
* /
Int Int;
DATAWITHSOURCE PUBLIC (VALUE INT, INT SOURCE, INT Index) {
Ceci.Value = valeur;
"This.source = Source;
Index; }
/ **
*
* Parce que la priorité utilisant la priorité utilisant la pile haut petit, cela est fait en modifiant
* pour rendre priorityqueque dans les plus grandes piles.
Public int comparaison (DatawithSource O) { renvoie entier. comparer (O.gevalue (), cela.Value); Inspection de la classe { Données intimes inticiatiques publiques (] (int [] [] [] [] [int Rowsize = data.length; // Créez une matrice de taille de colonne, résultats de stockage int] Int] Résultats = Nouveau Int [colonne]; Priorité et LT; DatawithSource & GT; MaxHeap = Nouvelle priorityQueue & lt; (); ] Pour (int I = 0; i & lt; Rowsize; ++ i) { // Définissez l'élément maximum de chaque tableau dans le tas Datawithsource D = Nouveau DatawithSource (Data [i] [0], I, 0); } int Num = 0; tandis que ( Num & lt; colonne) { // Supprimer éléments onduleursng Daxhaeap.poll (); Résultats [Num ++] = D.Getvalue (); { Break; } D.setvalue [D.Getsource ()] [D.GetIndex () + 1]); d.sedindex (d.getindex () + 1); Maxhaeap.add (D); } } } Public statique Void Main (String [] args) { [INT [] [] Data = { {29, 17, 14, 2, 1}, {19, 17, 16, 15, 6}, {30, 25 , 20, 14, 5}, }; int [] top = gettop (données); System.out Array.Tostring (haut));/// [30, 29, 25, 20, 19] } 3. RÉSUMÉ DE MÉTHODE Rechercher TOWK, voir compte tenu de la prise de vue Classification de la pile?