un million d'enregistrements dans le fichier journal pour un site de magasinage en ligne. FInd adresses IP distinctes

Question

Il s'agit d'une question de test technique. Compte tenu de 1 million d'enregistrements dans un fichier journal. Ce sont des enregistrements de hits de site Web d'un site Web de magasinage en ligne. Les enregistrements sont de type:

TimeStamp:Date,time ; IP address; ProductName 

Trouvez les adresses IP distinctes et le produit le plus populaire. Quel est le moyen le plus efficace de le faire? Une solution est le hachage. Si la solution est un hachage, veuillez fournir une explication pour le hachager efficacement puisqu'il y a un million d'enregistrements.

Answer 1

Dans le monde réel, s'il s'agit d'une chose ponctuelle ou occasionnelle, j'insérerais simplement les données dans une base de données et j'exécuterais quelques requêtes de base.

Puisqu'il s'agit d'une tâche de devoirs, ce n'est probablement pas ce que le prof cherche. Une adresse IP est vraiment juste un nombre de 32 bits. Je pourrais convertir chaque adresse IP en son équivalent 32 bits au lieu de créer un hachage.

Depuis ce est devoirs, le reste "est laissé comme un exercice pour le lecteur."

Answer 2

J'ai récemment fait quelque chose de similaire pour les devoirs, je ne suis pas sûr du nombre total de lignes, mais c'était beaucoup. Le fait est que votre ordinateur peut probablement le faire très rapidement, même s'il y a un million d'enregistrements.

Je suis d'accord avec vous sur la table de hachage, et je ferais les deux questions un peu différemment. Le premier je verifierais chaque ip contre la hashtable, et s'il existe, ne rien faire. S'il n'existe pas, ajoutez-le à la hashtable et incrémentez un compteur. À la fin du programme, le compteur vous dira combien d'IP uniques il y avait.

La seconde je voudrais hacher le nom du produit et le mettre dans la hashtable. J'augmenterais la valeur associée au hashkey chaque fois que je trouverais une correspondance dans la table. À la fin, parcourez toutes les clés et valeurs de la table de hachage et trouvez la valeur la plus élevée. C'est le produit le plus populaire.

Answer 3

Un million d'enregistrements de journal est vraiment un très petit nombre; il suffit de les lire et de garder un ensemble d'adresses IP et une dictée des noms de produits au nombre de mentions - vous ne mentionnez aucune contrainte de langage spécifique donc je suppose un langage qui fera (implicitement) un excellent hachage de ces chaînes Votre nom est acceptable (Perl, Python, Ruby, Java, C#, etc, tous ont de bonnes installations à cet effet).

Par ex, en Python:

import collections 
import heapq 

ipset = set() 
prodcount = collections.defaultdict(int) 

numlines = 0 
for line in open('logfile.txt', 'r'): 
    timestamp, ip, product = line.strip().split(';') 
    ipset.add(ip) 
    prodcount[product] += 1 
    numlines += 1 

print "%d distinct IP in %d lines" % (len(ipset), numlines) 
print "Top 10 products:" 

top10 = heapq.nlargest(10, prodcount, key=prodcount.get) 
for product in top10: 
    print "%6d %s" % (prodcount[product], product) 

Answer 4

Tout d'abord, un million de lignes ne sont pas du tout un énorme fichier. Un simple script Perl peut masquer un script de 2,7 millions de lignes en 6 secondes, sans avoir à trop penser à l'algorithme.

Dans tous les cas, le hash est le chemin à parcourir et, comme indiqué, il n'y a pas besoin de s'embêter avec le hachage sur une représentation entière. Si nous parlions d'un fichier vraiment énorme, alors les E/S deviendraient le goulot d'étranglement et donc la méthode de hachage devient de moins en moins pertinente au fur et à mesure que le fichier grossit. Théoriquement dans un langage comme C, il serait probablement plus rapide de hacher sur un entier que sur une chaîne, mais je doute que dans un langage adapté à cette tâche, cela fasse vraiment une différence.Des choses comme la façon de lire efficacement le fichier importeraient beaucoup plus.

code

vinko@parrot:~$ more hash.pl 
use strict; 
use warnings; 

my %ip_hash; 
my %product_hash; 

open my $fh, "<", "log2.txt" or die $!; 

while (<$fh>) { 
     my ($timestamp, $ip, $product) = split (/;/,$_); #To fix highlighting 
     $ip_hash{$ip} = 1 if (!defined $ip_hash{$ip}); 
     if (!defined $product_hash{$product}) { 
       $product_hash{$product} = 1 
     } else { 
       $product_hash{$product} = $product_hash{$product} + 1; 
     } 
} 

for my $ip (keys %ip_hash) { 
     print "$ip\n"; 
} 

my @pkeys = sort {$product_hash{$b} <=> $product_hash{$a}} keys %product_hash; 

print "Top product: $pkeys[0]\n"; 

Exemple

vinko@parrot:~$ wc -l log2.txt 
2774720 log2.txt 
vinko@parrot:~$ head -1 log2.txt 
1;10.0.1.1;DuctTape 
vinko@parrot:~$ time perl hash.pl 
11.1.3.3 
11.1.3.2 
10.0.2.2 
10.1.2.2 
11.1.2.2 
10.0.2.1 
11.2.3.3 
10.0.1.1 
Top product: DuctTape 

real 0m6.295s 
user 0m6.230s 
sys  0m0.030s 

Answer 5

Je voudrais également lire le fichier dans une base de données, et la lierait à une autre table de noms de fichiers journaux et date/heure importés.

C'est parce que dans le monde réel, vous aurez besoin de le faire régulièrement. La société va vouloir être en mesure de vérifier les tendances au fil du temps, de sorte que vous allez rapidement poser des questions comme "est-ce plus ou moins d'adresses IP uniques que le fichier journal du mois dernier?" et "comment les produits les plus populaires changent-ils d'une semaine à l'autre". Dans mon expérience, la meilleure façon de répondre à ces questions dans un scénario d'entrevue que vous décrivez est de montrer la conscience des situations du monde réel. Un outil pour analyser les fichiers journaux (produit journalier? Hebdomadaire? Mensuel?) Et les lire dans une base de données où certaines requêtes, graphiques etc peuvent tirer toutes les données, en particulier dans plusieurs fichiers journaux, prendra un peu plus de temps pour écrire mais être infiniment plus utile et utilisable.

Answer 6

Comme d'autres personnes écrivent, il y a seulement 2 hashtables. Un pour les IP et un pour les produits. Vous pouvez compter les occurrences pour les deux, mais vous vous souciez d'eux dans la dernière "Popularité du produit"

La clé du hachage est d'avoir une clé de hachage efficace, et l'efficacité du hachage signifie que les clés sont réparties uniformément. Un choix de clé médiocre signifie qu'il y aura beaucoup de collisions et que la performance de la table de hachage en souffrira.

Étant paresseux, je serais tenté de créer un Dictionary<IPAddress,int> et j'espère que l'implémenteur de la classe IPAddress a créé la clé de hachage de manière appropriée. Pour la liste Produits, après avoir configuré la table de hachage, utilisez simplement linq pour les sélectionner.

var sorted = from o in products 
      orderby o.Value descending 
      where o.Value > 1 
      select new { ProductName = o.Key, Count = o.Value }; 

Answer 7

Il suffit de trier le fichier par chacun des deux champs d'intérêt. Cela évite d'avoir à se soucier des fonctions de hachage et fonctionnera très bien sur un jeu d'enregistrements million.

Le tri des adresses IP de cette manière facilite également l'extraction d'autres informations intéressantes telles que les accès du même sous-réseau.

Answer 8

adresses IP DISTINCTS:

$ cut -f 2 -d \; | sort | uniq 

produit le plus populaire:

$ cut -f 3 -d \; | sort | uniq -c | sort -n 

Si vous pouvez le faire, script shell comme ça. comte

$ awk -F\; '{print $2}' log.file | sort -u 

:

Answer 9

IP uniques.awk

{ a[$0]++ } 

END { 
    for(key in a) { 
     print a[key] " " key; 
    } 
} 

Top 10 articles préférés:

$ awk -F\; '{print $3}' log.file | awk -f count.awk | sort -r -n | top