La forma más rápida de sumr enteros en un archivo de texto

Pregunta

Supongamos que tiene un archivo de texto ASCII grande, con un entero aleatorio no negativo en cada línea, cada uno en el rango de 0 a 1,000,000,000. Hay 100,000,000 líneas en el archivo. ¿Cuál es la forma más rápida de leer el archivo y calcular la sum de todos los enteros?

Restricción: tenemos 10MB de RAM para trabajar. El archivo tiene 1 GB de tamaño, por lo que no queremos leer todo y luego procesarlo.

Aquí hay varias soluciones que he probado. Los resultados me parecieron bastante sorprendentes.

¿Hay algo más rápido que me he perdido?

Tenga en cuenta: todos los tiempos dados a continuación son para ejecutar el algoritmo 10 veces en total (ejecutar una vez y descartar, iniciar el temporizador, ejecutar 10 veces, detener el temporizador). La máquina es un Core 2 Duo bastante lento.

Método 1: el enfoque natural

Lo primero que debes probar es el enfoque obvio:

private long sumLineByLine() throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new FileReader(file)); String line; long total = 0; while ((line = br.readLine()) != null) { int k = Integer.parseInt(line); total += k; } br.close(); return total; } 

Tenga en cuenta que el máximo valor de retorno posible es 10 ^ 17, que todavía se ajusta fácilmente en un long , por lo que no tenemos que preocuparnos por los desbordamientos.

En mi máquina, ejecutar esto 11 veces y descontar la primera carrera lleva alrededor de 92,9 segundos .

Método 2: un pequeño ajuste

Inspirado por un comentario sobre esta pregunta , traté de no crear una nueva int k para almacenar el resultado de analizar la línea, y en su lugar simplemente agregar el valor analizado directamente al total . Así que esto:

  while ((line = br.readLine()) != null) { int k = Integer.parseInt(line); total += k; } 

se convierte en esto:

  while ((line = br.readLine()) != null) total += Integer.parseInt(line); 

Estaba seguro de que esto no supondría ninguna diferencia, y pensé que era muy probable que el comstackdor generara el mismo bytecode para las dos versiones. Pero, para mi sorpresa, se tomó un poco de tiempo libre: hemos bajado a 92.1 segundos .

Método 3: analizar manualmente el entero

Una cosa que me molesta sobre el código hasta ahora es que convertimos el String en un int y luego lo agregamos al final. ¿No sería más rápido agregar a medida que avanzamos? ¿Qué pasa si analizamos el String nosotros mismos? Algo como esto…

 private long sumLineByLineManualParse() throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new FileReader(file)); String line; long total = 0; while ((line = br.readLine()) != null) { char chs[] = line.toCharArray(); int mul = 1; for (int i = chs.length - 1; i >= 0; i--) { char c = chs[i]; switch (c) { case '0': break; case '1': total += mul; break; case '2': total += (mul << 1); break; case '4': total += (mul << 2); break; case '8': total += (mul << 3); break; default: total += (mul*((byte) c - (byte) ('0'))); } mul*=10; } } br.close(); return total; } 

Esto, pensé, podría ahorrar un poco de tiempo, especialmente con algunas optimizaciones de bitshift para hacer la multiplicación. Pero los gastos generales de la conversión a una matriz de caracteres deben inundar cualquier ganancia: ahora esto demora 148.2 segundos .

Método 4: procesamiento en binario

Una última cosa que podemos intentar es procesar el archivo como datos binarios.

Analizar un número entero desde el frente es incómodo si no conoce su longitud. Analizarlo al revés es mucho más fácil: el primer dígito que encuentras son unidades, el siguiente es decenas, y así sucesivamente. Entonces, la manera más fácil de abordar todo es leer el archivo al revés.

Si asignamos un búfer de byte[] de (digamos) 8MB, podemos llenarlo con los últimos 8MB del archivo, procesarlo, luego leer los 8MB precedentes, y así sucesivamente. Tenemos que tener un poco de cuidado para no arruinar un número que estamos en medio del análisis cuando pasamos al bloque siguiente, pero ese es el único problema.

Cuando encontramos un dígito, lo agregamos (adecuadamente multiplicado según su posición en el número) al total, y luego multiplicamos el coeficiente por 10, así que estamos listos para el siguiente dígito. Si encontramos algo que no sea un dígito (un CR o LF), simplemente reiniciamos el coeficiente.

 private long sumBinary() throws IOException { RandomAccessFile raf = new RandomAccessFile(file, "r"); int lastRead = (int) raf.length(); byte buf[] = new byte[8*1024*1024]; int mul = 1; long total = 0; while (lastRead>0) { int len = Math.min(buf.length, lastRead); raf.seek(lastRead-len); raf.readFully(buf, 0, len); lastRead-=len; for (int i=len-1; i>=0; i--) { //48 is '0' and 57 is '9' if ((buf[i]>=48) && (buf[i]<=57)) { total+=mul*(buf[i]-48); mul*=10; } else mul=1; } } raf.close(); return total; } 

¡Esto funciona en 30.8 segundos ! Eso es un aumento de velocidad en un factor de 3 sobre el mejor anterior.

Preguntas de seguimiento

  1. ¿Por qué es esto mucho más rápido? Esperaba que ganara, pero no tan impresionantemente. ¿Son principalmente los gastos generales de la conversión a una String ? ¿Y todas las preocupaciones tras bambalinas sobre los conjuntos de personajes y cosas por el estilo?
  2. ¿Podemos hacer algo mejor que esto usando MappedByteBuffer para ayudar? Tengo la sensación de que los gastos generales de invocar métodos para leer desde el búfer desacelerarían las cosas, especialmente cuando se lee hacia atrás desde el búfer.
  3. ¿Sería mejor leer el archivo hacia adelante en lugar de hacia atrás, pero aún escanear el buffer hacia atrás? La idea sería leer el primer trozo del archivo y luego escanear hacia atrás, pero descartando el medio número al final. Luego, cuando lea el siguiente fragmento, configure el desplazamiento para que lea desde el principio del número que descartó.
  4. ¿Hay algo que no haya pensado que pueda hacer una diferencia significativa?

Actualización: resultados más sorprendentes

Primero, una observación. Me debería haber ocurrido antes, pero creo que la razón de la ineficacia de la lectura basada en String no es tanto el tiempo necesario para crear todos los objetos String sino el hecho de que son de corta duración: tenemos 100,000,000 de ellos para que el recolector de basura se encargue de ellos. Eso está destinado a trastornarlo.

Ahora algunos experimentos basados ​​en respuestas / comentarios han publicado personas.

¿Estoy haciendo trampa con el tamaño del buffer?

Una sugerencia fue que dado que un BufferedReader usa un buffer por defecto de 16KB, y he usado un buffer de 8MB, no estoy comparando con like. Seguramente será más rápido si usa un buffer más grande.

Aquí está el shock. El método sumBinary() (Método 4) se ejecutó en 30.8 segundos ayer con un buffer de 8MB. Hoy, sin cambiar el código, la dirección del viento ha cambiado y estamos en 30.4 segundos. Si reduzco el tamaño del búfer a 16 KB para ver cuánto más lento se vuelve, ¡ se vuelve más rápido! Ahora se ejecuta en 23.7 segundos . Loca. ¿Quién lo vio venir?

Un poco de experimentación sugiere que 16KB es aproximadamente óptimo. Tal vez los chicos de Java hicieron los mismos experimentos, ¡y es por eso que fueron con 16KB!

¿El problema está vinculado a E / S?

Me preguntaba acerca de esto también. ¿Cuánto tiempo se dedica al acceso al disco y cuánto se usa en el procesamiento de números? Si es casi todo el acceso al disco, como lo sugiere un comentario bien respaldado sobre una de las respuestas propuestas, entonces no podremos mejorar mucho lo que hagamos.

Esto es fácil de probar ejecutando el código con todos los análisis sintácticos y numéricos comentados, pero con la lectura intacta:

 private long sumBinary() throws IOException { RandomAccessFile raf = new RandomAccessFile(file, "r"); int lastRead = (int) raf.length(); byte buf[] = new byte[16 * 1024]; int mul = 1; long total = 0; while (lastRead > 0) { int len = Math.min(buf.length, lastRead); raf.seek(lastRead - len); raf.readFully(buf, 0, len); lastRead -= len; /*for (int i = len - 1; i >= 0; i--) { if ((buf[i] >= 48) && (buf[i] <= 57)) { total += mul * (buf[i] - 48); mul *= 10; } else mul = 1; }*/ } raf.close(); return total; } 

¡Ahora esto funciona en 3.7 segundos ! Esto no parece vinculado a I / O para mí.

Por supuesto, parte de la velocidad de E / S vendrá de aciertos de caché de disco. Pero ese no es el punto aquí: todavía estamos tomando 20 segundos de tiempo de CPU (también confirmados con el comando de time de Linux), que es lo suficientemente grande como para tratar de reducirlo.

Escaneo hacia adelante en lugar de hacia atrás

Había mantenido en mi publicación original que había buenas razones para escanear el archivo hacia atrás en lugar de hacia adelante. No lo explicaba muy bien. La idea era que si escanea un número hacia adelante, debe acumular el valor total del número escaneado y luego agregarlo. Si escanea hacia atrás, puede agregarlo al total acumulativo a medida que avanza. Mi subconsciente tenía algún sentido para sí mismo (más adelante), pero me había perdido un punto clave, que se señaló en una de las respuestas: para escanear hacia atrás, estaba haciendo dos multiplicaciones por iteración, pero con buscando hacia delante solo necesita uno. Así que codifiqué una versión de exploración hacia adelante:

 private long sumBinaryForward() throws IOException { RandomAccessFile raf = new RandomAccessFile(file, "r"); int fileLength = (int) raf.length(); byte buf[] = new byte[16 * 1024]; int acc = 0; long total = 0; int read = 0; while (read < fileLength) { int len = Math.min(buf.length, fileLength - read); raf.readFully(buf, 0, len); read += len; for (int i = 0; i = 48) && (buf[i] <= 57)) acc = acc * 10 + buf[i] - 48; else { total += acc; acc = 0; } } } raf.close(); return total; } 

Esto se ejecuta en 20.0 segundos , superando la versión de escaneo hacia atrás por una distancia. Bonito.

Caché de multiplicación

Lo que me di cuenta durante la noche, sin embargo, fue que, aunque estaba realizando dos multiplicaciones por iteración, existía la posibilidad de usar un caché para almacenar estas multiplicaciones, de modo que pudiera evitar tener que realizarlas durante la iteración hacia atrás. ¡Me complació ver que cuando desperté, alguien había tenido la misma idea!

El punto es que hay como máximo 10 dígitos en los números que estamos escaneando, y solo 10 dígitos posibles, por lo que solo hay 100 posibilidades para el valor de un dígito en el total acumulado. Podemos precomputar estos y luego usarlos en el código de exploración hacia atrás. Eso debería superar a la versión de escaneo directo, porque ahora nos hemos deshecho por completo de las multiplicaciones. (Tenga en cuenta que no podemos hacer esto con el escaneo directo, porque la multiplicación es del acumulador, que podría tomar cualquier valor hasta 10 ^ 9. Solo en el caso retrospectivo, ambos operandos están limitados a unas pocas posibilidades).

 private long sumBinaryCached() throws IOException { int mulCache[][] = new int[10][10]; int coeff = 1; for (int i = 0; i < 10; i++) { for (int j = 0; j  0) { int len = Math.min(buf.length, lastRead); raf.seek(lastRead - len); raf.readFully(buf, 0, len); lastRead -= len; for (int i = len - 1; i >= 0; i--) { if ((buf[i] >= 48) && (buf[i] <= 57)) total += mulCache[mul++][buf[i] - 48]; else mul = 0; } } raf.close(); return total; } 

Esto se ejecuta en 26.1 segundos . Decepcionante para decir lo menos. Leer hacia atrás es menos eficiente en términos de E / S, pero hemos visto que la E / S no es el mayor dolor de cabeza aquí. Esperaba que esto marcara una gran diferencia positiva. Quizás la búsqueda de matriz es tan costosa como las multiplicaciones que hemos reemplazado. (Intenté hacer la matriz 16×16 y usar los cambios de bits para indexar, pero no sirvió de nada).

Parece que el escaneo hacia adelante es donde está.

Usando un MappedByteBuffer

Lo siguiente que debe agregar es un MappedByteBuffer , para ver si eso es más eficiente que usar un RandomAccessFile bruto. No necesita mucho cambio en el código.

 private long sumBinaryForwardMap() throws IOException { RandomAccessFile raf = new RandomAccessFile(file, "r"); byte buf[] = new byte[16 * 1024]; final FileChannel ch = raf.getChannel(); int fileLength = (int) ch.size(); final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0, fileLength); int acc = 0; long total = 0; while (mb.hasRemaining()) { int len = Math.min(mb.remaining(), buf.length); mb.get(buf, 0, len); for (int i = 0; i = 48) && (buf[i] <= 57)) acc = acc * 10 + buf[i] - 48; else { total += acc; acc = 0; } } ch.close(); raf.close(); return total; } 

Esto parece mejorar un poco las cosas: ahora estamos en 19.0 segundos . ¡Hemos tomado otro segundo de lo mejor de nosotros mismos!

¿Qué pasa con multi-threading?

Una de las respuestas propuestas implica el uso de múltiples núcleos. ¡Estoy un poco avergonzado de que eso no se me haya ocurrido!

La respuesta vino en algún palo, debido a la suposición de que es un problema ligado a E / S. ¡Esto parece un poco duro, a la luz de los resultados sobre I / O! Sin duda vale la pena intentarlo, en cualquier caso.

Lo haremos usando fork / join. Aquí hay una clase para representar el resultado de un cálculo en una parte del archivo, teniendo en cuenta que puede haber un resultado parcial a la izquierda (si comenzamos a la mitad de un número), y un resultado parcial a la derecha (si el búfer terminado a la mitad de un número). La clase también tiene un método que nos permite unir dos de estos resultados, en un resultado combinado para dos subtareas adyacentes.

 private class SumTaskResult { long subtotal; int leftPartial; int leftMulCount; int rightPartial; public void append(SumTaskResult rightward) { subtotal += rightward.subtotal + rightPartial * rightward.leftMulCount + rightward.leftPartial; rightPartial = rightward.rightPartial; } } 

Ahora el bit clave: el RecursiveTask que calcula el resultado. Para pequeños problemas (menos de 64 caracteres), llama a computeDirectly() para calcular el resultado en un solo hilo; para problemas más grandes, se divide en dos, resuelve los dos subproblemas en hilos separados y luego combina los resultados.

 private class SumForkTask extends RecursiveTask { private byte buf[]; // startPos inclusive, endPos exclusive private int startPos; private int endPos; public SumForkTask(byte buf[], int startPos, int endPos) { this.buf = buf; this.startPos = startPos; this.endPos = endPos; } private SumTaskResult computeDirectly() { SumTaskResult result = new SumTaskResult(); int pos = startPos; result.leftMulCount = 1; while ((buf[pos] >= 48) && (buf[pos] <= 57)) { result.leftPartial = result.leftPartial * 10 + buf[pos] - 48; result.leftMulCount *= 10; pos++; } int acc = 0; for (int i = pos; i = 48) && (buf[i] <= 57)) acc = acc * 10 + buf[i] - 48; else { result.subtotal += acc; acc = 0; } result.rightPartial = acc; return result; } @Override protected SumTaskResult compute() { if (endPos - startPos < 64) return computeDirectly(); int mid = (endPos + startPos) / 2; SumForkTask left = new SumForkTask(buf, startPos, mid); left.fork(); SumForkTask right = new SumForkTask(buf, mid, endPos); SumTaskResult rRes = right.compute(); SumTaskResult lRes = left.join(); lRes.append(rRes); return lRes; } } 

Tenga en cuenta que esto está operando en un byte[] , en lugar de en todo el MappedByteBuffer . El motivo es que queremos mantener el acceso al disco secuencial. Tomaremos trozos bastante grandes, tenedor / unión, y luego pasaremos al siguiente trozo.

Este es el método que hace eso. Tenga en cuenta que hemos aumentado el tamaño del búfer hasta 1 MB (subóptimo anteriormente, pero más sensato aquí, parece).

 private long sumBinaryForwardMapForked() throws IOException { RandomAccessFile raf = new RandomAccessFile(file, "r"); ForkJoinPool pool = new ForkJoinPool(); byte buf[] = new byte[1 * 1024 * 1024]; final FileChannel ch = raf.getChannel(); int fileLength = (int) ch.size(); final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0, fileLength); SumTaskResult result = new SumTaskResult(); while (mb.hasRemaining()) { int len = Math.min(mb.remaining(), buf.length); mb.get(buf, 0, len); SumForkTask task = new SumForkTask(buf, 0, len); result.append(pool.invoke(task)); } ch.close(); raf.close(); pool.shutdown(); return result.subtotal; } 

Ahora esta es la desilusión que destruye el alma: este codigo con muchos subprocesos ahora toma 32.2 segundos . ¿Por qué es tan lenta? Pasé bastante tiempo depurándolo, suponiendo que hubiera hecho algo terriblemente mal.

Resulta que solo se necesitaba una pequeña modificación. Pensé que el umbral de 64 entre pequeño problema y gran problema era razonable; resulta que fue totalmente ridículo.

Piénsalo así. Los sub-problemas son exactamente del mismo tamaño, por lo que deben completarse casi al mismo tiempo. Así que realmente no tiene sentido dividirse en más piezas que los procesadores disponibles. En la máquina que uso, con solo dos núcleos, bajar a un umbral de 64 es ridículo: solo agrega más sobrecarga.

Ahora no desea limitar las cosas para que solo use dos núcleos, incluso cuando haya más disponibles. Tal vez lo correcto sea averiguar la cantidad de procesadores en tiempo de ejecución y dividirlos en muchas partes.

En cualquier caso, si cambio el umbral a 512 KB (la mitad del tamaño del búfer), ahora se completa en 13,3 segundos . Bajar a 128 KB o 64 KB permitiría utilizar más núcleos (hasta 8 o 16, respectivamente), y no afectará significativamente el tiempo de ejecución.

Por lo tanto, multi-threading hace una gran diferencia.

Ha sido un viaje bastante largo, pero comenzamos con algo que tomó 92,9 segundos y ahora tenemos 13,3 segundos … eso es siete veces la velocidad del código original. Y eso no es mejorando la complejidad del tiempo asintótica (big-Oh), que fue lineal (óptima) desde el principio … todo ha sido para mejorar el factor constante.

Un buen día de trabajo.

Supongo que probablemente debería intentar usar la GPU a continuación …

Posdata: generando el archivo de números aleatorios

Genere los números aleatorios con el siguiente código, que ejecuté y redirigí a un archivo. Obviamente no puedo garantizar que termines exactamente con los mismos números aleatorios que tenía 🙂

 public static void genRandoms() { Random r = new Random(); for (int i = 0; i < 100000000; i++) System.out.println(r.nextInt(1000000000)); } 

Creo que hay otra forma de hacer esto.

Este es un problema clásico de progtwigción de múltiples procesos. En el lenguaje C, hay una biblioteca MPI que resuelve este tipo de problemas.

La idea es dividir la lista de enteros, por ejemplo, en 4 partes y cada parte se sum mediante un proceso diferente. Después de terminar, los procesos se sumn.

En java esto podría hacerse con hilos (pseudo paralelo) y concurrencia java.

Por ejemplo, 4 hilos diferentes que sumn 4 partes diferentes de la lista. Al final se sumn.

Las compañías telefónicas usan computadoras de cuadrícula que hacen este tipo de técnica de progtwigción paralela para sumr sus transacciones.

El único problema aquí (cuello de botella) es la operación IO. Leer el archivo llevará mucho tiempo. Si de alguna manera puedes hacer que varios hilos lean diferentes partes del archivo … Este es un enfoque muy complicado y creo que esto no servirá de mucho porque el disco no girará más rápido solo porque es usado por muchos hilos, pero hay otras técnicas de hacer cosas similares. Puedes leer más sobre esto aquí: Acceder al archivo a través de múltiples hilos y aquí Leer un único archivo con múltiples hilos : ¿debería acelerarse?

Su cuello de botella principal será archivo IO. El análisis y la sum de los números no deberían contribuir al algoritmo, ya que esto se puede hacer en un subproceso separado mientras el archivo de E / S está esperando el disco.

Hace algunos años, investigué cómo leer de los archivos de la manera más rápida posible y encontré algunos consejos excelentes, que implementé como una rutina de exploración como la siguiente:

 // 4k buffer size. static final int SIZE = 4 * 1024; static byte[] buffer = new byte[SIZE]; // Fastest because a FileInputStream has an associated channel. private static void ScanDataFile(Hunter p, FileInputStream f) throws FileNotFoundException, IOException { // Use a mapped and buffered stream for best speed. // See: http://nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly final FileChannel ch = f.getChannel(); long red = 0L; do { final long read = Math.min(Integer.MAX_VALUE, ch.size() - red); final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, red, read); int nGet; while (mb.hasRemaining() && p.ok()) { nGet = Math.min(mb.remaining(), SIZE); mb.get(buffer, 0, nGet); for (int i = 0; i < nGet && p.ok(); i++) { p.check(buffer[i]); //size += 1; } } red += read; } while (red < ch.size() && p.ok()); // Finish off. p.close(); ch.close(); f.close(); } 

Es posible que desee ajustar esta técnica antes de probarla en busca de velocidad, ya que está utilizando un objeto interconectado llamado Hunter para buscar los datos.

Como puede ver, el consejo se derivó en 2008 y ha habido muchas mejoras en Java desde entonces, por lo que es posible que esto no proporcione una mejora.

Adicional

No he probado esto, pero esto debería encajar en sus pruebas y usar la misma técnica:

 class Summer { long sum = 0; long val = 0; public void add(byte b) { if (b >= '0' && b <= '9') { val = (val * 10) + (b - '0'); } else { sum += val; val = 0; } } public long getSum() { return sum + val; } } private long sumMapped() throws IOException { Summer sum = new Summer(); FileInputStream f = new FileInputStream(file); final FileChannel ch = f.getChannel(); long red = 0L; do { final long read = Math.min(Integer.MAX_VALUE, ch.size() - red); final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, red, read); int nGet; while (mb.hasRemaining()) { nGet = Math.min(mb.remaining(), SIZE); mb.get(buffer, 0, nGet); for (int i = 0; i < nGet; i++) { sum.add(buffer[i]); } } red += read; } while (red < ch.size()); // Finish off. ch.close(); f.close(); return sum.getSum(); } 

¿Por qué es esto mucho más rápido?

Crear una cadena es mucho más costoso que un poco de matemáticas.

¿Podemos hacer algo mejor que esto utilizando una ayuda de MappedByteBuffer?

Un pequeño sí. Es lo que uso Guarda una memoria en la copia de memoria. es decir, no se necesita byte [].

Tengo la sensación de que los gastos generales de invocar métodos para leer desde el búfer reducirían la velocidad,

Los métodos se marcan si son simples.

especialmente cuando lee hacia atrás desde el búfer.

No será más lento, de hecho el análisis de avance es más simple / más rápido porque usa uno * lugar de dos.

¿Sería mejor leer el archivo hacia adelante en lugar de hacia atrás, pero aún escanear el buffer hacia atrás?

No entiendo por qué tendrías que leer al revés.

La idea sería leer el primer trozo del archivo y luego escanear hacia atrás, pero descartando el medio número al final. Luego, cuando lea el siguiente fragmento, configure el desplazamiento para que lea desde el principio del número que descartó.

suena innecesariamente complicado. Leería en una sola pasada, mapeo de memoria en todo el archivo de una vez. No es necesario utilizar fragmentos a menos que el archivo tenga 2+ GB de tamaño. e incluso entonces leería de una vez.

¿Hay algo que no haya pensado que pueda hacer una diferencia significativa?

Si los datos están en caché de disco, harán más diferencia que cualquier otra cosa.

Puede elegir un tamaño de búfer más grande y una encoding más rápida para Cadena (a Unicode).

 BufferedReader br = new BufferedReader(new InputStreamReader( new FileInputStream(file), StandardCharsets.US_ASCII), 1_024_000_000); 

Su método para eliminar el uso de String, mediante el uso de un InputStream / RandomAccessFile binario vale la pena.

Entonces también podría ser bueno si los archivos fuente estuvieran comprimidos . En Unix uno elegiría el formato gzip, donde xxx.txt.gz descomprime a xxx.txt . Eso sería legible con un GZipInputStream . Tiene la ventaja de acelerar en general la transferencia de archivos hacia y desde el directorio del servidor.

Fuente: http://nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly

Para obtener el mejor rendimiento de lectura de Java, hay cuatro cosas para recordar:

  • Minimice las operaciones de E / S leyendo una matriz a la vez, no un byte a la vez. Una matriz de 8Kbytes tiene un buen tamaño.
  • Minimice las llamadas a métodos obteniendo datos de una matriz a la vez, no de un byte a la vez. Use indexación de matriz para obtener bytes en la matriz.
  • Minimice los lockings de sincronización de subprocesos si no necesita seguridad de subprocesos. Realice menos llamadas a métodos a una clase segura para subprocesos o use una clase no segura para subprocesos como FileChannel y MappedByteBuffer.
  • Minimice la copia de datos entre la JVM / OS, los búferes internos y las matrices de aplicaciones. Use FileChannel con mapeo de memoria, o una matriz directa o envolvente ByteBuffer.

Basado en este comentario : “Simplemente resumiendo todos los bytes es más rápido”, propongo una variación de la respuesta aceptada.

La respuesta aceptada propone dividir el problema en trozos, calcular una sum para cada portabrocas utilizando subprocesos múltiples y sumrlos al final.

Esta idea se puede usar para reducir el número de multiplicaciones a O (1) en el escaneo hacia atrás, sin búsquedas en la tabla y sin enhebrar (o combinarlo con subprocesamiento). Simplemente tome ventaja de la forma en que la multiplicación se distribuye sobre la sum y agregue todos los dígitos en un acumulador, las decenas en una separada , cientos y miles en sus propios acumuladores. Esto no requiere multiplicación alguna.

El paso de reducción combina los resultados de múltiples hilos también se puede hacer utilizando los acumuladores por lugar. El paso final para calcular los totales requerirá multiplicación (o aprovechar el hecho de que 10 tiene solo dos bits establecidos y usar cambios de bit y agregar), pero solo 9 multiplicaciones son suficientes.

Hay varios problemas aqui.

  1. Cualquier solución basada en líneas de lectura va a procesar cada personaje dos veces. Los comstackdores, por ejemplo, no hacen esto, leen un personaje a la vez y lo envían directamente.
  2. Cualquier solución basada en readLine() va a crear cadenas.
  3. Estás usando diferentes tamaños de buffer.
  4. Está utilizando diferentes tecnologías de E / S.
  5. En algunos casos, está utilizando la conversión de caracteres, mientras que en otros no.
  6. Estás analizando en exceso el archivo. Realmente no te importa dónde está el espacio en blanco, o cuánto hay, siempre que separe los números entre sí.

Mi solución:

  BufferedInputStream bis = new BufferedInputStream(new FileInputStream(file), 8*1024*1024/2); long total = 0; int i; while ((i = bis.read()) != -1) { byte b = (byte)i; long number = 0; while (b >= '0' && b <= '9') { number = number*10+b-'0'; if ((i = bis.read()) == -1) break; b = (byte)i; } total += number; }