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-question
pero 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.
Respuestas:
Al
C
omitir mensajes de error significativos:fuente
xsel -bo | cc -xc - -o cselect
. Y simplemente funcionó: solo necesita las dos bibliotecas.LINE_MAX
tu versión, por lo que probablemente trabajes con líneas muy grandes en tus archivos. He actualizado la A con una versión que usagetline()
para eliminar el límite de tamaño de línea.LINE_MAX
, por lo quegetline
parece correcto.Lo usaría
awk
, pero no almacenaría todo el contenidoL.txt
en la memoria y haría búsquedas innecesarias de hash ;-).fuente
n
, de lo contrario (como está) se echa de menos1
enL.txt
command-in-question
script, 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í.grep -n | sort | sed | cut
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
./F
apilado en línea con./L
el archivo de lineno, los únicos caracteres de los que realmente tendremos que preocuparnos son los[0-9]
dígitos ASCII y los:
dos puntos.grep -n ''
LINENO:
en el encabezado de cada línea en stdin - o<./F
.sort -t: -nmk1,1 ./L -
sort
se niega a ordenar sus archivos de entrada en absoluto, y en su lugar (correctamente) presume que se han clasificado previamente y-m
les Erges en-numerically
forma ordenada, ignorando básicamente cualquier cosa más allá de cualquier posible-k1,1
que ocurre st-t:
carácter de dos puntos de todos modos.sort
generará una sola secuencia donde cualquier entrada de lineno./L
precederá inmediatamente a las líneas correspondientes./F
../L
Las líneas siempre vienen primero porque son más cortas.sed /:/d\;n
/:/
dos puntos,d
elíjala de la salida. De lo contrario, imprima automáticamente lan
línea actual y la ext.sed
eliminasort
la 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./L
y luego a la siguiente.cut -sd: -f2-
cut
-s
elimina 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í./L
las líneas se eliminan por completo.:
delimitado por dos puntos-f
estácut
lejos, y así desaparecen todosgrep
los lineno insertados.pequeña prueba de entrada
... genera 5 líneas de entrada de muestra. Luego...
...huellas dactilares...
pruebas cronometradas más grandes
Creé un par de archivos bastante grandes:
... que ponen 5mil líneas
/tmp/F
y 1.5mil líneas seleccionadas al azar de eso/tmp/L
. Entonces hice:Impreso:
(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:Entonces hice:
... y los resultados fueron ...
fuente
sed -ne'/:/!{n;p;}' | cut -d: -f2-
lugar desed -ne'/:/!N;/\n/s/[^:]*://p'
sed
s, losed
que estoy usando es la herenciased
, puede ver elalias
valor en lostime
resultados. 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 GNUsed
, y lo ejecuto sincut
, 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.sort -mn
en lugar desort -nmk1,1
podría ser mejor ya que no es necesario dividir aquí (no probado)-n
se especifica solo para hacer la primera cadena numérica en una línea, así que pensé, ok-mn
o-nm
y, 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-m
en primer lugar, sabía de qué se trataba, pero parecía funcionar como una especie de optimización automática. Curiosamente, la herenciasort
tiene una-z
opción de longitud de cadena que solo se aplica a-[cm]
...-n
no es la primera cadena numérica en la línea . Simplemente considera la línea como un número, porabc 123
lo que sería 0. Por lo tanto, no puede ser menos eficiente que con-t: -k1,1
Yo usaría
awk
: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.
fuente
awk
s podrían manejar conjuntos de datos tan grandes. - Estoy usando GNUawk
y no hay problemas; La prueba con 500 millones de líneas de datos requirió 7 minutos.real 16m3.468s
-user 15m48.447s
-sys 0m10.725s
. Usó 3.3 GB de RAM probando un tamaño de 1/10 'L
con 50,000,000 líneas; yF
con 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.seq
de salida y luego un subconjunto más pequeño, seleccionados al azar de los mismos en L .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).
fuente
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 elawk
trabajo ... Sin embargo, ambas respuestas son avergonzadas por FloHimself's .awk
s. 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).Escribí un script simple de Perl para hacer eso:
Usage: script.pl inputfile_f inputfile_f
F.txt
L.txt
L.txt
en una matrizF.txt
línea por línea, rastreando su número de línea actual y el índice de matriz actual; aumenta elF.txt
número de línea actual; si elF.txt
nú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 índiceConsideraciones 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.txt
y N 2 como el número de líneasL.txt
, elwhile
ciclo 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 elwhile
ciclo 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.txt
archivo de 10 millones de líneas que contiene líneas aleatorias de 50 caracteres y unL.txt
archivo de 10 millones de líneas que contiene números del 1 al 10000000 (peor de los casos):fuente
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.
fuente
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
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 "|".
fuente
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!join
/comm
no puede funcionar con la entrada numéricamente ordenados.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 0join -t' ' L.txt F.txt | cut -d' ' -f2-
, todavía fue lento (sin incluir el tiempo de preparación) - más lento que laawk
respuesta de @Janis (donde publiqué un comentario sobre los tiempos reales tomados para ambos respuesta de él y @ StéphaneChazelasjoin
+ 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.513s
real 2m11.637s user 2m2.748s sys 0m6.424s
L
F
Para completar, otro intento de
join
solución: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.
nl
se usa para agregar números de línea en este formato a F.txt. Lamentablementesed
, 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
sed
y 1/3 enjoin
. Quizás haya una mejor expresión sed ...fuente
nl
es 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 2Como la respuesta aceptada está en C, pensé que está bien lanzar una solución de Python aquí:
Si usa una biblioteca externa como numpy, una solución se vería aún más elegante:
fuente