Tengo ~ 30k archivos. Cada archivo contiene ~ 100k líneas. Una línea no contiene espacios. Las líneas dentro de un archivo individual se ordenan y no se duplican.

Mi objetivo: quiero encontrar todas las líneas duplicadas en dos o más archivos y también los nombres de los archivos que contienen entradas duplicadas.

Una solución simple sería esta:

cat *.words | sort | uniq -c | grep -v -F '1 '

Y luego correría:

grep 'duplicated entry' *.words

¿Ves una manera más eficiente?

Como todos los archivos de entrada ya están ordenados, podemos omitir el paso de clasificación real y simplemente usarlo sort -mpara fusionar los archivos.

En algunos sistemas Unix (que yo sepa, solo Linux), puede ser suficiente

sort -m *.words | uniq -d >dupes.txt

para obtener las líneas duplicadas escritas en el archivo dupes.txt.

Para encontrar de qué archivos provienen estas líneas, puede hacer

grep -Fx -f dupes.txt *.words

Esto le indicará grepque trate las líneas en dupes.txt( -f dupes.txt) como patrones de cadena fijos ( -F). greptambién requerirá que toda la línea coincida perfectamente de principio a fin ( -x). Imprimirá el nombre del archivo y la línea al terminal.

Unices no Linux (o incluso más archivos)

En algunos sistemas Unix, los nombres de los archivos 30000 se expandirán a una cadena que es demasiado larga para pasar a una sola utilidad (lo sort -m *.wordsque significa que fallará Argument list too long, lo que hace en mi sistema OpenBSD). Incluso Linux se quejará de esto si la cantidad de archivos es mucho mayor.

Encontrando a los engañados

Esto significa que en el caso general (esto también funcionará con muchos más que solo 30000 archivos), uno tiene que "fragmentar" la clasificación:

rm -f tmpfile
find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

Alternativamente, creando tmpfilesin xargs:

rm -f tmpfile
find . -type f -name '*.words' -exec sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh {} +

Esto encontrará todos los archivos en el directorio actual (o debajo) cuyos nombres coincidan *.words. Para un fragmento de estos nombres de tamaño apropiado a la vez, cuyo tamaño está determinado por xargs/ find, los fusiona en el tmpfilearchivo ordenado . Si tmpfileya existe (para todos menos el primer fragmento), este archivo también se fusiona con los otros archivos en el fragmento actual. Dependiendo de la longitud de sus nombres de archivo y la longitud máxima permitida de una línea de comando, esto puede requerir más o mucho más de 10 ejecuciones individuales del script interno ( find/ xargslo hará automáticamente).

El shguión "interno" ,

if [ -f tmpfile ]; then
    sort -o tmpfile -m tmpfile "$@"
else
    sort -o tmpfile -m "$@"
fi

se usa sort -o tmpfilepara enviar a tmpfile(esto no se sobrescribirá tmpfileincluso si esto también es una entrada para sort) y -mpara hacer la fusión. En ambas ramas, "$@"se expandirá a una lista de nombres de archivos entre comillas individuales pasados ​​al script desde findo xargs.

A continuación, basta con ejecutar uniq -den tmpfileobtener toda la línea que se duplican:

uniq -d tmpfile >dupes.txt

Si le gusta el principio "SECO" ("No se repita"), puede escribir el guión interno como

if [ -f tmpfile ]; then
    t=tmpfile
else
    t=/dev/null
fi

sort -o tmpfile -m "$t" "$@"

o

t=tmpfile
[ ! -f "$t" ] && t=/dev/null
sort -o tmpfile -m "$t" "$@"

¿De dónde vienen ellos?

Por las mismas razones que anteriormente, no podemos usar grep -Fx -f dupes.txt *.wordspara encontrar de dónde provienen estas duplicaciones, así que en su lugar, usamos findnuevamente:

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt {} +

Como no hay que realizar un procesamiento "complicado", podemos invocar grepdirectamente desde -exec. La -execopción toma un comando de utilidad y colocará los nombres encontrados {}. Con +al final, findcolocará tantos argumentos en lugar de {}los que admite el shell actual en cada invocación de la utilidad.

Para ser totalmente correcto, uno puede usar cualquiera

find . -type f -name '*.words' \
    -exec grep -H -Fx -f dupes.txt {} +

o

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt /dev/null {} +

para asegurarse de que los nombres de archivo siempre se incluyan en la salida de grep.

La primera variación se usa grep -Hpara generar siempre nombres de archivo coincidentes. La última variación utiliza el hecho de que grepincluirá el nombre del archivo coincidente si se proporciona más de un archivo en la línea de comando.

Esto es importante ya que la última parte de los nombres de archivo enviados grepdesde findpuede contener solo un nombre de archivo único, en cuyo caso grepno lo mencionaría en sus resultados.

Material de bonificación:

Diseccionando el comando find+ xargs+ sh:

find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

find . -type f -name '*.words'simplemente generará una lista de nombres de ruta desde el directorio actual (o debajo) donde cada nombre de ruta es el de un archivo normal ( -type f) y que tiene un componente de nombre de archivo al final que coincide *.words. Si solo se busca el directorio actual , se puede agregar -maxdepth 1después del ., antes -type f.

-print0garantizará que todos los nombres de ruta encontrados se muestren con un carácter \0( nul) como delimitador. Este es un carácter que no es válido en una ruta de Unix y nos permite procesar nombres de ruta incluso si contienen caracteres de nueva línea (u otras cosas extrañas).

findcanaliza su salida a xargs.

xargs -0leerá la \0lista de nombres de ruta delimitada y ejecutará la utilidad dada repetidamente con fragmentos de estos, asegurando que la utilidad se ejecute con suficientes argumentos para no hacer que el shell se queje de una lista de argumentos demasiado larga, hasta que no haya más entradas de find.

La utilidad invocada por xargses shcon un script dado en la línea de comando como una cadena usando su -cbandera.

Al invocar sh -c '...some script...'con los siguientes argumentos, los argumentos estarán disponibles para el script $@, excepto el primer argumento , que se colocará $0(este es el "nombre del comando" en el que puede detectar, por ejemplo, topsi es lo suficientemente rápido). Es por eso que insertamos la cadena shcomo el primer argumento después del final del script real. La cadena shes un argumento ficticio y podría ser cualquier palabra (algunos parecen preferir _o sh-find).

Las líneas dentro de un archivo individual se ordenan y no se duplican.

Lo que significa que probablemente pueda encontrar algún uso para sort -m:

 -m, --merge
        merge already sorted files; do not sort

La otra alternativa obvia para hacer esto sería awkrecolectar las líneas en una matriz y contarlas. Pero como comentó @ dave_thompson_085 , esos 3 000 millones de líneas (o las muchas que haya) probablemente requerirán una cantidad considerable de memoria para almacenar, por lo que puede que no funcione muy bien.

Con awk puede obtener todas las líneas repetidas en todos los archivos en un comando corto:

$ awk '_[$0]++' *.words

Pero repetirá líneas si existe una línea 3 o más veces.
Hay una solución para obtener solo el primer duplicado:

$ awk '_[$0]++==1' *.words

Debería ser bastante rápido (si las repeticiones son pocas) pero consumirá mucha memoria para mantener todas las líneas en la memoria. Tal vez, dependiendo de sus archivos y repeticiones reales, intente primero con 3 o cuatro archivos.

$ awk '_[$0]++==1' [123]*.words

De lo contrario, puedes hacer:

$ sort -m *.words | uniq -d

Lo que imprimirá líneas repetidas uniq.

Solución optimizada sort+ uniq:

sort --parallel=30000 *.words | uniq -d

• --parallel=N - cambie el número de tipos ejecutados simultáneamente a N
• -d, --repeated - solo imprime líneas duplicadas, una para cada grupo