Entfernen Sie doppelte Zeilen, während Sie die Reihenfolge der Zeilen beibehalten

[root@server]# awk '!seen[$0]++' out.txt > cleaned
awk: (FILENAME=out.txt FNR=8547098) fatal error: internal error
Aborted
[root@server]#

Der "" Server "" verfügt über: 8 GByte RAM + 16 GByte SWAP, x> 300 GByte freien Speicherplatz, amd64, Desktop-CPU. Wissenschaftliches Linux 6.6. Nichts anderes läuft darauf, um LOAD zu machen. Awk bricht nach ein paar Sekunden ab. Out.txt ist ~ 1.6 GByte. GNU Awk 3.1.7.

Frage : Wie kann ich die doppelten Zeilen entfernen, während die Reihenfolge der Zeilen beibehalten wird? Groß- / Kleinschreibung ist auch wichtig, zB: "A" und "a" sind zwei verschiedene Zeilen, müssen es behalten. "A" und "a" sind jedoch doppelt vorhanden, nur das erste wird benötigt.

Antwort könnte in irgendetwas sein .. wenn awk nicht gut dafür ist .. dann perl / sed .. was könnte das Problem sein?

[root@server]# ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 61945
max locked memory       (kbytes, -l) 99999999
max memory size         (kbytes, -m) unlimited
open files                      (-n) 999999
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 99999999
cpu time               (seconds, -t) unlimited
max user processes              (-u) 61945
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited
[root@server]# 

Update: Ich habe es auf einem RHEL-Rechner versucht, es wird nicht abgebrochen, aber ich hatte keine Zeit, bis es fertig ist. Warum unterscheidet sich SL Linux nicht von RHEL?

Update: Ich versuche es mit einer virtuellen Ubuntu 14-Version. Soweit funktioniert es! Es ist kein Ulimit-Problem: mawk 1.3.3

root@asdf-VirtualBox:~# ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 51331
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 51331
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited
root@asdf-VirtualBox:~# 

Ich bezweifle, dass dies einen Unterschied bewirken wird, aber für den Fall, dass dies in Perl nicht anders ist:

perl -ne 'print if ++$k{$_}==1' out.txt

Wenn das Problem darin besteht, die eindeutigen Zeilen im Speicher zu behalten, tritt das gleiche Problem auf wie bei dem awkVersuch. Ein anderer Ansatz könnte also sein:

cat -n out.txt | sort -k2 -k1n  | uniq -f1 | sort -nk1,1 | cut -f2-

Wie es funktioniert:

1. In einem GNU-System cat -nwird jeder Zeile die Zeilennummer vorangestellt, gefolgt von einer gewissen Anzahl von Leerzeichen und einem <tab> -Zeichen. catleitet diese Eingabedarstellung an sort.

2. sortMit der -k2Option wird festgelegt, dass beim Sortieren nur die Zeichen vom zweiten Feld bis zum Ende der Zeile berücksichtigt und die sortFelder standardmäßig nach Leerzeichen (oder catden eingefügten Leerzeichen und dem <Tabulator> ) aufgeteilt werden .
   Wenn gefolgt -k1n, wird zuerst sortdas 2. Feld und dann - bei identischen -k2Feldern - das 1. Feld als numerisch sortiert betrachtet. Wiederholte Zeilen werden also in der Reihenfolge sortiert, in der sie erscheinen.

3. Die Ergebnisse werden weitergeleitet an uniq- wobei angegeben wird, dass das erste Feld ignoriert werden soll ( -f1- und auch durch Leerzeichen getrennt) - und was zu einer Liste eindeutiger Zeilen in der Originaldatei führt und an zurückgeleitet wird sort.
4. Dieses Mal wird sortdas erste Feld ( catdie eingefügte Zeilennummer) numerisch sortiert, wobei die Sortierreihenfolge auf den Wert in der Originaldatei zurückgesetzt und die Ergebnisse weitergeleitet werden cut.
5. Entfernt zuletzt cutdie Zeilennummern, die von eingefügt wurden cat. Dies geschieht, indem cutnur vom 2. Feld bis zum Ende der Zeile gedruckt wird (und cutdas Standardtrennzeichen ist ein <tab> -Zeichen) .

Um zu veranschaulichen:

$ cat file
bb
aa
bb
dd
cc
dd
aa
bb
cc
$ cat -n file | sort -k2 | uniq -f1 | sort -k1 | cut -f2-
bb
aa    
dd
cc

#!/usr/bin/perl 
use DB_File;
tie %h, 'DB_File';

while(<>){ not $h{$_} and print and $h{$_}=1 }

EDIT 1: Funktioniert es wirklich? (im Vergleich)

Sol1 : Terdon et all Schwartzian-transform-like one-liner
    cat -n _1 | sort -uk2 | sort -nk1 | cut -f2-

Sol2 : perl  + DB_File (this answer)
    perl dbfile-uniq _1

Sol3 : PO (John W. Gill solution has a similar behavior)
    awk '!seen[$0]++' _1

Sol4: Terdon perl
    perl -ne 'print if ++$k{$_}==1' _1

Fall 1 : 100_000_000 Zufallszahlen (jeweils 5 Stellen), 566 MByte, 31_212 verschiedene Werte:

$ while true ; do echo $RANDOM; done | head -100000000 > _1

Fall 2 : 50_000_000 Rand-Nummern (je 10 Stellen), 516 MByte, 48_351_464 verschiedene Werte:

$ shuf _1 |  sed 'N;s/\n/ /' > _11

(Die folgenden Zahlen sind nicht sehr genau):

┌────────┬────────┬────────────────┬────────┬──────┐
│        │ Sol1   │ Sol2           │ Sol3   │ Sol4 │
│        │ sort...│ perl DB        │ awk    │ perl │
├────────┼────────┼────────────────┼────────┼──────┤
│ case 1 │ 6m15   │ 6m17           │ 0m28   │ 0m28 │
├────────┼────────┼────────────────┼────────┴──────┤
│ case 2 │ 11m15  │ 81m44          │ out of memory │
├────────┼────────┼────────────────┼────────┬──────┤
│ case 2 │        │ 5m54 /cache=2G │        │      │
└────────┴────────┴────────────────┴────────┴──────┘

Sol2 mit Cache ist:

use DB_File;
use Fcntl ;

$DB_HASH->{'cachesize'} = 2000_000_000;
tie %h, 'DB_File', "_my.db", O_RDWR|O_CREAT|O_TRUNC, 0640, $DB_HASH;

while(<>){ not $h{$_} and print and $h{$_}=1 }

Sortieren kann auch optimiert werden, indem eine Option für die Cachegröße hinzugefügt wird (wird nicht ausgeführt).

Eine kurze Schlussfolgerung:

• sort ist ein fantastischer Befehl!

Ich habe benutzt

awk -v BINMODE=rw '!($0 in a){a[$0];print}' infile >> outfile

BINMODE = rw: um Zeilenende-Abschlusszeichen zufrieden zu stellen. (Ich lebe in einer gemischten Umgebung)

Logik ist einfach.

Wenn sich die aktuelle Zeile nicht im assoziativen Array befindet, fügen Sie sie dem assoziativen Array hinzu und drucken Sie sie zur Ausgabe aus.

Bei diesem Ansatz kann es zu Speicherbeschränkungen kommen. Bei sehr großen Dateien und Dateigruppen habe ich Variationen verwendet und den Dateispeicher verwendet, um die Einschränkungen zu umgehen.

Die ordnungserhaltende Semantik Ihres Problems hat eine wunderbare Eigenschaft: Sie können das Problem unterteilen. Sie können split -l 1000000die Eingabedatei bearbeiten. Die 1000000-Linien, die es produziert, haben lexikalisch geordnete Namen, was gut ist. dann vereinheitliche die Stücke; und dann (als zweiter Durchgang) vereinheitlichen Sie die Ausgaben von diesen.

Dies löst das Speichermangelproblem (durch Begrenzen des Speicherbedarfs) auf Kosten der Umwandlung in eine Multipass-Lösung.

Speziell:

Eingabedaten generieren:

$ cat make-uniqm-input.py
#!/usr/bin/env python
import random
n = 1000000
for i in xrange(0, n):
    print random.randint(1000, 2000)

$ python make-uniqm-input.py  > uniqm-input.txt

$ wc -l uniqm-input.txt
 1000000 uniqm-input.txt

Teilen Sie die Eingabedaten auf:

$ split -l 10000 uniqm-input.txt

$ ls x?? | head
xaa
xab
xac
xad
xae
xaf
xag
xah
xai
xaj

$ ls x?? | wc -l
     100

$ cat x?? | wc -l
 1000000

Führen Sie den Uniqifier auf einmal aus (behält alle eindeutigen Eingabezeilen im Speicher bei):

# 'uniqm' is any order-preserving uniq implementation, such as
# gawk '!counts[$0]++'.
$ uniqm < uniqm-input.txt > output-no-splitting.txt

$ wc -l output-no-splitting.txt
    1001 output-no-splitting.txt

Führen Sie den Uniqifier bei geteilten Teilen aus (behält nur eindeutige Eingabezeilen von jedem Teil im Speicher bei) und reduzieren Sie ihn dann als zweiten Durchgang:

$ for x in x??; do uniqm < $x; done | uniqm > output-with-splitting.txt

$ wc -l output-with-splitting.txt
    1001 output-with-splitting.txt

Vergleichen Sie:

$ diff output-no-splitting.txt output-with-splitting.txt

$ head uniqm-input.txt
1506
1054
1623
1002
1173
1400
1226
1340
1824
1091

$ head output-with-splitting.txt
1506
1054
1623
1002
1173
1400
1226
1340
1824
1091

Ich kenne das Verhältnis von eindeutigen zu nicht eindeutigen Zeilen in Ihrer Eingabe nicht und weiß auch nicht, wie gut die Eingabezeilen gemischt sind. Daher gibt es einige Optimierungen in Bezug auf die Anzahl der benötigten aufgeteilten Dateien.

Ein anderer Ansatz (der als separate Antwort veröffentlicht werden sollte) ist: Anstelle des Split-File-Ansatzes, bei dem temporäre Dateien erstellt werden, führen Sie die Stapelverarbeitung in der Uniqifier-Software selbst durch. Beispiel: Verwenden einer Ruby-Uniqifier-Implementierung zu Erläuterungszwecken:

require 'set'
line_batch_count = 50000 # tunable parameter
lines_seen = Set.new
line_number = 0
ARGF.each do |line|
   line_number += 1
   if (line_number % line_batch_count) == 0
     lines_seen.clear
   end
   unless lines_seen.include? line
      puts line
      lines_seen << line
   end
end

Die Idee ist, das Hash-Set von Zeit zu Zeit zu löschen. Dann wird dies iterativ:

$ cat uniqm-input.txt | ruby uniqm-capped.rb | wc -l
   20021

$ cat uniqm-input.txt | ruby uniqm-capped.rb | ruby uniqm-capped.rb | wc -l
    1001

$ cat uniqm-input.txt | ruby uniqm-capped.rb | ruby uniqm-capped.rb | head
1506
1054
1623
1002
1173
1400
1226
1340
1824
1091

Sie können diese begrenzte Version also so oft ausführen, bis sich die Zeilenanzahl von einer Iteration zur nächsten nicht mehr ändert.

Beachten Sie, dass diese capped-uniqm-Technik sprachunabhängig ist: Sie können das lines_seenArray alle N Zeilen löschen, unabhängig davon , ob Sie awk, Python, Perl, C ++ usw. verwenden. Für alle diese Sprachen gibt es set-clear-Methoden. Ich glaube awk, es deleteist nicht Standard, aber üblich.