Usuń zduplikowane linie, zachowując ich kolejność

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

„Serwer” ma: 8 GB RAM + 16 GB SWAP, x> 300 GB wolnego miejsca, amd64, procesor na pulpicie. Scientific Linux 6.6. Nic więcej na nim nie działa, aby wykonać OBCIĄŻENIE. Awk przerywa po kilku sekundach. Out.txt wynosi ~ 1,6 GB. GNU Awk 3.1.7.

Pytanie : Jak mogę usunąć zduplikowane linie, zachowując ich kolejność? Ważna jest także sprawa, np. „A” i „a” to dwie różne linie, musisz je zachować. Ale „a” i „a” są zduplikowane, potrzebny jest tylko pierwszy.

Odpowiedź może być w czymkolwiek ... jeśli awk nie jest do tego dobry ... to perl / sed .. jaki może być problem?

[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]# 

Aktualizacja: Próbowałem tego na maszynie RHEL, nie przerywa, ale nie miałem czasu czekać na zakończenie. Dlaczego linux SL różni się od RHEL?

Aktualizacja: Próbuję wirtualnego zgadywania w Ubuntu 14 .. do tej pory działa! To nie jest problem ulimit: 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:~# 

Wątpię, czy to coś zmieni, ale tak na wszelki wypadek, oto jak zrobić to samo w Perlu:

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

Jeśli problemem jest utrzymywanie unikalnych linii w pamięci, będzie to ten sam problem, co awkpróbowano. Innym podejściem może być:

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

Jak to działa:

1. W systemie GNU cat -nwstawi numer wiersza do każdego wiersza po pewnej ilości spacji, a po nim znak <tab> . catpotokuje tę reprezentację wejściową do sort.

2. sort„s -k2opcja instruuje go tylko do rozważenia postacie z drugiego pola, aż do końca linii podczas sortowania i sortDzieli pola domyślnie white-space (lub cat” y wstawione spacje i <Tab> ) .
   Po którym następuje -k1n, sortnajpierw rozważa drugie pole, a następnie - w przypadku identycznych -k2pól - pierwsze pole, ale posortowane numerycznie. Tak więc powtarzane wiersze zostaną posortowane razem, ale w kolejności, w jakiej się pojawiły.

3. Wyniki są przesyłane potokowo do uniq- do którego należy zignorować pierwsze pole ( -f1- a także jako oddzielone spacją) - i który powoduje powstanie listy unikalnych linii w oryginalnym pliku i jest przesyłany z powrotem do sort.
4. Tym razem sortsortuje się według pierwszego pola ( catnumer wstawionego wiersza) numerycznie, przywracając porządek sortowania z powrotem do tego, co było w oryginalnym pliku i przesyłając wyniki cut.
5. Na koniec cutusuwa numery linii, które zostały wstawione cat. Odbywa się to poprzez cutdrukowanie tylko od 2. pola do końca wiersza ( cutdomyślnym ogranicznikiem jest znak <tab> ) .

Ilustrować:

$ 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 }

EDYCJA 1: Czy to naprawdę działa? (porównując)

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

Przypadek 1 : 100_000_000 liczb losowych (po 5 cyfr), 566 MB, 31_212 różnych wartości:

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

Przypadek 2 : 50_000_000 liczb losowych (po 10 cyfr), 516 MB, 48_351_464 różne wartości:

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

(następujące liczby nie są bardzo dokładne):

┌────────┬────────┬────────────────┬────────┬──────┐
│        │ 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 z pamięcią podręczną to:

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 }

Sortowanie można również zoptymalizować, dodając opcję buforowania (nie zrobione).

Jeden szybki wniosek:

• sort to fantastyczne polecenie!

Użyłem

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

BINMODE = rw: aby zadowolić terminatory końca linii. (Mieszkam w mieszanym środowisku OS)

Logika jest prosta.

Jeśli bieżący wiersz nie znajduje się w tablicy asocjacyjnej, dodaj go do tablicy asocjacyjnej i wypisz na wyjście.

Przy takim podejściu mogą występować ograniczenia pamięci. W przypadku bardzo dużych plików i zestawów plików użyłem różnych wariantów tego, używając pamięci plików, aby ominąć ograniczenia.

Zachowująca porządek semantyka twojego problemu ma cudowną właściwość: możesz podzielić problem. Możesz to zrobić split -l 1000000na pliku wejściowym; 1000000 wierszy, które produkuje, ma uporządkowane leksykalnie nazwy, co jest dobre; następnie ujednolic kawałki; a następnie (w drugim przejściu) ujednolicić wyniki tych.

Rozwiązuje to problem braku pamięci (poprzez ograniczenie zapotrzebowania na pamięć) kosztem przekształcenia go w rozwiązanie wielopasmowe.

Konkretnie:

Generuj dane wejściowe:

$ 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

Podziel dane wejściowe:

$ 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

Uruchom uniqifier naraz (zachowuje wszystkie unikalne linie wejściowe w pamięci):

# '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

Uruchom unifikator na podzielonych elementach (zachowuje tylko unikalne linie wejściowe z każdego elementu w pamięci), a następnie zmniejsz jako drugi przebieg:

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

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

Porównać:

$ 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

Nie znam stosunku linii unikatowych do nieunikalnych w twoim wejściu ani tego, jak dobrze wymieszane są linie wejściowe - więc jest pewne dostrojenie, jeśli chodzi o liczbę potrzebnych plików podzielonych.

Innym podejściem (wartym opublikowania jako osobnej odpowiedzi) jest: zamiast podejścia podzielonego pliku, który tworzy pliki tymczasowe, wykonaj wsadowanie w obrębie samego oprogramowania uniqifier. Na przykład za pomocą implementacji unikatowego Ruby w celach wyjaśniających:

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

Chodzi o to, aby co jakiś czas usuwać zestaw skrótów. To staje się iteracyjne:

$ 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

Możesz więc wielokrotnie uruchamiać tę ograniczoną wersję, dopóki liczba wierszy nie zmieni się z jednej iteracji do następnej.

Zauważ, że ta technika capped-uniqm jest niezależna od języka: możesz wyczyścić lines_seentablicę co N wierszy, niezależnie od tego, czy korzystasz z awk, python, perl, C ++ itp. Istnieją metody ustawiania jasności dla wszystkich tych języków; Wierzę, że awkjest deleteto nietypowe, ale powszechne.