java - por - La forma más rápida de sumar enteros en un archivo de texto

leer un archivo de texto en java palabra por palabra

Question

Pregunta

Suponga 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 suma de todos los enteros?

Restricción: tenemos 10 MB de RAM para trabajar. El archivo tiene un tamaño de 1 GB, por lo que no queremos leerlo 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 haya perdido?

Tenga en cuenta: todos los tiempos que se indican 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 debe intentar 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 valor de retorno máximo posible es 10 ^ 17, que todavía cabe 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 ejecución toma alrededor de 92.9 segundos .

Método 2: un pequeño retoque

Inspirado por un comentario sobre esta pregunta , intenté no crear una nueva int k para almacenar el resultado del análisis de la línea y, en su lugar, solo 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 haría ninguna diferencia, y pensé que era muy probable que el compilador generara el mismo código de bytes para las dos versiones. Pero, para mi sorpresa, redujo un poco el tiempo libre: hemos reducido a 92.1 segundos .

Método 3: análisis manual del 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 agregarlo a medida que avanzamos? ¿Qué sucede si analizamos la 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 cambio de bits para hacer la multiplicación. Pero los gastos generales de la conversión a una matriz de personajes deben afectar cualquier ganancia: esto ahora toma 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 encuentra son unidades, el siguiente es decenas, y así sucesivamente. Entonces, la forma más fácil de abordar todo el asunto 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 anteriores, y así sucesivamente. Debemos tener un poco de cuidado para no arruinar un número que estamos analizando cuando pasamos al siguiente bloque, pero ese es el único problema.

Cuando encontramos un dígito, lo sumamos (multiplicado adecuadamente según su posición en el número) al total, y luego multiplicamos el coeficiente por 10 para que estemos listos para el siguiente dígito. Si encontramos algo que no es un dígito (un CR o LF), simplemente restablecemos 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 se ejecuta 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. ¿Se trata principalmente de los gastos generales de la conversión a una String ? ¿Y todas las preocupaciones detrás de escena sobre los juegos de personajes y cosas por el estilo?
2. ¿Podemos hacer algo mejor que esto usando un MappedByteBuffer para ayudar? Tengo la sensación de que los gastos generales de invocar métodos para leer desde el búfer ralentizarían las cosas, especialmente al leer 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 búfer hacia atrás? La idea sería leer el primer fragmento del archivo y luego escanear hacia atrás, pero descartando el medio número al final. Luego, cuando lee el siguiente fragmento, establece el desplazamiento para que lea desde el principio del número que descartó.
4. ¿Hay algo en lo que no haya pensado que pueda hacer una diferencia significativa?

Actualización: resultados más sorprendentes

Primero, una observación. Debería haberme ocurrido antes, pero creo que la razón de la ineficiencia de la lectura basada en String no es tanto el tiempo necesario para crear todos los objetos de String sino el hecho de que son de corta duración: tenemos 100,000,000 de ellos para el recolector de basura. Eso seguramente lo alterará.

Ahora, algunos experimentos basados ​​en respuestas / comentarios que la gente ha publicado.

¿Estoy haciendo trampa con el tamaño del búfer?

Una sugerencia fue que, dado que un BufferedReader usa un búfer predeterminado de 16 KB, y he usado un búfer de 8 MB, no estoy comparando me gusta. Seguro que será más rápido si usa un búfer más grande.

Aquí está el shock. El método sumBinary() (Método 4) se ejecutó ayer en 30.8 segundos con un búfer de 8MB. Hoy, el código no ha cambiado, la dirección del viento ha cambiado y estamos a 30,4 segundos. Si dejo caer 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 vio venir a ese?

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

¿El problema está vinculado a E / S?

Me preguntaba sobre esto también. ¿Cuánto tiempo se dedica al acceso al disco y cuánto a la suma 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 todo el análisis y el procesamiento de números 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;
}

¡Esto ahora se ejecuta en 3.7 segundos ! Esto no me parece vinculado a E / S.

Por supuesto, parte de la velocidad de E / S vendrá de los éxitos de caché de disco. Pero ese no es realmente el punto aquí: todavía estamos tomando 20 segundos de tiempo de CPU (también confirmado usando 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 expliqué 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 sentido para sí mismo (sobre lo cual más adelante), pero 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 escanear hacia adelante 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 < len; i++) {
            if ((buf[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 a la versión de exploración hacia atrás por una distancia. Agradable.

Caché de multiplicación

Sin embargo, de lo que me di cuenta durante la noche fue que, aunque realizaba dos multiplicaciones por iteración, existía la posibilidad de utilizar un caché para almacenar estas multiplicaciones, de modo que pudiera evitar tener que realizarlas durante la iteración hacia atrás. ¡Me complació ver cuando desperté que 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 al total acumulado. Podemos precalcularlos y luego usarlos en el código de exploración hacia atrás. Eso debería vencer a la versión de exploración hacia adelante, porque ahora nos hemos librado de las multiplicaciones por completo. (Tenga en cuenta que no podemos hacer esto con el escaneo hacia adelante, porque la multiplicación es del acumulador, lo que podría tomar cualquier valor hasta 10 ^ 9. Es solo en el caso hacia atrás que 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 < 10; j++)
            mulCache[i][j] = coeff * j;
        coeff *= 10;
    }

    RandomAccessFile raf = new RandomAccessFile(file, "r");
    int lastRead = (int) raf.length();
    byte buf[] = new byte[16 * 1024];
    int mul = 0;
    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 += 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 al revé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 cara como las multiplicaciones que hemos reemplazado. (Intenté hacer la matriz 16x16 y usar bithifts para indexar, pero no ayudó).

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 procesar. No necesita muchos cambios 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 < len; i++)
            if ((buf[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 nuestro mejor esfuerzo personal!

¿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 llegó para un palo, debido a la suposición de que es un problema vinculado a E / S. ¡Esto parece un poco duro, a la luz de los resultados sobre E / S! Sin duda vale la pena intentarlo, en cualquier caso.

Haremos esto usando fork / join. Aquí hay una clase para representar el resultado de un cálculo en 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 buffer 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: la 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<SumTaskResult> {

    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 < endPos; i++)
            if ((buf[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 todo el MappedByteBuffer . La razón de esto es que queremos mantener el acceso al disco secuencial. Tomaremos trozos bastante grandes, bifurcaremos / uniremos, y luego pasaremos al siguiente fragmento.

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

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 aquí está la decepción que destruye el alma: este código agradablemente multiproceso ahora toma 32.2 segundos . ¿Por qué es tan lenta? Pasé bastante tiempo depurando esto, asumiendo que había hecho algo terriblemente mal.

Resulta que solo se necesitaba un pequeño ajuste. Pensé que el umbral de 64 entre un pequeño problema y un gran problema era razonable; Resulta que era totalmente ridículo.

Piénsalo así. Los subproblemas son exactamente del mismo tamaño, por lo que deberían completarse casi al mismo tiempo. Por lo tanto, realmente no tiene sentido dividirse en más piezas que procesadores disponibles. En la máquina que estoy usando, 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. Quizás lo correcto sería averiguar la cantidad de procesadores en tiempo de ejecución y dividirlos en tantas piezas.

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 afecta significativamente el tiempo de ejecución.

Entonces, el subprocesamiento múltiple hace una gran diferencia.

Ha sido un viaje bastante largo, pero comenzamos con algo que tomó 92.9 segundos y ahora estamos en 13.3 segundos ... eso es siete veces la velocidad del código original. Y eso no es mejorando la complejidad de tiempo asintótica (big-Oh), que era lineal (óptima) desde el principio ... todo se ha tratado de mejorar el factor constante.

Un buen día de trabajo.

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

Postdata: generar el archivo de números aleatorios

Generé los números aleatorios con el siguiente código, que ejecuté y redirigí a un archivo. Obviamente no puedo garantizar que termines con exactamente 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));
}

Answer 1

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

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

¿Podemos hacer algo mejor que esto usando una ayuda MappedByteBuffer?

Un pequeño sí. Es lo que yo uso. Se 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 retrasarían las cosas,

Los métodos se alinean si son simples.

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

No será más lento, de hecho, analizar hacia adelante 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 búfer hacia atrás?

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

La idea sería leer el primer fragmento del archivo y luego escanear hacia atrás, pero descartando el medio número al final. Luego, cuando lee el siguiente fragmento, establece 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 usar fragmentos a menos que el archivo tenga más de 2 GB de tamaño. e incluso entonces leería de una vez.

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

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

Answer 2

Basado en este comentario : "Simplemente resumir 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 suma para cada mandril utilizando subprocesos múltiples y sumarlos al final.

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

El paso de reducción que combina los resultados de múltiples subprocesos también se puede hacer usando los acumuladores por lugar. El último paso para calcular los totales requerirá una multiplicación (o aproveche el hecho de que 10 tiene solo dos bits establecidos y usa cambios de bits y suma), pero solo 9 multiplicaciones son suficientes.

Answer 3

Creo que hay otra forma de hacer esto.

Este es un problema clásico de programación de procesos múltiples. En 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 suma por un proceso diferente. Después de terminar, los procesos se suman juntos.

En java, esto podría hacerse con hilos (pseudo paralelos) y concurrencia de java.

Por ejemplo, 4 hilos diferentes que suman 4 partes diferentes de la lista. Al final se resumen juntos.

Las compañías telefónicas usan Grid Computers que hacen este tipo de técnica de programación paralela para sumar sus transacciones.

El único problema aquí (cuello de botella) es la operación IO. Leer el archivo llevará mucho tiempo. Si de alguna manera puede 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. Puede leer más sobre esto aquí: Acceda al archivo a través de varios subprocesos y aquí .

Answer 4

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

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

• Minimice las operaciones de E / S leyendo una matriz a la vez, no un byte a la vez. Una matriz de 8 KB es de buen tamaño.
• Minimice las llamadas a métodos al obtener datos de una matriz a la vez, no un byte a la vez. Utilice la indexación de matriz para obtener bytes en la matriz.
• Minimice los bloqueos de sincronización de hilos si no necesita seguridad de hilos. Realice menos llamadas de método a una clase segura para subprocesos o use una clase no segura para subprocesos como FileChannel y MappedByteBuffer.
• Minimice la copia de datos entre JVM / OS, memorias intermedias internas y matrices de aplicaciones. Use FileChannel con mapeo de memoria, o una matriz directa o envuelta ByteBuffer.

Answer 5

Hay varios problemas aqui.

1. Cualquier solución basada en líneas de lectura procesará cada carácter dos veces. Los compiladores, 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 utilizando diferentes tamaños de búfer.
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 sobreanalizando 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;
    }

Answer 6

Puede optar por un tamaño de búfer más grande y una codificación más rápida a String (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 de origen estuvieran comprimidos . En Unix, uno elegiría el formato gzip, donde xxx.txt.gz descomprime en xxx.txt . Eso sería legible con un GZipInputStream . Tiene la ventaja de acelerar la transferencia de archivos desde y hacia el directorio del servidor.

Answer 7

Su principal cuello de botella será el archivo IO. Analizar y sumar los números no debe contribuir al algoritmo, ya que eso se puede hacer en un hilo separado mientras el File I / O está esperando el disco.

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

// 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 probar su velocidad, ya que está utilizando un objeto interconectado llamado Hunter para buscar los datos.

Como puede ver, el consejo se obtuvo en 2008 y desde entonces ha habido muchas mejoras en Java, por lo que esto puede no proporcionar 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();
}