Filtrar archivo por número de línea

17

Dado un archivo L con un número entero no negativo por línea y un archivo de texto F, ¿cuál sería una forma rápida de mantener solo esas líneas en F, cuyo número de línea aparece en el archivo L?

Ejemplo:

$ 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

Estoy buscando un comando que pueda manejar un archivo L con 500 millones o más entradas; el archivo L está ordenado numéricamente.

Nota: Estoy a mitad de camino de una implementación para un, command-in-questionpero me preguntaba si uno también podría usar algunas herramientas de Unix aquí.


Actualización: Gracias por todas las respuestas, ¡aprendí mucho hoy! Me gustaría aceptar más una respuesta, pero eso no es posible.

miku
fuente
¿Cuántas líneas hay en el archivo F?
Peter
1
Hay al menos tantas líneas en F como en L.
miku

Respuestas:

8

Al Comitir mensajes de error significativos:

#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;
    }
}
Flo Mismo
fuente
2
Esta es la respuesta más eficaz aquí. Al menos, así es por mis pruebas. En caso de que a alguien le interesa, he recopilado ella como: xsel -bo | cc -xc - -o cselect. Y simplemente funcionó: solo necesita las dos bibliotecas.
mikeserv
1
Gracias, esto es genial! Espero que no te importe, pero envolví tu código en una pequeña herramienta .
miku
1
@miku Adelante, me alegra haber podido ayudar. Noté que has aumentado LINE_MAXtu versión, por lo que probablemente trabajes con líneas muy grandes en tus archivos. He actualizado la A con una versión que usa getline()para eliminar el límite de tamaño de línea.
FloHelf
@FloHelf, bueno, gracias de nuevo:) De hecho, algunas líneas de entrada pueden exceder LINE_MAX, por lo que getlineparece correcto.
miku
10

Lo usaría awk, pero no almacenaría todo el contenido L.txten la memoria y haría búsquedas innecesarias de hash ;-).

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
fuente
Exactamente, probé hash-maps y superarían la memoria; los bitsets te comprarán más espacio para la cabeza; pero al usar el hecho de que la entrada está ordenada, puede deshacerse de este problema (espacio) por completo.
miku
1
@ Janis; no es solo un caso de buena práctica de codificación estándar: no codifique los literales, use variables en su lugar ... (más flexible y menos propenso a errores, y más fácil de mantener)
Peter
1
@ StéphaneChazelas: necesita inicialización pre-bucle de n, de lo contrario (como está) se echa de menos 1enL.txt
Peter.O
1
@ Peter.O, vaya, eso es lo que intenté abordar con NR> = n, pero eso estaba mal. Debería estar mejor ahora.
Stéphane Chazelas
1
@ Janis, la idea era que si ese código se incrustara en un command-in-questionscript, entonces no se puede tener el nombre de archivo incrustado en el código. -v list="$opt_x"tampoco funciona debido al procesamiento de barra invertida hecho por awk en él. Es por eso que uso ENVIRON en su lugar aquí.
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

Eso debería funcionar bastante rápido (algunas pruebas cronometradas se incluyen a continuación) con entradas de cualquier tamaño. Algunas notas sobre cómo:

  • export LC_ALL=C
    • Debido a que el objetivo de la siguiente operación es obtener todo el archivo ./Fapilado en línea con ./Lel archivo de lineno, los únicos caracteres de los que realmente tendremos que preocuparnos son los [0-9]dígitos ASCII y los :dos puntos.
    • Por esa razón, es más simple preocuparse por encontrar esos 11 caracteres en un conjunto de 128 posibles que si UTF-8 está involucrado de otra manera.
  • grep -n ''
    • Esto inserta la cadena LINENO:en el encabezado de cada línea en stdin - o <./F.
  • sort -t: -nmk1,1 ./L -
    • sortse niega a ordenar sus archivos de entrada en absoluto, y en su lugar (correctamente) presume que se han clasificado previamente y -mles Erges en -numericallyforma ordenada, ignorando básicamente cualquier cosa más allá de cualquier posible -k1,1que ocurre st -t:carácter de dos puntos de todos modos.
    • Si bien esto puede requerir cierto espacio temporal (dependiendo de qué tan separadas puedan estar algunas secuencias) , no requerirá mucho en comparación con un tipo adecuado, y será muy rápido porque implica un retroceso cero.
    • sortgenerará una sola secuencia donde cualquier entrada de lineno ./Lprecederá inmediatamente a las líneas correspondientes ./F. ./LLas líneas siempre vienen primero porque son más cortas.
  • sed /:/d\;n
    • Si la línea actual coincide con /:/dos puntos, delíjala de la salida. De lo contrario, imprima automáticamente la nlínea actual y la ext.
    • Y, por lo tanto, sedelimina sortla salida a solo pares de líneas secuenciales que no coinciden con dos puntos y la siguiente línea, o, solo a una línea desde ./Ly luego a la siguiente.
  • cut -sd: -f2-
    • cut -selimina de la salida los de sus líneas de entrada que no contienen al menos una de sus -d:cadenas de eliminación, y así ./Llas líneas se eliminan por completo.
    • Para aquellas líneas que lo hacen, su primer campo :delimitado por dos puntos -festá cutlejos, y así desaparecen todos greplos lineno insertados.

pequeña prueba de entrada

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

... genera 5 líneas de entrada de muestra. Luego...

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

...huellas dactilares...

==> 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

pruebas cronometradas más grandes

Creé un par de archivos bastante grandes:

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

... que ponen 5mil líneas /tmp/Fy 1.5mil líneas seleccionadas al azar de eso /tmp/L. Entonces hice:

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

Impreso:

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

(Agregué las barras invertidas allí)

Entre las soluciones que se ofrecen actualmente aquí, esta es la más rápida de todas, pero una cuando se enfrenta al conjunto de datos generado anteriormente en mi máquina. De los otros, solo uno estuvo cerca de competir por el segundo lugar, y ese es meuh perl aquí .

Esta no es de ninguna manera la solución original ofrecida: ha reducido un tercio de su tiempo de ejecución gracias a los consejos / inspiración ofrecidos por otros. Vea el historial de publicaciones para soluciones más lentas (pero ¿por qué?) .

Además, vale la pena señalar que algunas otras respuestas podrían contestar mejor si no fuera por la arquitectura de múltiples CPU de mi sistema y la ejecución concurrente de cada uno de los procesos en esa tubería. Todos trabajan al mismo tiempo, cada uno en su propio núcleo de procesador, pasando los datos y haciendo su pequeña parte del conjunto. Es genial.

pero la solución más rápida es ...

Pero no es la solución más rápida. La solución más rápida que aquí se ofrecen, las manos hacia abajo, es el programa C . Yo lo llamaba cselect. Después de copiarlo en mi portapapeles X, lo compilé como:

xsel -bo | cc -xc - -o cselect

Entonces hice:

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

... y los resultados fueron ...

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
fuente
1
Puede que sea significativamente más rápido (casi tan rápido como el mío en sistemas multi-núcleo) con el sed -ne'/:/!{n;p;}' | cut -d: -f2-lugar desed -ne'/:/!N;/\n/s/[^:]*://p'
Stéphane Chazelas
@ StéphaneChazelas: puede obtener mejores resultados si cambia seds, lo sedque estoy usando es la herencia sed, puede ver el aliasvalor en los timeresultados. Mi paquete de reliquia, por cierto, está compilado estáticamente contra un libl musl, cuya implementación de expresiones regulares se basa en TRE . Cuando lo cambio a GNU sed, y lo ejecuto sin cut, agrega un segundo completo al tiempo de finalización (2.8 segundos) , lo aumenta en más de un tercio. Y eso es solo 0,3 segundos más rápido que el tuyo en mi sistema.
mikeserv
1
sort -mnen lugar de sort -nmk1,1podría ser mejor ya que no es necesario dividir aquí (no probado)
Stéphane Chazelas
@ StéphaneChazelas: sí, pensé lo mismo y lo intenté de todas maneras. -nse especifica solo para hacer la primera cadena numérica en una línea, así que pensé, ok -mno -nmy, por cualquier razón, las únicas veces que se sumergió por debajo de 2 segundos en el tiempo de finalización fue cuando agregué todas las opciones tal como están. Es extraño, y es la razón por la que ayer no mencioné el tema -men primer lugar, sabía de qué se trataba, pero parecía funcionar como una especie de optimización automática. Curiosamente, la herencia sorttiene una -zopción de longitud de cadena que solo se aplica a -[cm]...
mikeserv
-nno es la primera cadena numérica en la línea . Simplemente considera la línea como un número, por abc 123lo que sería 0. Por lo tanto, no puede ser menos eficiente que con-t: -k1,1
Stéphane Chazelas
9

Yo usaría awk:

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

Actualización: he hecho medidas de rendimiento; parece que esta versión se escala aún mejor con conjuntos de datos muy grandes (como es el caso con los requisitos establecidos), ya que la comparación es muy rápida y compensa en exceso el esfuerzo necesario para construir la tabla hash.

Janis
fuente
1
@miku; Sí, es una buena solución compacta. Pero una advertencia; No todos los awks podrían manejar conjuntos de datos tan grandes. - Estoy usando GNU awky no hay problemas; La prueba con 500 millones de líneas de datos requirió 7 minutos.
Janis
1
Esto es bastante lento (en comparación) real 16m3.468s- user 15m48.447s- sys 0m10.725s. Usó 3.3 GB de RAM probando un tamaño de 1/10 ' Lcon 50,000,000 líneas; y Fcon 500,000,000 líneas - vs tiempo para la respuesta awk de Stéphane Chazelas: real 2m11.637s- user 2m2.748s- sys 0m6.424s- No estoy usando una caja rápida, pero la comparación es interesante.
Peter
@ Peter.O; Gracias por los datos! Era de esperar una velocidad más lenta, dado que (en mi propio caso de prueba) se almacenaron 500 millones de líneas en una matriz asociativa. (Es por eso que comenté "(+1)" más arriba para la propuesta de Stephane.) - ¡Aunque me sorprendió que esta solución concisa todavía procesara 1 millón de líneas por segundo! Creo que hace que este patrón de código (¡por su simplicidad!) Sea una opción viable, y específicamente en casos con tamaños de datos menos extremos.
Janis
Definitivamente es una solución viable. En los datos de prueba que utilicé (5mil líneas / 1.5mil L), los suyos se completaron en poco más de 4 segundos, solo un segundo detrás de la respuesta de Stephane. El código utilizado para generación del equipo de prueba está en mi respuesta, pero es más que nada seqde salida y luego un subconjunto más pequeño, seleccionados al azar de los mismos en L .
mikeserv
1
Acabo de hacer algunas medidas de rendimiento más con un tamaño de archivo de datos de 500 millones de líneas y un tamaño de archivo clave de 50 millones y resp. 500 millones de líneas, con una observación notable. Con el archivo de clave más pequeño, los tiempos son 4 min (Stephane) frente a 8 min (Janis), mientras que con el archivo de clave más grande son 19 min (Stephane) frente a 12 min (Janis).
Janis
3

Solo para completar: podemos fusionar el excelente guión awk en la respuesta de Stéphane Chazelas, y el guión perl en la respuesta de kos pero sin mantener toda la lista en la memoria, con la esperanza de que perl sea más rápido que awk. (He cambiado el orden de los argumentos para que coincida con la pregunta original).

#!/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
fuente
Esto es mucho más rápido que el awk. Es casi tan rápido como el mío: probé las dos veces en este momento y cada vez que el mío manejó mi conjunto de pruebas de línea de 5mil en 1.8 ... segundos y el suyo 1.9 ... segundos cada vez. El código gen de testset está en mi respuesta si te importa, pero el punto es que es muy bueno. Además, el resultado es correcto: todavía no puedo hacer el awktrabajo ... Sin embargo, ambas respuestas son avergonzadas por FloHimself's .
mikeserv
@mikeserv, debemos tener diferentes awks. En su muestra, obtengo 1.4s con gawk (4s para Janis '), 0.9s con mawk, 1.7s con esta solución perl, 2.3s con kos', 4.5s con la suya (GNU sed) y 1.4s con la suya ( GNU sed) y mi mejora sugerida (y 0.5s para la solución C).
Stéphane Chazelas
@mikeserv, ¡ah! Por supuesto, con su enfoque, la configuración regional marca la diferencia. Bajó de 4.5s a 2.3s aquí cuando cambia de UFT-8 a C.
Stéphane Chazelas
3

Escribí un script simple de Perl para hacer eso:

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 ++;
    }
}
  • Cargas F.txt
  • Cargas L.txt
  • Almacena cada línea de L.txten una matriz
  • Lee F.txtlínea por línea, rastreando su número de línea actual y el índice de matriz actual; aumenta el F.txtnúmero de línea actual; si el F.txtnúmero de línea actual coincide con el contenido de la matriz en el índice de la matriz actual, imprime la línea actual y aumenta el índice

Consideraciones de costo y complejidad :

Teniendo en cuenta el costo de realizar las asignaciones, el costo de hacer las comparaciones y el costo de imprimir las líneas, dado N 1 como el número de líneas F.txty N 2 como el número de líneas L.txt, el whileciclo se ejecuta como máximo N 1 veces, conduce a asignaciones de 2N 1 + N 2 (obviamente asumiendo N 1 > N 2 ), a comparaciones de 2N 1 y a impresiones de N 2 ; dado que es igual al costo de cada operación, el costo total para ejecutar el whileciclo es 4N 1 + 2N 2 , lo que conduce a una complejidad del script de O (N).

Prueba en un archivo de entrada de 10 millones de líneas :

Usando un F.txtarchivo de 10 millones de líneas que contiene líneas aleatorias de 50 caracteres y un L.txtarchivo de 10 millones de líneas que contiene números del 1 al 10000000 (peor de los casos):

~/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
fuente
2

Esta solución perl es más rápida que las otras soluciones awk o perl en un 20% más o menos, pero obviamente no es tan rápida como la solución 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 es compatible con Monica
fuente
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

Como L.txt está ordenado, puede usar join. Simplemente numere cada línea en F.txt, una los dos archivos y luego elimine el número de línea. No se necesitan archivos intermedios grandes.

En realidad, lo anterior destruirá sus líneas de datos al reemplazar todos los espacios en blanco por un solo espacio. Para mantener la línea intacta, debe elegir como delimitador algún carácter que no aparezca en sus datos, por ejemplo, "|". El cmd es entonces

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

El primer sed elimina los espacios iniciales de la salida "cat -n" y reemplaza la pestaña. El segundo sed elimina el número de línea y "|".

meuh
fuente
Me temo que esto no funcionará en archivos más grandes. Necesita <10 líneas. Tuve la misma idea y lo intenté, join L.txt <(nl F.txt )pero no funcionará en archivos grandes. ¡Bienvenido al sitio, por cierto, no es frecuente que obtengamos respuestas tan claras y bien formateadas de los nuevos usuarios!
terdon
@terdon, Sí, una pena que join/ commno puede funcionar con la entrada numéricamente ordenados.
Stéphane Chazelas
@terdon: Seguí tu pista (ahora eliminada) e intenté join -t' ' <(<L.txt awk '{printf("%010s\n",$0)}') <(<F.txt awk '{printf("%010s %s\n",NR,$0)}') | cut -d' ' -f2-. ¡Fue lento! - e incluso cuando introduje archivos preparados con teclas adecuadas con relleno de 0 join -t' ' L.txt F.txt | cut -d' ' -f2- , todavía fue lento (sin incluir el tiempo de preparación) - más lento que la awkrespuesta de @Janis (donde publiqué un comentario sobre los tiempos reales tomados para ambos respuesta de él y @ StéphaneChazelas
Peter.O
@ Peter.O sí. Intenté un enfoque similar que evita uno de los problemas pero no pude encontrar una manera de que funcione y valga la pena.
terdon
@terdon y otros: El tiempo real para la sustitución del procesojoin + fue vs Stéphane Chazelas ' usando 50 millones de líneas, 500 millones de líneas. awk printf real 20m11.663s user 19m35.093s sys 0m10.513sreal 2m11.637s user 2m2.748s sys 0m6.424sLF
Peter.O
0

Para completar, otro intento de joinsolución:

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

Esto funciona formateando la columna de número de línea que une funciona como una longitud fija con ceros a la izquierda, de modo que los números siempre tengan 15 dígitos. Esto evita el problema de que a la unión no le guste el orden numérico normal, ya que la columna se ha visto obligada a clasificarse en el diccionario. nlse usa para agregar números de línea en este formato a F.txt. Lamentablemente sed, debe usarse para volver a formatear la numeración en L.txt.

Este enfoque parece funcionar bien en los datos de prueba generados utilizando el método de @ mikeserv. Pero todavía es muy lento: la solución c es 60 veces más rápida en mi máquina. aproximadamente 2/3 del tiempo se gasta en sedy 1/3 en join. Quizás haya una mejor expresión sed ...

Trauma digital
fuente
Ok, pero ¿por qué estamos anteponiendo todos los ceros? Estoy tratando de tener una idea de esto. Además, nles súper genial, pero no puedes usarlo de manera sólida en entradas no probadas. Una de las cosas que lo hace tan genial es su eliminador de páginas -d lógico. Por defecto, si hay alguna línea en la entrada que consta solo de las cadenas :\` (pero sin la tumba final) 1, 2, 3 o tres veces seguidas, sus cuentas se volverán un poco locas. Experimente con él: es bastante bueno. Especialmente eche un vistazo a lo que sucede cuando nl` lee una línea con 1 cadena de delimitador y luego otra w / 3 o 2
mikeserv
0

Como la respuesta aceptada está en C, pensé que está bien lanzar una solución de Python aquí:

# 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 usa una biblioteca externa como numpy, una solución se vería aún más elegante:

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
fuente