El UNIX sort comando puede ordenar un archivo muy grande como este:

sort large_file

Cómo es el tipo de algoritmo implementado?

¿Cómo es que no causa el consumo excesivo de memoria?

  • Esto es muy interesante. Realmente no sé cómo funciona, pero tengo una conjetura. Probablemente pone el primer carácter de cada una clave en un árbol binario, y cuando hay una colisión, se utiliza el siguiente carácter de la clave también, lo que no guarda más de la clave de lo que necesita. Se puede guardar un desplazamiento en el archivo con cada una de las teclas de manera que puede buscar e imprimir cada línea en orden.
  • En realidad, @ayaz es más interesante si usted no está de clasificación de un archivo en el disco, sino más bien en una tubería, ya que se hace obvio que no se puede simplemente hacer varias pasadas sobre los datos de entrada.
  • ¿Por qué todo el mundo en TAN siento tan impulsados a adivinar todo el tiempo?
  • Usted puede hacer varias pasadas en la entrada – sólo necesita leer toda la entrada, escribir a disco y, a continuación, ordenar el archivo de disco.
  • por el contexto parece evidente que él estaba tratando de ordenar el contenido del archivo que no se el nombre del archivo (que para un nombre sin sentido). Sólo quería mejorar la pregunta sin cambiar el contexto demasiado, por lo que iba a obtener respuestas en lugar de downvotes debido a un simple error.
  • mi punto fue que el uso de la tubería se hace obvio que usted no tiene acceso al archivo original y el ingenuo de implementaciones que hacer varias pasadas sobre los datos de entrada no funciona. Que hace la pregunta (y su aplicación) más interesante.
  • de hecho, esto es un error, lo siento mucho por este error
  • estás diciendo que eso no es un partmaps.org/era/unix/award.html ?
  • unix.stackexchange.com/questions/120096/how-to-sort-big-files

InformationsquelleAutor yjfuk | 2009-05-30

7 Comentarios

  1. 106

    La Detalles algorítmicos de UNIX comando Sort dice Unix Ordenar los usos Externos de I-Modo de mezcla algoritmo de ordenación. El vínculo entra en más detalles, pero en esencia se divide la entrada en pequeñas porciones (que caben en la memoria) y, a continuación, combina cada porción juntos al final.

  2. 42

    La sort comando almacena datos de trabajo en temporal en el disco de archivos (normalmente en /tmp).

    • uso -T para especificar la temp dir
  3. 13

    ADVERTENCIA: Esta secuencia de comandos se inicia un shell por porción, para archivos muy grandes, esto podría ser cientos.


    Aquí es un guión que escribí para este propósito. En un 4 procesador de la máquina de la mejora, el tipo de rendimiento al 100% !

    #! /bin/ksh
    
    MAX_LINES_PER_CHUNK=1000000
    ORIGINAL_FILE=$1
    SORTED_FILE=$2
    CHUNK_FILE_PREFIX=$ORIGINAL_FILE.split.
    SORTED_CHUNK_FILES=$CHUNK_FILE_PREFIX*.sorted
    
    usage ()
    {
         echo Parallel sort
         echo usage: psort file1 file2
         echo Sorts text file file1 and stores the output in file2
         echo Note: file1 will be split in chunks up to $MAX_LINES_PER_CHUNK lines
         echo  and each chunk will be sorted in parallel
    }
    
    # test if we have two arguments on the command line
    if [ $# != 2 ]
    then
        usage
        exit
    fi
    
    #Cleanup any lefover files
    rm -f $SORTED_CHUNK_FILES > /dev/null
    rm -f $CHUNK_FILE_PREFIX* > /dev/null
    rm -f $SORTED_FILE
    
    #Splitting $ORIGINAL_FILE into chunks ...
    split -l $MAX_LINES_PER_CHUNK $ORIGINAL_FILE $CHUNK_FILE_PREFIX
    
    for file in $CHUNK_FILE_PREFIX*
    do
        sort $file > $file.sorted &
    done
    wait
    
    #Merging chunks to $SORTED_FILE ...
    sort -m $SORTED_CHUNK_FILES > $SORTED_FILE
    
    #Cleanup any lefover files
    rm -f $SORTED_CHUNK_FILES > /dev/null
    rm -f $CHUNK_FILE_PREFIX* > /dev/null

    Vea también:
    «Clasificación de archivos de gran tamaño más rápido con un script de shell«

    • Sólo puede utilizar la especie –paralelo de N como de GNU especie de versión 8.11
    • GNU coreutils 8.6 realidad
    • Esto lo hizo el truco para mí. Tengo una especie de 8.4 versión. El uso de ordenar directamente en el archivo (190 millones de líneas) se va no se donde. Este programa lo hice con poco menos de 4 minutos
    • de nuevo, esta respuesta no tiene nada que ver con la pregunta
    • Este script es peligroso. Mi máquina Linux perdido de respuesta después de lanzar cientos de ordenar los procesos de…
    • eso es lo que me estaba mirando. Si el archivo de entrada se divide en 100 archivos, entonces se comenzará 100 sort -u en el bucle for!
    • Yo uso el tipo todo el tiempo, el uso de la memoria / hora de la toma nunca ha sido un problema. Mezclado por completo de la lista de 5,509,041 url con el parámetro cadenas ordenadas de forma exclusiva en 0m10.539s

  4. 11
    #!/bin/bash
    
    usage ()
    {
        echo Parallel sort
        echo usage: psort file1 file2
        echo Sorts text file file1 and stores the output in file2
    }
    
    # test if we have two arguments on the command line
    if [ $# != 2 ]
    then
        usage
        exit
    fi
    
    pv $1 | parallel --pipe --files sort -S512M | parallel -Xj1 sort -S1024M -m {} ';' rm {} > $2
    • Esto es excelente. No era consciente de que existía un paralelismo paquete ! Ordenar el tiempo mejoró más que el 50% después de usar el anterior. Gracias.
    • He intentado utilizar el comm de diff de los archivos generados por este y su darme advertencia de que los archivos no están ordenadas.
  5. 5

    Mirar con cuidado las opciones de ordenación para acelerar el rendimiento y entender su impacto en su máquina y el problema.
    Los parámetros clave en Ubuntu son

    • Ubicación de los archivos temporales -T directory_name
    • Cantidad de memoria a usar-S N% ( N% de toda la memoria a usar, y cuanto más, mejor, pero
      evitar el exceso de suscripción que hace que el intercambio de disco. Se puede utilizar como una «-S del 80%», para usar el 80% de la memoria RAM disponible, o «-S 2G» por 2 GB de memoria RAM.)

    El interrogador pregunta «¿por Qué no el uso de memoria alta?» La respuesta viene de la historia, antiguas máquinas unix eran pequeñas y el defecto de memoria de tamaño pequeño. El ajuste de este tan grande como sea posible para que su carga de trabajo para mejorar enormemente tipo de rendimiento. Establecer el directorio de trabajo a un lugar en su dispositivo más rápido que tiene espacio suficiente para albergar al menos 1,25 * el tamaño del archivo que se ordena.

    • intentar esto en un 2,5 GB de archivos, en una caja con 64GB de RAM con -S 80%, es usando ese porcentaje, a pesar de que todo el archivo es más pequeño que eso. ¿por qué es eso? incluso si no se utiliza una especie que parece gratuito
    • Probablemente especie -S pre-asigna la memoria para el proceso de ordenación, incluso antes de leer el contenido del archivo.
  6. -3

    De memoria no debería ser un problema – tipo ya se encarga de eso. Si desea hacer un uso óptimo de su multi-core CPU tengo implementend esta en un pequeño script (similar a la de algunos de ustedes podrían encontrar en la red, pero más simple/limpiador de que la mayoría de esas ;)).

    #!/bin/bash
    # Usage: psort filename <chunksize> <threads>
    # In this example a the file largefile is split into chunks of 20 MB.
    # The part are sorted in 4 simultaneous threads before getting merged.
    # 
    # psort largefile.txt 20m 4    
    #
    # by h.p.
    split -b $2 $1 $1.part
    suffix=sorttemp.`date +%s`
    nthreads=$3
    i=0
    for fname in `ls *$1.part*`
    do
        let i++
        sort $fname > $fname.$suffix &
        mres=$(($i % $nthreads))
        test "$mres" -eq 0 && wait
    done
    wait
    sort -m *.$suffix 
    rm $1.part*
    • Interesante script, pero no hace nada para responder a esta pregunta.
    • split -b se divide en bytes, por lo tanto truncar las líneas en una posición arbitraria

Dejar respuesta

Please enter your comment!
Please enter your name here