Filtrer le fichier par numéro de ligne

17

Étant donné un fichier L avec un entier non négatif par ligne et un fichier texte F, quel serait un moyen rapide de conserver uniquement ces lignes dans F, dont le numéro de ligne apparaît dans le fichier L?

Exemple:

$ cat L.txt
1
3

$ cat F.txt
Hello World
Hallo Welt
Hola mundo

$ command-in-question -x L.txt F.txt
Hello World
Hola mundo

Je recherche une commande capable de gérer un fichier L avec 500 millions d'entrées ou plus; le fichier L est trié numériquement.

Remarque: je suis à mi-chemin d'une implémentation pour un, command-in-questionmais je me demandais simplement si on pouvait également utiliser certains outils Unix ici.


Mise à jour: Merci pour toutes les réponses, j'ai beaucoup appris aujourd'hui! J'aimerais accepter plus d'une réponse, mais ce n'est pas possible.

miku
la source
Combien de lignes y a-t-il dans le fichier F?
Peter.O
1
Il y a au moins autant de lignes en F qu'en L.
miku

Réponses:

8

En Comettant les messages d'erreur significatifs:

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {

    FILE *L;
    FILE *F;

    unsigned int to_print;
    unsigned int current = 0;
    char *line = NULL;
    size_t len = 0;

    if ((L = fopen(argv[1], "r")) == NULL) {
        return 1;
    } else if ((F = fopen(argv[2], "r")) == NULL) {
        fclose(L);
        return 1;
    } else {

        while (fscanf(L, "%u", &to_print) > 0) {
            while (getline(&line, &len, F) != -1 && ++current != to_print);
            if (current == to_print) {
                printf("%s", line);
            }
        }

        free(line);
        fclose(L);
        fclose(F);
        return 0;
    }
}
FloHimself
la source
2
C'est la réponse la plus performante ici. C'est du moins le cas par mes tests. Dans le cas où quelqu'un est intéressé, je compilé comme: xsel -bo | cc -xc - -o cselect. Et cela a juste fonctionné - il n'a besoin que des deux bibliothèques.
mikeserv
1
Merci, c'est super! J'espère que cela ne vous dérange pas, mais j'ai enveloppé votre code dans un petit outil .
miku
1
@miku Allez-y, je suis content d'avoir pu aider. J'ai remarqué que vous avez augmenté LINE_MAXvotre version, vous travaillez donc probablement avec de très grandes lignes dans vos fichiers. J'ai mis à jour le A avec une version utilisant getline()pour supprimer la limite de taille de ligne.
FloHimself
@FloHimself, eh bien, merci encore:) En effet, certaines lignes d'entrée peuvent dépasser LINE_MAX, getlinesemble donc juste.
miku
10

J'utiliserais awk, mais ne stockerais pas tout le contenu de la L.txtmémoire et ferais des recherches de hachage inutiles ;-).

list=L.txt file=F.txt
LIST="$list" awk '
  function nextline() {
    if ((getline n < list) <=0) exit
  }
  BEGIN{
    list = ENVIRON["LIST"]
    nextline()
  }
  NR == n {
    print
    nextline()
  }' < "$file"
Stéphane Chazelas
la source
Exactement, j'ai essayé des cartes de hachage et elles dépasseraient la mémoire; les ensembles de bits vous procureront plus de marge; mais en utilisant le fait que l'entrée est triée, vous pouvez vous débarrasser complètement de ce problème (d'espace).
miku
1
@Janis; n'est-ce pas juste un cas de bonne pratique de codage standard: ne
codez
1
@ StéphaneChazelas: Il a besoin de pré-initialisation boucle n, sinon (en l' état ) , il manque 1àL.txt
Peter.O
1
@ Peter.O, oups, c'est ce que j'avais essayé de résoudre avec NR> = n, mais c'était faux. Ça devrait être mieux maintenant.
Stéphane Chazelas
1
@Janis, l'idée était que si ce code devait être incorporé dans un command-in-questionscript, alors vous ne pouvez pas avoir le nom de fichier incorporé dans le code. -v list="$opt_x"ne fonctionne pas non plus à cause du traitement antislash effectué par awk dessus. C'est pourquoi j'utilise plutôt ENVIRON ici.
Stéphane Chazelas
10

grep -n | sort | sed | cut

(   export LC_ALL=C
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)   <./F

Cela devrait fonctionner assez rapidement (certains tests chronométrés sont inclus ci-dessous) avec une entrée de n'importe quelle taille. Quelques notes sur comment:

  • export LC_ALL=C
    • Parce que le point de l'opération suivante est d'obtenir le fichier entier ./Fempilé en ligne avec ./Lle fichier de son lineno, les seuls caractères dont nous devrons vraiment nous soucier sont les [0-9]chiffres ASCII et les :deux - points.
    • Pour cette raison, il est plus simple de s'inquiéter de trouver ces 11 caractères dans un ensemble de 128 possibles que si l'UTF-8 est autrement impliqué.
  • grep -n ''
    • Cela insère la chaîne LINENO:dans la tête de chaque ligne dans stdin - ou <./F.
  • sort -t: -nmk1,1 ./L -
    • sortnéglige de trier ses fichiers d'entrée, et au lieu de cela (correctement) présume qu'ils sont triés et les -mefface dans l' -numericallyordre trié, ignorant fondamentalement tout ce qui dépasse tout caractère de côlon -k1,1se produisant de -t:toute façon.
    • Bien que cela puisse nécessiter un peu d'espace temporaire (selon la distance à laquelle certaines séquences peuvent se produire) , cela ne demandera pas grand-chose par rapport à un tri approprié, et il sera très rapide car il n'implique aucun retour en arrière.
    • sortproduira un seul flux où n'importe quel lineno ./Lprécédera immédiatement les lignes correspondantes ./F. ./LLes lignes viennent toujours en premier car elles sont plus courtes.
  • sed /:/d\;n
    • Si la ligne actuelle correspond à /:/deux points, dsupprimez-la de la sortie. Sinon, imprimez automatiquement la ligne actuelle et la nligne ext.
    • Et ainsi de sedpruneaux sortsortie S » à seulement paires de lignes successives qui ne correspondent pas à deux points et la ligne suivante - ou, à seulement une ligne de ./Lpuis le lendemain.
  • cut -sd: -f2-
    • cut -ssupprime de la sortie celles de ses lignes d'entrée qui ne contiennent pas au moins une de ses -d:chaînes d'élimitation - et donc ./Lles lignes sont complètement élaguées.
    • Pour les lignes qui le font, leur premier champ :délimité par deux -fpoints est cutabsent - et il en va de même pour tous greples lineno insérés.

petit test d'entrée

seq 5 | sed -ne'2,3!w /tmp/L
        s/.*/a-z &\& 0-9/p' >/tmp/F

... génère 5 lignes d'entrée d'échantillon. Alors...

(   export LC_ALL=C; </tmp/F \
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)|  head - /tmp[FL]

... impressions ...

==> standard input <==
a-z 1& 0-9
a-z 4& 0-9
a-z 5& 0-9

==> /tmp/F <==
a-z 1& 0-9
a-z 2& 0-9
a-z 3& 0-9
a-z 4& 0-9
a-z 5& 0-9

==> /tmp/L <==
1
4
5

de plus grands tests chronométrés

J'ai créé quelques fichiers assez volumineux:

seq 5000000 | tee /tmp/F |
sort -R | head -n1500000 |
sort -n >/tmp/L

... qui a mis 5mil de lignes dedans /tmp/Fet 1,5mil de lignes sélectionnées aléatoirement dans /tmp/L. J'ai ensuite fait:

time \
(   export LC_ALL=C
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)   <./F |wc - l

Il a imprimé:

1500000
grep -n '' \
    0.82s user 0.05s system 73% cpu 1.185 total
sort -t: -nmk1,1 /tmp/L - \
    0.92s user 0.11s system 86% cpu 1.185 total
sed /:/d\;n \
    1.02s user 0.14s system 98% cpu 1.185 total
cut -sd: -f2- \
    0.79s user 0.17s system 80% cpu 1.184 total
wc -l \
    0.05s user 0.07s system 10% cpu 1.183 total

(J'ai ajouté les barres obliques inverses là-bas)

Parmi les solutions actuellement proposées ici, celle-ci est la plus rapide de toutes, sauf une lorsqu'elle est opposée à l'ensemble de données généré ci-dessus sur ma machine. Parmi les autres, un seul a failli prétendre à la deuxième place, et c'est perl ici meuh .

Ce n'est en aucun cas la solution originale proposée - elle a chuté d'un tiers de son temps d'exécution grâce aux conseils / inspiration offerts par d'autres. Voir l'historique des publications pour des solutions plus lentes (mais pourquoi?) .

En outre, il convient de noter que certaines autres réponses pourraient très bien lutter si ce n'était pour l'architecture multi-CPU de mon système et l'exécution simultanée de chacun des processus de ce pipeline. Ils travaillent tous en même temps - chacun sur son propre cœur de processeur - en contournant les données et en faisant leur petite partie de l'ensemble. C'est vraiment cool.

mais la solution la plus rapide est ...

Mais ce n'est pas la solution la plus rapide. La solution la plus rapide offerte ici, les mains vers le bas, est le programme C . Je l'ai appelé cselect. Après l'avoir copié dans mon presse-papiers X, je l'ai compilé comme:

xsel -bo | cc -xc - -o cselect

J'ai ensuite fait:

time \
    ./cselect /tmp/L /tmp/F |
wc -l

... et les résultats étaient ...

1500000
./cselect /tmp/L /tmp/F  \
    0.50s user 0.05s system 99% cpu 0.551 total
wc -l \
    0.05s user 0.05s system 19% cpu 0.551 total
mikeserv
la source
1
Vous pouvez le rendre beaucoup plus rapide (presque aussi rapide que le mien sur des systèmes multicœurs) avec sed -ne'/:/!{n;p;}' | cut -d: -f2-au lieu desed -ne'/:/!N;/\n/s/[^:]*://p'
Stéphane Chazelas
@ StéphaneChazelas - vous obtiendrez peut-être de meilleurs résultats si vous changez de seds - ce que sedj'utilise est l'héritage sed- vous pouvez voir la aliasvaleur dans les timerésultats. Soit dit en passant, mon package hérité est compilé statiquement sur une libl musl - l'implémentation regex pour laquelle est basée sur TRE . Lorsque je le passe au GNU sed- et que je l'exécute sans cut- cela ajoute une seconde complète au temps de réalisation (2,8 secondes) - l'aggrave de plus d'un tiers. Et c'est seulement 0,3 seconde plus rapide que la vôtre sur mon système.
mikeserv
1
sort -mnpar opposition à sort -nmk1,1peut-être mieux car vous n'avez pas besoin de faire le fractionnement ici (non testé)
Stéphane Chazelas
@ StéphaneChazelas - oui, j'ai pensé la même chose et je l'ai essayé dans tous les sens. -nest spécifié juste pour faire la première chaîne numérique sur une ligne, donc je me suis dit, ok -mnou -nmet, pour une raison quelconque, les seules fois où il est descendu en dessous de 2 secondes dans le temps de réalisation, c'est quand j'ai ajouté toutes les options telles quelles. C'est bizarre - et c'est la raison pour laquelle hier je n'ai pas abordé la question -men premier lieu - je savais de quoi je parlais, mais cela semblait fonctionner comme une sorte de chose d'auto-optimisation. Fait intéressant, l'héritage sorta une -zoption de longueur de chaîne qui ne s'applique qu'aux -[cm]....
mikeserv
-nn'est pas la première chaîne numérique de la ligne . Il considère simplement la ligne comme un nombre et abc 123serait donc 0. Donc, cela ne peut pas être moins efficace qu'avec-t: -k1,1
Stéphane Chazelas
9

J'utiliserais awk:

awk 'NR==FNR {a[$1]; next}; FNR in a' L.txt F.txt

Mise à jour: j'ai fait des mesures de performance; il semble que cette version évolue encore mieux avec des ensembles de données très volumineux (comme c'est le cas avec les exigences énoncées), car la comparaison est très rapide et compense l'effort nécessaire pour construire la table de hachage.

Janis
la source
1
@miku; Oui, c'est une belle solution compacte. Mais une mise en garde; tous awkne peuvent pas gérer de tels ensembles de données. - J'utilise GNU awket il n'y a aucun problème; le test avec 500 millions de lignes de données a nécessité 7 minutes.
Janis
1
C'est plutôt lent (par comparaison) real 16m3.468s- user 15m48.447s- sys 0m10.725s. Il a utilisé 3,3 Go de RAM pour tester une taille de 1 / 10e Lavec 50 000 000 lignes; et Favec 500 000 000 lignes - vs temps pour awk anser de Stéphane Chazelas: real 2m11.637s- user 2m2.748s- sys 0m6.424s- Je n'utilise pas de boîte rapide, mais la comparaison est intéressante.
Peter.O
@ Peter.O; Merci pour les données! Une vitesse plus lente était à prévoir, étant donné que (dans mon propre cas de test) un demi-milliard de lignes étaient stockées dans un tableau associatif. (C'est pourquoi j'ai commenté "(+1)" ci-dessus pour la proposition de Stéphane.) - Bien que j'étais étonné que cette solution laconique traitait toujours 1 million de lignes par seconde! Je pense que cela rend ce modèle de code (en raison de sa simplicité!) Une option viable, et en particulier dans les cas avec des tailles de données moins extrêmes.
Janis
C'est définitivement une solution viable. Sur les données de test que j'ai utilisées (5 mil lignes / 1,5 mil L), la vôtre a été complétée en un peu plus de 4 secondes - seulement une seconde derrière la réponse de Stéphane. Le code utilisé pour l'ensemble gen de test est dans ma réponse, mais il est surtout juste seqsortie et un plus petit, sous - ensemble de même choisi au hasard dans L .
mikeserv
1
Je viens de faire quelques mesures de performances supplémentaires avec une taille de fichier de données de 500 millions de lignes et une taille de fichier clé de 50 millions et resp. 500 millions de lignes, avec une observation notable. Avec le fichier clé plus petit, les temps sont de 4 min (Stéphane) contre 8 min (Janis), tandis qu'avec le fichier clé plus grand, c'est 19 min (Stéphane) vs 12 min (Janis).
Janis
3

Juste pour être complet: nous pouvons fusionner l'excellent script awk dans la réponse de Stéphane Chazelas, et le script perl dans la réponse de kos mais sans garder la liste entière en mémoire, dans l'espoir que perl soit plus rapide que awk. (J'ai changé l'ordre des arguments pour correspondre à la question d'origine).

#!/usr/bin/env perl
use strict;

die "Usage: $0 l f\n" if $#ARGV+1 != 2;
open(L,$ARGV[0]) or die "$ARGV[0]: $!";
open(F,$ARGV[1]) or die "$ARGV[1]: $!";

while(my $number = <L>){
    #chop $number;
    while (<F>) {
        if($. == $number){
            print;
            last;
        }
    }
}
meuh
la source
C'est bien plus rapide que le awk. Il est à peu près aussi rapide que le mien - j'ai testé les deux trois fois tout à l'heure et chaque fois que le mien a géré mon test de ligne de 5mil en 1,8 ... secondes et le vôtre 1,9 ... secondes à chaque fois. Le code gen de testset est dans ma réponse si vous vous en souciez, mais le fait est qu'il est très bon. De plus, la sortie est correcte - je ne peux toujours pas faire le awktravail ... Pourtant, nos deux réponses sont honteuses par FloHimself .
mikeserv
@mikeserv, nous devons avoir différents awks. Sur votre échantillon, j'obtiens 1,4s avec gawk (4s pour Janis '), 0,9s avec mawk, 1,7s avec cette solution perl, 2,3s avec kos', 4,5s avec le vôtre (GNU sed) et 1,4s avec le vôtre ( GNU sed) et mon amélioration suggérée (et 0,5 s pour la solution C).
Stéphane Chazelas
@mikeserv, ah! bien sûr avec votre approche, les paramètres régionaux font une différence. De 4.5s à 2.3s ici lors du passage de l'UFT-8 à C.
Stéphane Chazelas
3

J'ai écrit un simple script Perl pour cela:

Usage: script.pl inputfile_f inputfile_f

#!/usr/bin/env perl

$number_arguments = $#ARGV + 1;
if ($number_arguments != 2) {
    die "Usage: script.pl inputfile_f inputfile_l\n";
}

open($f, '<', $ARGV[0])
    or die "$ARGV[0]: Not found\n";
open($l, '<', $ARGV[1])
    or die "$ARGV[1]: Not found\n";

@line_numbers = <$l>;

while ($line = <$f>) {
    $count_f ++;
    if ($count_f == @line_numbers[$count_l]) {
        print $line;
        $count_l ++;
    }
}
  • Charges F.txt
  • Charges L.txt
  • Stocke chaque ligne de L.txtdans un tableau
  • Lit F.txtligne par ligne, en suivant son numéro de ligne actuel et l'index du tableau actuel; augmente le F.txtnuméro de ligne actuel; si le F.txtnuméro de ligne actuel correspond au contenu du tableau à l'index du tableau actuel, il imprime la ligne actuelle et augmente l'index

Considérations de coût et de complexité :

Considérant le coût pour effectuer les affectations, le coût pour faire les comparaisons et le coût pour imprimer les lignes, étant donné N 1 comme le nombre de lignes F.txtet N 2 comme le nombre de lignes L.txt, la whileboucle s'exécute au plus N 1 fois, conduisant à 2N 1 + N 2 affectations (en supposant évidemment N 1 > N 2 ), à 2N 1 comparaisons et à N 2 impressions; étant donné que le coût de chaque opération est égal, le coût total pour exécuter la whileboucle est de 4N 1 + 2N 2 , ce qui conduit à une complexité du script de O (N).

Testez sur un fichier d'entrée de 10 millions de lignes :

En utilisant un F.txtfichier de 10 millions de lignes contenant des lignes aléatoires de 50 caractères et un L.txtfichier de 10 millions de lignes contenant des nombres de 1 à 10000000 (pire scénario):

~/tmp$ for ((i=0; i<3; i++)); do time ./script.pl F.txt L.txt > output; done

real    0m15.628s
user    0m13.396s
sys 0m2.180s

real    0m16.001s
user    0m13.376s
sys 0m2.436s

real    0m16.153s
user    0m13.564s
sys 0m2.304s
kos
la source
2

Cette solution perl est plus rapide que les autres solutions awk ou perl de 20% environ, mais pas aussi vite que la solution en C.

perl -e '
  open L, shift or die $!;
  open F, shift or die $!;
  exit if ! ($n = <L>);
  while (1) {
    $_ = <F>;
    next if $. != $n;
    print;
    exit if ! ($n = <L>);
  }
' -- L F
jrw32982 prend en charge Monica
la source
0
cat <<! >L.txt
1
3
!

cat <<! >F.txt
Hello World
Hallo Welt
Hola mundo
!

cmd(){
 L=$1 F=$2
 cat -n $F |
 join $L - |
 sed 's/[^ ]* //'
}

cmd L.txt F.txt
Hello World
Hola mundo

Puisque L.txt est trié, vous pouvez utiliser join. Il suffit de numéroter chaque ligne dans F.txt, de joindre les deux fichiers, puis de supprimer le numéro de ligne. Aucun gros fichier intermédiaire n'est nécessaire.

En fait, ce qui précède va modifier vos lignes de données en remplaçant tous les espaces blancs par un seul espace. Pour garder la ligne intacte, vous devez choisir comme délimiteur un caractère qui n'apparaît pas dans vos données, par exemple "|". Le cmd est alors

cmd(){
 L=$1 F=$2
 cat -n $F |
 sed 's/^ *//;s/\t/|/' |
 join -t'|' $L - |
 sed 's/[^|]*|//'
}

Le premier sed supprime les espaces de tête de la sortie "cat -n" et remplace l'onglet. Le deuxième sed supprime le numéro de ligne et "|".

meuh
la source
Je crains que cela ne fonctionne pas sur des fichiers plus volumineux. Il a besoin de <10 lignes. J'ai eu la même idée et essayé, join L.txt <(nl F.txt )mais cela ne fonctionnera pas sur les gros fichiers. Bienvenue sur le site, d'ailleurs, ce n'est pas souvent que nous obtenons des réponses aussi claires et bien formatées de nouveaux utilisateurs!
terdon
@terdon, oui, une honte qui join/ commne peut pas fonctionner avec une entrée triée numériquement.
Stéphane Chazelas
@terdon: J'ai suivi votre piste (maintenant supprimée) et j'ai essayé join -t' ' <(<L.txt awk '{printf("%010s\n",$0)}') <(<F.txt awk '{printf("%010s %s\n",NR,$0)}') | cut -d' ' -f2-- C'était lent! - et même lorsque j'ai alimenté des fichiers préparés avec des touches 0 remplies appropriées join -t' ' L.txt F.txt | cut -d' ' -f2- , c'était toujours lent (sans compter le temps de préparation) - plus lent que la awkréponse de @Janis (où j'ai posté un commentaire sur les temps réels pris pour les deux sa et la réponse de @ StéphaneChazelas
Peter.O
@ Peter.O ouais. J'ai essayé une approche similaire qui évite l'un des problèmes, mais je n'ai pas trouvé de moyen de le faire fonctionner et en valait la peine.
terdon
@terdon et autres: Le temps réel pour la substitution du processusjoin + était vs Stéphane Chazelas en utilisant 50 millions de lignes, 500 millions de lignes. awk printf real 20m11.663s user 19m35.093s sys 0m10.513sreal 2m11.637s user 2m2.748s sys 0m6.424sLF
Peter.O
0

Pour être complet, une autre tentative de joinsolution:

sed -r 's/^/00000000000000/;s/[0-9]*([0-9]{15})/\1/' /tmp/L | join <( nl -w15 -nrz /tmp/F ) - | cut -d' ' -f2-

Cela fonctionne en formatant la colonne de numéro de ligne qui joint fonctionne comme une longueur fixe avec des zéros non significatifs, de sorte que les nombres comportent toujours 15 chiffres. Cela contourne le problème de jointure n'aimant pas l'ordre de tri numérique normal, car la colonne a effectivement été forcée d'être un tri par dictionnaire. nlest utilisé pour ajouter des numéros de ligne dans ce format à F.txt. Malheureusement, seddoit être utilisé pour reformater la numérotation dans L.txt.

Cette approche semble fonctionner correctement sur les données de test générées à l'aide de la méthode de @ mikeserv. Mais c'est encore très lent - la solution c est 60 fois plus rapide sur ma machine. environ 2/3 du temps est passé sedet 1/3 po join. Il y a peut-être une meilleure expression sed ...

Traumatisme numérique
la source
Ok - mais pourquoi ajoutons-nous tous les zéros? J'essaie de comprendre cela. Aussi, c'est nlsuper cool, mais vous ne pouvez pas l'utiliser de manière robuste sur des entrées non testées. L'une des choses qui le rend si cool est son séparateur de pages logique -d . Par défaut, s'il y a une ligne en entrée composée uniquement des cordes :\` (mais sans le grave arrière) 1, 2, 3 ou trois fois de suite, vos décomptes deviendront un peu fous. Expérimentez avec - c'est assez soigné. En particulier, regardez ce qui se passe lorsque nl` lit une ligne avec 1 chaîne de délimiteur, puis un autre avec 3 ou 2
mikeserv
0

Étant donné que la réponse acceptée est en C, je me suis dit que c'était OK de lancer une solution python ici:

# Read mask
with open('L.txt', 'r') as f:
    mask = [int(line_num) for line_num in f.read().splitlines()]

# Filter input file
filtered_lines = []
with open('F.txt', 'r') as f:
    for i, line in enumerate(f.read().splitlines()):
        if (i+1) in mask:
            filtered_lines.append(line)

# Write newly filtered file
with open('F_filtered.txt', 'w') as f:
    for line in filtered_lines:
        f.write('%s\n' % line)

Si vous utilisez une bibliothèque externe comme numpy, une solution serait encore plus élégante:

import numpy as np

with open('L.txt', 'r') as f:
    mask = np.array([int(line_num)-1 for line_num in f.read().splitlines()])

with open('F.txt', 'r') as f:
    lines = np.array(f.read().splitlines())
filtered_lines = lines[mask]

with open('F_filtered.txt', 'w') as f:
    for line in filtered_lines:
        f.write('%s\n' % line)
AlexG
la source