Ordenar el contenido de un archivo de texto extremadamente grande (800 GB) en Windows

Tengo un archivo de texto con una palabra en cada línea, el tamaño del archivo es de 800 GB. Necesito ordenar las palabras alfabéticamente.

He intentado usar el programa de ordenación de Windows usando:

sort.exe input.txt /o output.txt

lo que da el error: No hay suficiente memoria principal para completar el ordenamiento.

Tengo 32 GB de RAM, así que cuando trato de especificar 10 GB de memoria para el tipo usando:

sort.exe input.txt /o output.txt /M 10000000

Yo obtengo:

Advertencia: el tamaño de memoria especificado se reduce a la memoria de paginación disponible.

El registro de entrada excede la longitud máxima. Especificar máximo más grande.

¿Cuáles son mis opciones?

¿Cuáles son mis opciones?

Pruebe Freeware Command Line Sort Utility CMSort .

Utiliza varios archivos temporales y luego los combina al final.

CMsort está leyendo registros de un archivo de entrada hasta que se alcanza la memoria ajustada. Luego, los registros se ordenan y escriben en un archivo temporal. Esto se repetirá hasta que se procesen todos los registros. Finalmente, todos los archivos temporales se fusionan en el archivo de salida. Si la memoria disponible es suficiente, no se escriben archivos temporales y no es necesaria la fusión.

Un usuario informa que ordenó un archivo de 130,000,000 bytes.

Si desea ajustar algún código usted mismo, también hay Ordenar archivos de texto enormes - CodeProject - "Algoritmo de líneas de clasificación en archivos de texto cuyo tamaño excede la memoria disponible"

Otra opción es cargar el archivo en una base de datos. EG MySQL y MySQL Workbench.
Las bases de datos son candidatas perfectas para trabajar con archivos grandes

Si su archivo de entrada contiene solo palabras separadas por una nueva línea, esto no debería ser demasiado difícil.

Después de haber instalado la base de datos y MySQL Workbench, esto es lo que debe hacer.
Primero cree el esquema (esto supone que las palabras no serán más largas que 255 caracteres, aunque podría alterar esto aumentando el valor del argumento). La primera columna "idwords" es una clave primaria.

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

En segundo lugar, importe los datos: EG Esto importará todas las palabras en la tabla (este paso puede tardar un tiempo en completarse. Mi consejo sería ejecutar primero una prueba con un pequeño archivo de palabras y una vez que esté seguro de que el formato es el mismo que el más grande (truncar la tabla. IE Borrarlo y cargar el conjunto de datos completo).

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);

Este enlace puede ayudar a obtener el formato correcto para la carga. https://dev.mysql.com/doc/refman/5.7/en/load-data.html
EG Si necesita omitir la primera línea, haría lo siguiente.

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

Finalmente guarde el archivo ordenado. Esto puede tomar un tiempo también dependiendo de su PC.

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

También puede buscar los datos a voluntad como lo desee. EG Esto le dará las primeras 50 palabras en orden ascendente (comenzando desde la 0 o primera palabra).

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

Buena suerte
pete

sort

Hay muchos algoritmos utilizados para ordenar los archivos ordenados y no ordenados ^{[ 1 ]} .
Como todos esos algoritmos ya están implementados, elija un programa ya probado.

En coreutils (de Linux pero también disponible para Windows ^{[ 2 ]} ), existe el sortcomando capaz de ejecutarse en paralelo bajo procesadores multi-core: generalmente es suficiente.

Si su archivo es tan grande , puede ayudar al procesamiento de división ( split -l), el archivo en algunos fragmentos, posiblemente utilizando la opción paralela ( --parallel), y ordenando los fragmentos ordenados resultantes con la -mopción ( ordenar por fusión ). Aquí
se explica una de las muchas formas de hacerlo (dividir archivos, ordenar fragmentos individuales, fusionar fragmentos ordenados, eliminar archivos temporales).

Notas:

• En Windows 10 existe el llamado Subsistema de Windows para Linux en el que todos los ejemplos de Linux parecerán más naturales.
• Ordenar con diferentes algoritmos tiene diferentes tiempos de ejecución que se escalan en función del número de entradas de datos que se ordenarán (O (n ^m ), O (nlogn) ...).
• La eficiencia del algoritmo depende del orden que ya está presente en el archivo original.
  (Por ejemplo, una clasificación de burbujas es el algoritmo más rápido para un archivo ya ordenado, exactamente N, pero no es eficiente en otros casos).

Para ofrecer una solución alternativa a Peter H, hay un programa q que permite comandos de estilo SQL contra archivos de texto. El siguiente comando haría lo mismo (ejecutar desde el símbolo del sistema en el mismo directorio que el archivo), sin necesidad de instalar SQL Workbench o crear tablas.

q "select * from words.txt order by c1"

c1 es la abreviatura de la columna 1.

Puede excluir palabras duplicadas con

q "select distinct c1 from words.txt order by c1"

y enviar la salida a otro archivo

q "select distinct c1 from words.txt order by c1" > sorted.txt

Si las palabras en cada línea provienen de un vocabulario limitado (como el inglés), puede ordenar la lista en O (n + m log m) usando un TreeMap y registrando los recuentos (donde m es el número de valores únicos).

De lo contrario, puede utilizar el gran clasificador de la biblioteca java . Divide la entrada en archivos intermedios ordenados y los fusiona eficientemente (O general (nlogn)). Para ordenar su archivo se ve así:

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

Creé un archivo de 1.7GB (100m líneas) con palabras de 16 caracteres generadas aleatoriamente y las ordené como se indica arriba en 142s y en base a la complejidad computacional O (n log n) del método que estoy usando. Calculo que 800GB de palabras de 16 caracteres Tardo unas 24 horas en ordenar un solo subproceso en mi computadora portátil i5 2.3GHz con SSD.