Plus rapide pour trouver des doublons conditionnés par le temps

Question

Dans une machine avec AIX sans PERL j'ai besoin de filtrer les enregistrements qui seront considérés comme dupliqués s'ils ont le même id et s'ils ont été enregistrés entre une période de quatre heures.

I mis en œuvre ce filtre à l'aide AWK et assez bien fonctionner, mais je besoin d'une solution beaucoup plus rapide:

 
# Generar lista de Duplicados 
awk 'BEGIN { 
FS="," 
} 
/OK/ { 
    old[$8] = f[$8]; 
    f[$8] = mktime($4, $3, $2, $5, $6, $7); 
    x[$8]++; 
} 
/OK/ && x[$8]>1 && f[$8]-old[$8] 

Any suggestions? Are there ways to improve the environment (preloading the file or someting like that)?
 

The input file is already sorted.
 

With the corrections suggested by jj33 I made a new version with better treatment of dates, still maintaining a low profile for incorporating more operations:
 


awk 'BEGIN { 
    FS=","; 
    SECSPERMINUTE=60; 
    SECSPERHOUR=3600; 
    SECSPERDAY=86400; 
    split("0 31 59 90 120 151 181 212 243 273 304 334", DAYSTOMONTH, " "); 
    split("0 366 731 1096 1461 1827 2192 2557 2922 3288 3653 4018 4383 4749 5114 5479 5844 6210 6575 6940 7305", DAYSTOYEAR, " "); 
} 
/OK/ { 
    old[$8] = f[$8]; 
    f[$8] = mktime($4, $3, $2, $5, $6, $7); 
    x[$8]++; 
} 
/OK/ && x[$8]>1 && f[$8]-old[$8] 2) && (((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0))) { 
     d2m = d2m + 1; 
    } 
    d2y = DAYSTOYEAR[ y - 1999 ]; 
    return ss + (mm*SECSPERMINUTE) + (hh*SECSPEROUR) + (d*SECSPERDAY) + (d2m*SECSPERDAY) + (d2y*SECSPERDAY); 
} 
' 

Answer 1

Si votre fichier de données contient tous vos enregistrements (il inclut les enregistrements qui ne sont pas dupicate ids dans le fichier) vous pouvez le pré-traiter et produire un fichier qui contient uniquement des enregistrements qui ont des doublons (ids).

Si c'est le cas, cela réduirait la taille du fichier que vous devez traiter avec votre programme AWK.

Answer 2

Comment le fichier d'entrée est-il trié? Comme, cat fichier | trier, ou trié via un seul champ spécifique, ou plusieurs champs? Si plusieurs champs, quels champs et quel ordre? Il semble que les champs horaires sont une horloge de 24 heures, pas 12, n'est-ce pas? Est-ce que tous les champs date/heure sont remplis de zéros (9h ou 9h?)

Sans tenir compte des performances, il semble que votre code rencontre des problèmes avec les limites des mois car il suppose que tous les mois sont 30 jours longue. Prenez les deux dates 2008-05-31/12: 00: 00 et 2008-06-01: 12: 00: 00. Ce sont 24 heures d'intervalle, mais votre code produit le même code temporel pour les deux (63339969600)

Answer 3

Je pense que vous auriez besoin de considérer les années bissextiles. Je n'ai pas fait le calcul, mais je pense que pendant une année bissextile, avec un code dur de 28 jours pour feb, une comparaison de midi le 2/29 et midi le 3/1 donnerait le même horodatage en double qu'auparavant . Bien qu'il semble que vous ne l'avez pas implémenté comme ça. De la façon dont vous l'avez implémenté, je pense que vous avez toujours le problème mais c'est entre les dates du 12/31 de $ leapyear et 1/1 de $ leapyear + 1.

Je pense que vous pourriez également avoir des collisions pendant les changements d'heure si votre code doit gérer les fuseaux horaires qui les gèrent.

Le fichier ne semble vraiment pas trié de manière utile. Je devine que ce champ $ 1 est une sorte de statut (le "OK" que vous vérifiez). Donc, il est trié par statut d'enregistrement, puis par JOUR, puis MOIS, ANNÉE, HEURES, MINUTES, SECONDES. Si c'était l'année, le mois, le jour, je pense qu'il pourrait y avoir des optimisations là-bas. Peut-être encore mais mon cerveau va dans une direction différente en ce moment.

S'il y a un petit nombre de clés dupliquées par rapport au nombre total de lignes, je pense que votre meilleur pari est de réduire le fichier que votre script awk fonctionne pour simplement dupliquer les clés (comme David said). Vous pouvez également pré-traiter le fichier afin que les seules lignes présentes soient les lignes/OK /. Je pense que je le ferais avec un pipeline où le premier script awk imprime uniquement les lignes avec des ID en double et le second script awk est fondamentalement celui ci-dessus mais optimisé pour ne pas chercher/OK/et avec la connaissance que toute clé est un clé en double.

Si vous savez à l'avance que toutes ou la plupart des lignes auront des clés répétées, cela ne vaut probablement pas la peine de jouer avec. Je mordrais la balle et l'écrirais dans C. Tons plus de lignes de code, beaucoup plus vite que le script awk.

Answer 4

Sur beaucoup d'unix, vous pouvez obtenir le tri par tri d'une colonne ou d'un champ particulier. Ainsi, en triant le fichier par l'ID, puis par la date, vous n'avez plus besoin de conserver le tableau associatif de la dernière fois que vous avez vu chaque ID. Tout le contexte est là dans l'ordre du fichier.

Sur mon Mac, ce qui a en quelque sorte GNU, il est:

sort -k 8 <input.txt> output.txt 

pour trier sur le champ ID. Vous pouvez aussi trier sur un deuxième champ, en disant (par exemple) 8,3 à la place, mais seulement 2 champs. Ainsi, un horodatage time_t de style unix n'est peut-être pas une mauvaise idée dans le fichier - il est facile à trier et vous permet d'économiser tous ces calculs de date. Aussi, (encore au moins dans GNU awk), il y a un mktime function qui fait le time_t pour vous des composants.

Answer 5

@AnotherHowie, je pensais que tout le prétraitement pouvait être fait avec tri et uniq. Le problème est que les données de l'OP semblent être délimitées par des virgules et que uniq (Solaris 8) ne vous permet pas de spécifier le séparateur d'enregistrements, donc il n'y avait pas de moyen super propre de faire le pré-traitement en utilisant les outils unix standard. Je ne pense pas que ce serait plus vite, donc je ne vais pas regarder les options exactes, mais vous pouvez faire quelque chose comme:

cut -d, -f8 <infile.txt | sort | uniq -d | xargs -i grep {} infile.txt >outfile.txt 

Ce n'est pas très bon parce qu'il exécute grep pour chaque ligne contenant un clé en double. Vous pourriez probablement masser la sortie uniq en une seule expression rationnelle pour alimenter grep, mais le bénéfice ne serait connu que si l'OP affiche le ratio attendu de lignes contenant des clés dupliquées suspectées sur le nombre total de lignes dans le fichier.

Answer 6

Cela ressemble à un travail pour une base de données réelle. Même quelque chose comme SQLite pourrait probablement vous aider raisonnablement bien ici. Le gros problème que je vois est votre définition de "dans les 4 heures". C'est un problème de fenêtre glissante, ce qui signifie que vous ne pouvez pas simplement quantifier toutes les données en segments de 4 heures ... vous devez calculer tous les éléments "à proximité" pour chaque autre élément séparément. Pouah.