☰

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

tag-icon • tag-icon windows sorting
Ordene el contenido de un archivo de texto extremadamente grande (800 GB) en Windows

tengo untextoarchivo 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 elventanas clasificarprograma usando:

sort.exe input.txt /o output.txt

lo que da el error:No hay suficiente memoria principal para completar la clasificación.

tengo 32gb deRAMentonces, cuando intento 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 está reduciendo a la memoria de paginación disponible.

El registro de entrada excede la longitud máxima. Especifique un máximo mayor.

¿Cuáles son mis opciones?

Respuesta1

¿Cuáles son mis opciones?

IntentarUtilidad gratuita de clasificación de línea de comandos 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 clasifican 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 necesario fusionarlos.

Un usuario informa que clasificó un archivo de 130.000.000 de bytes.

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

Respuesta2

Otra opción es cargar el archivo en una base de datos. Por ejemplo, MySQL y MySQL Workbench.
Las bases de datos son candidatos perfectos 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 deberá hacer.

Primero, cree el esquema (esto supone que las palabras no tendrán más de 255 caracteres, aunque puede modificarlo aumentando el valor del argumento).

La primera columna "idwords" es una clave principal.

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.
Por ejemplo, esto importará todas las palabras a la tabla; Este paso puede tardar un poco en completarse. Mi consejo sería ejecutar una prueba con un archivo más pequeño primero y una vez que esté seguro de que el formato es el mismo que el más grande (truncar la tabla... es decir, borrarla 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 conseguir el formato adecuado para la carga. https://dev.mysql.com/doc/refman/5.7/en/load-data.html

Por ejemplo, si necesitara 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 tardar un poco 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 que desee.
Por ejemplo, esto le dará las primeras 50 palabras en orden ascendente (comenzando desde la posición cero o la primera palabra).

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

Respuesta3

sort

Existen muchos algoritmos que se utilizan para ordenar archivos ordenados y no ordenados [1] .
Como todos esos algoritmos ya están implementados, elija un programa que ya haya sido probado.

Encoreutils (desde Linux pero disponible también para Windows [2] ), existe un sortcomando capaz de ejecutarse en paralelo en procesadores multinúcleo: normalmente es suficiente.

Si su archivo estan enormePuede ayudar al procesamiento dividiendo ( split -l), el archivo en algunos fragmentos, posiblemente usando la opción paralela ( --parallel), y ordenando el resultado.trozos-ordenadoscon la -mopción (fusionar ordenar).
Se explica una de las muchas formas de hacerlo.aquí(dividir archivos, ordenar fragmentos individuales, fusionar fragmentos ordenados, eliminar archivos temporales).

Notas:

  • En Windows 10 existe el llamadoSubsistema de Windows para Linuxen el que todo el ejemplo de Linux te parecerá más natural.
  • La clasificación con diferentes algoritmos tiene diferentes tiempos de ejecución que escalan en función del número de entradas de datos a clasificar (O(n m ), O(nlogn)...).
  • La eficiencia del algoritmo depende del orden que ya está presente en el archivo original.
    (Por ejemplo unordenamiento de burbujaes el algoritmo más rápido para un archivo ya ordenado (exactamente N), pero no es eficiente en otros casos).

Respuesta4

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

De lo contrario puedes usar la biblioteca java.clasificador grande. Divide la entrada en archivos intermedios ordenados y los combina de manera eficiente (O (nlogn) general). Para ordenar su archivo se ve así:

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

Creé un archivo de 1,7 GB (100 millones de líneas) con palabras de 16 caracteres generadas aleatoriamente y lo clasifiqué como se indica arriba en 142 y, según la complejidad computacional O (n log n) del método que estoy usando, calculo que 800 GB de palabras de 16 caracteres serían Me toma aproximadamente 24 horas ordenar un solo subproceso en mi computadora portátil i5 de 2,3 GHz con SSD.

información relacionada