Schnellere Suche nach Duplikaten in Abhängigkeit von der Zeit

Question

In einer Maschine mit AIX ohne PERL muss ich Datensätze filtern, die als dupliziert gelten, wenn sie dieselbe ID haben und wenn sie innerhalb von vier Stunden registriert wurden.

implementiert ich diesen Filter AWK und arbeiten sehr gut mit, aber ich brauche eine Lösung viel schneller:

 
# 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

Wenn Ihre Datendatei alle Datensätze enthält (dh es Datensätze enthält, die dupicate ids innerhalb der nicht über Datei) Sie könnten es vorverarbeiten und eine Datei erzeugen, die nur Datensätze enthält, die doppelte (ids) haben.

Wenn dies der Fall ist, würde die Größe der Datei reduzieren, die Sie mit Ihrem AWK-Programm verarbeiten müssen.

Answer 2

Wie wird die Eingabedatei sortiert? Wie, cat-Datei | sortieren, oder sortiert über ein einzelnes spezifisches Feld oder mehrere Felder? Wenn mehrere Felder, welche Felder und welche Reihenfolge? Es scheint, die Stundenfelder sind eine 24-Stunden-Uhr, nicht 12, oder? Sind alle Felder für Datum/Uhrzeit gepolstert (9 Uhr wäre "9" oder "09"?)

Ohne Berücksichtigung der Leistung sieht Ihr Code Probleme mit Monatsgrenzen aus, da davon ausgegangen wird, dass alle Monate 30 Tage sind lange. Nehmen Sie die zwei Daten 2008-05-31/12: 00: 00 und 2008-06-01: 12: 00: 00. Diese sind 24 Stunden auseinander, aber Ihr Code erzeugt den gleichen Zeitcode für beide (63339969600)

Answer 3

Ich denke, Sie müssten Schaltjahre berücksichtigen. Ich habe die Mathematik nicht gemacht, aber ich denke während eines Schaltjahres, mit einem harten Code von 28 Tagen für Feb, würde ein Vergleich von Mittag am 2./29 und Mittag am 3/1 denselben doppelten Zeitstempel wie vorher ergeben . Obwohl es aussieht, als hättest du es nicht so implementiert. So wie Sie es implementiert haben, ich denke, Sie haben immer noch das Problem, aber es ist zwischen Daten am 31.12. Von $ leapyear und 1/1 von $ leapyear + 1.

Ich denke, Sie könnten auch einige Kollisionen während Zeitänderungen haben, wenn Ihr Code mit Zeitzonen umgehen muss, die sie behandeln.

Die Datei scheint nicht wirklich sinnvoll sortiert zu sein. Ich nehme an, dass Feld 1 eine Art Status ist (das "OK", nach dem Sie suchen). Es wird also nach Datensatzstatus sortiert, dann nach TAG, dann nach MONAT, JAHR, STUNDEN, MINUTEN, SEKUNDEN. Wenn es Jahr, Monat, Tag war, denke ich, dass es dort einige Optimierungen geben könnte. Trotzdem könnte es sein, aber mein Gehirn geht gerade in eine andere Richtung.

Wenn es eine kleine Anzahl von doppelten Schlüsseln im Verhältnis zur Gesamtzahl der Zeilen gibt, denke ich, Ihre beste Wette ist es, die Datei zu reduzieren, die Ihr awk-Skript überspringt, um nur Schlüssel zu duplizieren (wie David said). Sie können die Datei auch vorverarbeiten, so dass nur die Zeilen/OK/vorhanden sind. Ich denke, ich würde dies mit einer Pipeline tun, wo das erste awk-Skript nur die Zeilen mit doppelten IDs ausgibt und das zweite awk-Skript im Grunde das obige ist, aber optimiert, um nicht nach/OK/zu suchen und mit dem Wissen, dass ein beliebiger Schlüssel vorhanden ist Zweitschlüssel.

Wenn Sie im Voraus wissen, dass alle oder die meisten Zeilen wiederholt Schlüssel haben, ist es wahrscheinlich nicht wert, damit zu tun. Ich würde in den sauren Apfel beißen und es in C schreiben. Tons mehr Zeilen Code, viel schneller als das awk-Skript.

Answer 4

Bei vielen Unixen können Sie sortieren, um nach einer bestimmten Spalte oder einem Feld zu sortieren. Wenn Sie also die Datei nach der ID und dann nach dem Datum sortieren, müssen Sie das assoziative Array nicht mehr anzeigen, wenn Sie zuletzt alle IDs gesehen haben. Der gesamte Kontext ist in der Reihenfolge der Datei vorhanden.

Auf meinem Mac, die GNU Art hat, ist es:

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

auf dem ID-Feld zu sortieren. Sie können auch nach einem zweiten Feld sortieren, indem Sie z. B. 8,3 statt NUR 2 Felder angeben. Ein unix-artiger time_t-Zeitstempel ist also möglicherweise keine schlechte Idee in der Datei - er ist einfach zu sortieren und speichert alle diese Datumsberechnungen. Auch, (zumindest in GNU awk) gibt es eine mktime function, die die time_t für Sie aus den Komponenten macht.

Answer 5

@AnotherHowie, dachte ich, die gesamte Vorverarbeitung könnte mit sort und uniq erfolgen. Das Problem ist, dass die Daten des OPs durch Kommata getrennt zu sein scheinen und (Solaris 8) uniq es nicht erlaubt, das Datensatz-Trennzeichen auf irgendeine Weise anzugeben, also gab es keine besonders saubere Möglichkeit, die Vorverarbeitung mit Standard-Unix-Werkzeugen durchzuführen. Ich glaube nicht, es schneller sein würde, so gehen sehen Ich bin nicht die genauen Möglichkeiten, aber man könnte so etwas wie tun:

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

Das ist nicht sehr gut, weil es grep für jede Zeile ein ausführt enthält Zweitschlüssel. Sie könnten wahrscheinlich die uniq-Ausgabe in eine einzige Regexp einmassieren, um sie an grep zu füttern, aber der Nutzen wäre nur bekannt, wenn das OP das erwartete Verhältnis von Zeilen mit verdächtigen doppelten Schlüsseln zu den gesamten Zeilen in der Datei posten würde.

Answer 6

Das klingt wie ein Job für eine tatsächliche Datenbank. Selbst etwas wie SQLite könnte dir hier ziemlich gut helfen. Das große Problem, das ich sehe, ist Ihre Definition von "innerhalb von 4 Stunden". Das ist ein Problem mit dem Sliding-Fenster, das heißt, Sie können nicht einfach alle Daten in 4-Stunden-Segmente quantisieren ... Sie müssen alle "nahen" Elemente für jedes andere Element separat berechnen. Pfui.