Como parte de un proyecto en el que estoy trabajando, me gustaría limpiar un archivo que se generan de la duplicación de entradas de línea. Estos duplicados a menudo no producen cerca uno de otro, sin embargo. Se me ocurrió una forma de hacerlo en Java (que, básicamente, una copia de el archivo, entonces se utiliza un anidados, mientras que la instrucción para comparar cada línea en un fichero con el resto de los otros). El problema, es que mi archivo generado es bastante grande y el texto pesado (alrededor de 225k líneas de texto, y alrededor de 40 megas). Yo estimo que mi actual proceso de 63 horas! Este definitivamente no es aceptable.

Necesito una solución integrada para esto, sin embargo. Preferiblemente en Java. Alguna idea? Gracias!

  • 9 respuestas y no votos? esto es perfectamente válido y bien formulada la pregunta
InformationsquelleAutor Monster | 2009-06-15

14 Comentarios

  1. 37

    Hmm… 40 megas parece lo suficientemente pequeño que se podía construir una Set de las líneas y, a continuación, imprimir todos ellos de vuelta. Esto sería mucho, mucho más rápido que hacer O(n2) I/O trabajo.

    Sería algo como esto (haciendo caso omiso de las excepciones):

    public void stripDuplicatesFromFile(String filename) {
        BufferedReader reader = new BufferedReader(new FileReader(filename));
        Set<String> lines = new HashSet<String>(10000); //maybe should be bigger
        String line;
        while ((line = reader.readLine()) != null) {
            lines.add(line);
        }
        reader.close();
        BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
        for (String unique : lines) {
            writer.write(unique);
            writer.newLine();
        }
        writer.close();
    }

    Si el orden es importante, se puede utilizar un LinkedHashSet en lugar de un HashSet. Ya que los elementos son almacenados por referencia, la sobrecarga de una lista enlazada debe ser insignificante en comparación con la cantidad real de datos.

    Edición: Como Taller de Alex señaló, si no te importa hacer un archivo temporal, usted puede simplemente imprimir las líneas a medida que se lee. Esto le permite utilizar un simple HashSet en lugar de LinkedHashSet. Pero dudo que se nota la diferencia en un I/O bound operación como esta.

    • esa es la respuesta que iba a dar
    • sí, de 40 megas no es nada, leer toda la cosa en la memoria, volcado a un hashset para mantener sólo las únicas líneas, escribir en el disco.
    • Según el interlocutor de los requisitos, usted puede necesitar para mantener un seguimiento del número de línea, debido a la iteración sobre un HashSet devolverá las líneas en un bonito orden arbitrario.
    • Usted puede inicializar el hashset con un valor como #líneas / 0.75 porque HashSet hará una nueva tabla y refrito de todo, si alcanza su defecto de relleno grado de 75%. Otra posibilidad sería crear el HashSet con un fillgrade de 1.0 f (100%) y un tamaño que es un poco más grande que sus datos-contar -> «new HashSet(300000, 1.0 f)». De esta manera usted puede evitar costosos rehash.
    • Usted podría simplificar este código mediante el uso de readLines() y writeLines() de Commons IO FileUtils, commons.apache.org/io/api-release/org/apache/commons/io/…. (No estoy seguro de si eso afectaría a la escalabilidad sin embargo.)
    • Hmmm, me trató de implementar esto, pero me sale el error «java.lang.OutOfMemoryError: Java heap space». He intentado aumentar el HashSet tamaño, pero no es bueno. Ideas? Gracias!
    • De paso Xmx64m (donde 64 es el número de megabytes en el montón) para el programa en el inicio, como «java -Xmx64m Miprograma» o «java -Xmx100m -jar MyJar.jar».
    • lo más probable es que necesite más de 64MB de ram. por qué? 40MB us-ascii-prueba-de-archivo – > 80 MB como cadenas + HashSet sobrecarga + Objeto sobrecarga + …. Me gustaría ir con 512 MB o así 🙂
    • – Ah, pero él no es el almacenamiento de las líneas duplicadas, por lo que depende de cómo muchos duplicados hay. (Es probable el derecho, aunque, y no es nada malo tener una asignación mayor en un corto programa que se ejecuta como este.)
    • Ah, me puse el xmx a 512 y pareció funcionar. Gran solución! Duplicados han ido! Gracias chicos!
    • Y como final a un lado, me hizo acabar con LinkedHashSet. Mientras que el orden no es de enorme importancia, que hace el seguimiento de las cosas mucho más fáciles. Y la sobrecarga es igual a cero. Gracias de nuevo a todos!
    • Este exacta aplicación en la Scala blog.cyberwhale.tech/2017/01/09/…
    • Conjunto están destinados a que sólo. (y)

  2. 15

    Bien, la mayoría de las respuestas son un poco tonto y lento, ya que implica la adición de líneas a algunos de hashset o lo que sea y, a continuación, hacia atrás, desde que configurar de nuevo. Permítanme mostrarles la solución más óptima en pseudocódigo:

    Create a hashset for just strings.
    Open the input file.
    Open the output file.
    while not EOF(input)
      Read Line.
      If not(Line in hashSet)
        Add Line to hashset.
        Write Line to output.
      End If.
    End While.
    Free hashset.
    Close input.
    Close output.

    Por favor chicos, no hacen más difícil de lo que necesita ser. 🙂 No te molestes sobre la ordenación, no es necesario.

    • +1 para afirmar que el sangrado evidente que debería haber visto al escribir mi respuesta. D’oh! 🙂
    • Cierto, pero yo lo estaba haciendo sin un archivo temporal, pero podría ser un poco más eficiente con uno (no LinkedHashSet es necesario). Pero me gustaría aventurar una suposición de que la CPU no va a ser el cuello de botella de todos modos.
    • Er, mi comentario fue dirigido a el Taller de Alex, no gustafc.
    • Por supuesto, en lugar de utilizar un archivo de salida, usted podría salida a un sin clasificar cadena de lista, en la memoria. Luego, cuando hayas terminado de añadir la entrada sin duplicados, escribir la lista de cadenas sobre el antiguo archivo de entrada. Esto significa que usted va a utilizar dos veces la cantidad de memoria que con otras soluciones, pero es todavía extremadamente rápido.
    • Alex: eso es básicamente lo Que hice. ¿Por qué dice que utiliza dos veces la cantidad de memoria?
    • Esto es debido a que las tiendas de las cadenas de dos veces: una vez en la tabla hash y una vez en la lista de cadenas. (A continuación, de nuevo, es probable que tanto el hashset y la cadena de la lista sólo almacenar referencias a cadenas de caracteres, en cuyo caso no se comen mucho.)
    • Sí, lo hacen almacenar referencias. La sobrecarga adicional es, probablemente, ni siquiera lo suficiente como para notar, a las 8 bytes por cadena única.
    • Cálculo Simple: 225k líneas, horarios de 8 por cada referencia que hace 1.8 megabytes. Con dos listas, que se duplica a 3.6 megabytes. Entonces de nuevo, si el 90% son duplicados, entonces usted puede reducir el número de estos de nuevo en un 90%…
    • super eficiente ! Tuve que procesar 30.000 archivos con 100 líneas cada uno y eliminar duplicados. Este tomó 10 minutos, mientras que la otra solución que tomó 3 horas.

  3. 10

    Un enfoque similar

    public void stripDuplicatesFromFile(String filename) {
        IOUtils.writeLines(
            new LinkedHashSet<String>(IOUtils.readLines(new FileInputStream(filename)),
            "\n", new FileOutputStream(filename + ".uniq"));
    }
    • No debería el último FileInputStream ser en realidad un FileOutputStream? Aparte de eso, +1 de una simplicidad y de «conocer y utilizar las bibliotecas».
    • También, vale la pena mencionar que IOUtils es de Apache Commons IO (commons.apache.org/io); que, probablemente, no es obvio para cualquier lector.
    • gracias por que señalar los dos comentarios.
  4. 4

    Algo como esto, quizás:

    BufferedReader in = ...;
    Set<String> lines = new LinkedHashSet();
    for (String line; (line = in.readLine()) != null;)
        lines.add(line); //does nothing if duplicate is already added
    PrintWriter out = ...;
    for (String line : lines)
        out.println(line);

    LinkedHashSet mantiene el orden de inserción, en contraposición a HashSet (aunque siendo un poco más rápido para la búsqueda/insertar) se reordenar todas las líneas.

  5. 3

    Usted podría utilizar Establecido en las Colecciones de la biblioteca para almacenar único, visto como valores de leer el archivo.

    Set<String> uniqueStrings = new HashSet<String>();
    
    //read your file, looping on newline, putting each line into variable 'thisLine'
    
        uniqueStrings.add(thisLine);
    
    //finish read
    
    for (String uniqueString:uniqueStrings) {
      //do your processing for each unique String
      //i.e. System.out.println(uniqueString);
    }
  6. 2

    Trate de un simple HashSet que almacena las líneas que ya han leído.
    Luego iterar sobre el archivo.
    Si usted viene a través de los duplicados son simplemente ignorados (como un Conjunto sólo puede contener cada elemento de una vez).

    • estás mejor con algún tipo de conjunto en lugar de un mapa
    • Es por eso que ya he solucionado 😉
    • Yo he hecho algo similar en Delphi una vez, aunque me he tenido que escribir mi propio HashSet clase para ello. El único inconveniente es que necesita mucha memoria con archivos de gran tamaño, lo cual está bien si usted no esta del lado del cliente, pero no en un servidor. Básicamente, el proyecto que necesita de esta conseguido leer un archivo de 500 kb de líneas y eliminar todos los duplicados dentro de dos minutos.
    • Sin embargo, acabo de leer una línea, comprueba si fue en el hash-y si no lo era, me gustaría agregar y escribir en archivo. De lo contrario, acababa de saltar a la línea siguiente. De esa manera, no me voy a leer desde el hashset y lo mejor de todo: seguí todas las líneas en el mismo orden.
  7. 2
    • De leer el archivo, el almacenamiento, el número de línea y la línea: O(n)
    • Ordenar en orden alfabético: O(n log n)
    • Eliminar duplicados: O(n)
    • Especie en su línea original número de orden: O(n log n)
  8. 1

    El Hash Conjunto de enfoque está bien, pero usted puede modificar para no tener que almacenar todas las Cadenas en memoria, pero una lógica puntero a la ubicación en el archivo para que usted pueda volver a leer el valor real sólo en caso de necesidad.

    Otro enfoque creativo es anexar a cada línea el número de la línea, a continuación, ordenar todas las líneas, eliminar los duplicados (ignorando el último símbolo que debe ser el número) y, a continuación, vuelve a ordenar el archivo por el último símbolo y la creación de bandas en la salida.

  9. 0

    Si usted puede usar los comandos shell de UNIX se podría hacer algo como lo siguiente:

    for(i = line 0 to end)
    {
        sed 's/$i//2g' ; deletes all repeats
    }

    Este sería iterar a través de todo su archivo y sólo pasar cada ocurrencia única vez por sed de llamada. De esta manera usted no está haciendo un montón de búsquedas que hayas hecho antes.

  10. 0

    Hay dos soluciones escalables, donde por escalable me refiero a la disco y no la memoria, dependiendo de si el procedimiento debe ser estable o no, donde se estable me refiero a que el orden después de la eliminación de duplicados es el mismo. si la escalabilidad no es un problema, a continuación, simplemente el uso de la memoria para el mismo tipo de método.

    Para la no solución estable, ordenar primero el archivo en el disco. Esto se realiza mediante la división del archivo en archivos más pequeños, de ordenación de los fragmentos más pequeños en la memoria, y, a continuación, combinar los archivos en orden, donde la combinación omite los registros duplicados.

    La mezcla en sí mismo puede ser hecho usando casi no hay memoria, comparando sólo la actual línea de cada archivo, ya que la siguiente línea está garantizada para ser mayor.

    La solución estable es un poco más complicado. En primer lugar, ordenar el archivo en fragmentos como antes, pero indican en cada línea de la original número de línea. Luego, durante la «fusión» no te molestes en almacenamiento
    el resultado, sólo los números de línea para ser eliminados.

    A continuación, copie el archivo original, línea por línea, ignorando los números de línea que usted ha almacenado anteriormente.

  11. 0

    ¿Importa el orden en que las líneas de venir, y de cómo muchos duplicados estás contando a ver?

    Si no, y si usted está contando con una gran cantidad de incautos (es decir, mucho más de la lectura de la escritura) también me gustaría pensar la paralelización de el hashset solución, con el hashset como un recurso compartido.

    • No es una mala idea, pero desde el archivo de entrada es de sólo 40 megabytes no creo que sea un problema.
    • Supongo. Pero la paralelización de cosas es phun! :3
  12. 0

    He hecho dos supuestos para esta solución eficiente:

    1. Hay una nota equivalente de la línea o de la que podemos procesar como binario
    2. Podemos guardar el desplazamiento o un puntero al inicio de cada línea.

    Basándose en estos supuestos la solución es:
    1.leer una línea, guardar la longitud en el hashmap como clave , por lo que tenemos más ligero hashmap. Guardar la lista como la entrada en hashmap para todas las líneas de tener esa longitud se menciona en clave. La construcción de este hashmap es O(n).
    Mientras que la asignación de los desplazamientos para cada línea en el hashmap,comparar la línea de notas con todas las entradas existentes en la lista de líneas(offsets) para esta longitud de la clave, excepto la entrada de -1 como offset.si duplicados encontrados quitar ambas líneas y guardar el desplazamiento -1 en esos lugares en la lista.

    Por lo que considerar la complejidad y el uso de la memoria:

    Hashmap la memoria ,el espacio de la complejidad = O(n), donde n es el número de líneas de

    Tiempo de Complejidad – si no duplicados, pero todos iguales en longitud de líneas teniendo en cuenta la longitud de cada línea = m, considerar el número de líneas =n, entonces que sería , O(n). Puesto que suponemos que podemos comparar blob , el m no importa.
    Que fue peor de los casos.

    En otros casos hemos de guardar en las comparaciones a pesar de que tienen poco espacio extra necesario en hashmap.

    Además podemos usar mapreduce en el lado del servidor para dividir el conjunto y la combinación de los resultados más tarde. Y el uso de la longitud o el comienzo de la línea como el asignador de clave.

  13. 0
    void deleteDuplicates(File filename) throws IOException{
        @SuppressWarnings("resource")
        BufferedReader reader = new BufferedReader(new FileReader(filename));
        Set<String> lines = new LinkedHashSet<String>();
        String line;
        String delims = " ";
        System.out.println("Read the duplicate contents now and writing to file");
        while((line=reader.readLine())!=null){
            line = line.trim(); 
            StringTokenizer str = new StringTokenizer(line, delims);
            while (str.hasMoreElements()) {
                line = (String) str.nextElement();
                lines.add(line);
                BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
                for(String unique: lines){
                    writer.write(unique+" ");               
                }
                writer.close();
            }
        }
        System.out.println(lines);
        System.out.println("Duplicate removal successful");
    }

Dejar respuesta

Please enter your comment!
Please enter your name here