Supprimez les lignes en double tout en conservant l'ordre des lignes

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

Le "" serveur "" a: 8 Go de RAM + 16 Go de SWAP, x> 300 Go d'espace libre, amd64, CPU de bureau. Scientific Linux 6.6. Rien d'autre ne tourne dessus pour faire de la CHARGE. Awk s'interrompt après quelques secondes. Out.txt fait ~ 1,6 Go. GNU Awk 3.1.7.

Question : Comment puis-je supprimer les lignes en double tout en conservant l'ordre des lignes? La casse est aussi importante, ex: "A" et "a" sont deux lignes différentes, faut la garder. Mais "a" et "a" est en double, seul le premier est nécessaire.

La réponse pourrait être dans n'importe quoi .. si awk n'est pas bon pour cela .. alors perl / sed .. quel pourrait être le problème?

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

Mise à jour: J'ai essayé cela sur une machine RHEL, cela n'interrompt pas, mais je n'ai pas eu le temps d'attendre qu'elle se termine. Pourquoi SL SL Linux ne diffère-t-il pas de RHEL?

Mise à jour: J'essaie un gues virtuel Ubuntu 14 .. jusqu'à présent ça marche! Ce n'est pas un problème ultime : 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:~# 

Je doute que cela fasse une différence, mais au cas où, voici comment faire la même chose en Perl:

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

Si le problème est de conserver les lignes uniques en mémoire, cela aura le même problème que celui que awkvous avez essayé. Ainsi, une autre approche pourrait être:

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

Comment ça fonctionne:

1. Sur un système GNU, cat -najoutera le numéro de ligne à chaque ligne en suivant une certaine quantité d'espaces et suivi d'un caractère <tab> . catredirige cette représentation d'entrée vers sort.

2. sortL' -k2option lui indique de ne considérer que les caractères du deuxième champ jusqu'à la fin de la ligne lors du tri, et sortdivise les champs par défaut sur les espaces blancs (ou catles espaces insérés et <tab> ) .
   Lorsqu'il est suivi de -k1n, sortconsidère le premier champ en premier, puis deuxièmement - dans le cas de -k2champs identiques - il considère le 1er champ mais comme trié numériquement. Les lignes répétées seront donc triées ensemble mais dans l'ordre où elles sont apparues.

3. Les résultats sont redirigés vers uniq- auquel il est dit d'ignorer le premier champ ( -f1- et également séparés par des espaces) - et qui se traduit par une liste de lignes uniques dans le fichier d'origine et est redirigé vers sort.
4. Cette fois, sorttrie numériquement le premier champ ( catle numéro de ligne inséré) , ramenant l'ordre de tri à ce qu'il était dans le fichier d'origine et redirige ces résultats cut.
5. Enfin, cutsupprime les numéros de ligne insérés par cat. Ceci est effectué en cutimprimant uniquement à partir du 2ème champ jusqu'à la fin de la ligne (et cutle délimiteur par défaut est un caractère <tab> ) .

Pour illustrer:

$ 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: ça marche vraiment? (comparant)

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

Cas 1 : 100_000_000 nombres aléatoires (5 chiffres chacun), 566 Mo, 31_212 valeurs différentes:

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

Cas 2 : 50_000_000 rands (10 chiffres chacun), 516 Mo, 48_351_464 valeurs différentes:

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

(les chiffres suivants ne sont pas très précis):

┌────────┬────────┬────────────────┬────────┬──────┐
│        │ 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 avec cache est:

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 }

Le tri peut également être optimisé en ajoutant une option de taille de cache (non effectuée).

Une conclusion rapide:

• sort est une commande fantastique!

J'ai utilisé

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

BINMODE = rw: pour satisfaire les terminateurs de fin de ligne. (Je vis dans un environnement de système d'exploitation mixte)

La logique est simple.

Si la ligne actuelle n'est pas dans le tableau associatif, ajoutez-la au tableau associatif et imprimez-la en sortie.

Il peut y avoir des limitations de mémoire avec cette approche. Pour les fichiers et les ensembles de fichiers très volumineux, j'ai utilisé des variantes à ce sujet, en utilisant le stockage de fichiers pour dépasser les limites.

La sémantique préservant l'ordre de votre problème a une merveilleuse propriété: vous pouvez subdiviser le problème. Vous pouvez le faire split -l 1000000sur le fichier d'entrée; les pièces de 1000000 lignes qu'il produit ont des noms lexicaux, ce qui est bien; puis uniqifiez les pièces; puis (comme deuxième passage) unifier les sorties de ceux-ci.

Cela résout le problème de mémoire insuffisante (en plafonnant les besoins en mémoire) au détriment de le transformer en une solution multipass.

Plus précisément:

Générez des données d'entrée:

$ 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

Répartissez les données d'entrée:

$ 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

Exécutez uniqifier en une seule fois (conserve toutes les lignes d'entrée uniques en mémoire):

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

Exécutez l'uniqifier sur les pièces séparées (ne conserve que les lignes d'entrée uniques de chaque pièce en mémoire), puis réduisez-les en deuxième passage:

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

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

Comparer:

$ 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

Je ne connais pas le rapport entre les lignes uniques et non uniques dans votre entrée, ni la façon dont les lignes d'entrée sont bien mélangées - il y a donc un réglage à faire en termes de nombre de fichiers divisés dont vous avez besoin.

Une autre approche (qui vaut la peine d'être publiée comme réponse distincte) est la suivante: au lieu de l'approche du fichier fractionné qui crée des fichiers temporaires, faites le traitement par lots dans le logiciel uniqifier lui-même. Par exemple, en utilisant une implémentation Ruby uniqifier à des fins explicatives:

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

L'idée est d'effacer le jeu de hachage de temps en temps. Cela devient alors itératif:

$ 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

Vous pouvez donc exécuter cette version plafonnée à plusieurs reprises, jusqu'à ce que le nombre de lignes ne change pas d'une itération à la suivante.

Notez que cette technique capped-uniqm est indépendante du langage: vous pouvez effacer le lines_seentableau toutes les N lignes, que vous utilisiez awk, python, perl, C ++, etc. Il existe des méthodes set-clear pour tous ces langages; Je crois que celui awk-ci deleteest non standard mais commun.