Algoritmo para devolver los valores únicos de la entrada sin clasificar -- java campo con algorithm camp codereview Relacionados El problema

Algorithm to return unique values from unsorted input


6
vote

problema

Español

Necesito crear un algoritmo eficiente que devuelva valores únicos de una entrada sin clasificar. No sé la longitud de la entrada.

Como la función que llamará a este algoritmo puede abortar la lectura en cualquier momento, creo que el uso de una implementación de código 99887765555544336 bien definido, por lo que no desperdiciaré la potencia de procesamiento adicional para el Entrada sin problemas.

Hoy en día, estoy usando un Set para realizar un seguimiento de los valores que ya he leído. Pero no sé si este es el algoritmo más eficiente, ya que mi longitud de entrada puede ser enorme.

El código a continuación es el algoritmo de trabajo de hoy:

  import java.util.Iterator; import java.util.HashSet; import java.util.Set; import java.util.NoSuchElementException; import java.io.BufferedReader; import java.io.StringReader; import java.io.IOException;  public class UniqueValues implements Iterable<String> {     private final Iterator<String> iterator;      public UniqueValues(BufferedReader r) {         this.iterator = new UniqueValuesIterator(r);     }      public Iterator<String> iterator() {         return iterator;     }      static class UniqueValuesIterator implements Iterator<String> {         private final BufferedReader r;          private final Set<String> values = new HashSet<>();          // When 'next' is null, need to get the next value         private String next;          public UniqueValuesIterator(BufferedReader r) {             this.r = r;         }          public boolean hasNext() {             // Good point from OldCurmudgeon             if(next != null) return true;              try {                 String line;                 while((line = r.readLine()) != null) {                     if(values.add(line)) { // add() returns 'true' when it is not a duplicate value.                         next = line;                         return true;                     }                 }             } catch(IOException e) { }              return false;         }          public String next() {             if(next == null) {                 if(! hasNext() ) throw new NoSuchElementException();             }              final String temp = next;             next = null;             return temp;         }          public void remove() {             throw new UnsupportedOperationException();         }     }      // For testing     public static void main(String... args) {         final StringReader r = new StringReader("value1 value6 value1 value3 value3 value6 value1 value6");          for(final String value : new UniqueValues(new BufferedReader(r)) ) {             System.out.println(value);         }          /* Output is (order is not important):          *           * line 1          * line 6          * line 3          */     } }   

¿Tiene algún algoritmo mejor para hacer esto?

Original en ingles

I need to create an efficient algorithm that returns unique values from an unsorted input. I don't know the length of the input.

As the function that will call this algorithm can abort the reading at any time, I think that using a well defined Iterable implementation is the right way, so I will not waste extra processing power for the uneeded input.

Today, I am using a Set to keep track of the values I've already read. But I don't know if this is the most efficient algorithm, as my input length can be huge.

The code below is my today's working algorithm:

import java.util.Iterator; import java.util.HashSet; import java.util.Set; import java.util.NoSuchElementException; import java.io.BufferedReader; import java.io.StringReader; import java.io.IOException;  public class UniqueValues implements Iterable<String> {     private final Iterator<String> iterator;      public UniqueValues(BufferedReader r) {         this.iterator = new UniqueValuesIterator(r);     }      public Iterator<String> iterator() {         return iterator;     }      static class UniqueValuesIterator implements Iterator<String> {         private final BufferedReader r;          private final Set<String> values = new HashSet<>();          // When 'next' is null, need to get the next value         private String next;          public UniqueValuesIterator(BufferedReader r) {             this.r = r;         }          public boolean hasNext() {             // Good point from OldCurmudgeon             if(next != null) return true;              try {                 String line;                 while((line = r.readLine()) != null) {                     if(values.add(line)) { // add() returns 'true' when it is not a duplicate value.                         next = line;                         return true;                     }                 }             } catch(IOException e) { }              return false;         }          public String next() {             if(next == null) {                 if(! hasNext() ) throw new NoSuchElementException();             }              final String temp = next;             next = null;             return temp;         }          public void remove() {             throw new UnsupportedOperationException();         }     }      // For testing     public static void main(String... args) {         final StringReader r = new StringReader("value1\nvalue6\nvalue1\nvalue3\nvalue3\nvalue6\nvalue1\nvalue6");          for(final String value : new UniqueValues(new BufferedReader(r)) ) {             System.out.println(value);         }          /* Output is (order is not important):          *           * line 1          * line 6          * line 3          */     } } 

Does it have any better algorithm to do this?

     

Lista de respuestas

8
 
vote
vote
La mejor respuesta
 

Hay tres problemas significativos que abordaría aquí ...

  • Ratchet Freak tiene razón acerca de estar preocupado por el iterador / filtro de filtro ... pero no estoy de acuerdo con su sugerencia. Creo que el problema es que su código está convirtiendo a un lector de tampones en un iterador, y haciendo que los resultados sean únicos al mismo tiempo. Esta es una clase que está realizando 2 funciones ... y deberías tener dos clases en su lugar. Uno que convierte el lector tamponado a un interantero, y el otro que hace cumplir la singularidad.

  • Si sus datos de entrada realmente son enormes, entonces un conjunto puede no ser la estructura de datos correcta debido a su huella de memoria. He encontrado que las implementaciones personalizadas de estructuras de eficiencia de la memoria pueden ahorrar mucho espacio. Sin embargo, dudo en recomendar que cambie del conjunto, sin embargo, es la opción 'lógica', pero, si, por ejemplo, su valor de cadena promedio es de aproximadamente 16 caracteres, entonces más de la mitad de su memoria estará en la sobrecarga establecida. Tengo, en el pasado, tenía razones para hacerte cosas similares, y he escrito una clase que puede ser una clase que puede ser visto en Jdom aquí (deberá realizar cambios en ese código si desea usarlo porque tendrá que tener un mecanismo para un verdadero / falso seen-it prueba).

  • Tengo un patrón que utilizo para los iteradores que es realmente efectivo, y hace que la lógica del iterador sea mucho más simple / legible. Te daré un ejemplo ...

Primero, Parte 1, una implementación de lector-iterator:

  import java.io.BufferedReader; import java.io.IOException; import java.io.Reader; import java.util.Iterator; import java.util.NoSuchElementException;   @SuppressWarnings("javadoc") public class ReaderLineIterator implements Iterator<String> {      private final BufferedReader reader;     private String nextval;      public ReaderLineIterator(Reader reader) {         this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader :             new BufferedReader(reader);          advance();      }      private void advance() {         try {             nextval = reader.readLine();         } catch (IOException ioe) {             throw new IllegalStateException("Unable to read from reader.", ioe);         }     }      @Override     public boolean hasNext() {         return nextval != null;     }      @Override     public String next() {         if (nextval == null) {             throw new NoSuchElementException();         }         try {             return nextval;         } finally {             advance();         }     }      @Override     public void remove() {         throw new UnsupportedOperationException();     }  }   

Nota Cómo, en esta clase, utilizo un truco para el nextval , donde se avanza en el bloque Finalmente de la llamada 9988776665544333 . Este es un patrón que me gusta porque hace que el método 99887766655443344 sea muy ligero, y siempre es un paso adelantado a los datos.

Por lo tanto, es decir, una clase de un solo propósito, convierte un 9988776655544335 a una línea AT-A-Time Iterator .

Ahora, necesita un 99887766555544337

  import java.util.HashSet; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Set;   @SuppressWarnings("javadoc") public class UniqueIterator implements Iterator<String> {      private final Iterator<String> source;     private String nextval = null;     Set<String> seenit = new HashSet<String>();      public UniqueIterator(Iterator<String> source) {         this.source = source;         advance();     }      private void advance() {         while (source.hasNext()) {             String nxt = source.next();             if (seenit.add(nxt)) {                 // found a unique value....                 nextval = nxt;                 return;             }         }         // no more unique values.         nextval = null;      }        @Override     public boolean hasNext() {         return nextval != null;     }      @Override     public String next() {         if (nextval == null) {             throw new NoSuchElementException();         }         try {             return nextval;         } finally {             advance();         }     }      @Override     public void remove() {         throw new UnsupportedOperationException();     }  }   

 

There are three significant issues I would address here...

  • Ratchet Freak is right about being concerned about the Iterator/FilteredReader... but I disagree with his suggestion. I think the problem is that your code is converting a BufferedReader in to an Iterator, and making the results unique at the same time. This is a class that is performing 2 functions... and you shoould have two classes instead. One that converts the BufferedReader to an interator, and the other that enforces uniqueness.

  • If your input data really is huge, then a Set may not be the right data structure because of it's memory footprint. I have found that custom implementations of memory-efficient structures can save a lot of space. I hesitate to recommend that you change from the Set though, it is the 'logical' choice, but, if, for example, your average String value is about 16 characters, then more than half of your memory will be in the Set overhead. I have, in the past, had reason to do similar things to you, and have written a memory-efficient class that can be seen in JDOM here (you will need to make changes to that code if you want to use it because it will need to have a mechanism for a true/false seen-it test).

  • I have a pattern I use for Iterators that is really effective, and makes the Iterator logic much simpler/readable. I'll give you an example....

First, part 1, a Reader-to-Iterator implementation:

import java.io.BufferedReader; import java.io.IOException; import java.io.Reader; import java.util.Iterator; import java.util.NoSuchElementException;   @SuppressWarnings("javadoc") public class ReaderLineIterator implements Iterator<String> {      private final BufferedReader reader;     private String nextval;      public ReaderLineIterator(Reader reader) {         this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader :             new BufferedReader(reader);          advance();      }      private void advance() {         try {             nextval = reader.readLine();         } catch (IOException ioe) {             throw new IllegalStateException("Unable to read from reader.", ioe);         }     }      @Override     public boolean hasNext() {         return nextval != null;     }      @Override     public String next() {         if (nextval == null) {             throw new NoSuchElementException();         }         try {             return nextval;         } finally {             advance();         }     }      @Override     public void remove() {         throw new UnsupportedOperationException();     }  } 

Note how, in this class, I use a trick for the nextval, where it is advanced in the finally block of the next() call. This is a pattern I like because it makes the hasNext() method very light-weight, and it is always a step-ahead of the data.

So, that is a single-purpose class, it converts a Reader to a line-at-a-time Iterator.

Now, you need a unique Iterator... which can look something like:

import java.util.HashSet; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Set;   @SuppressWarnings("javadoc") public class UniqueIterator implements Iterator<String> {      private final Iterator<String> source;     private String nextval = null;     Set<String> seenit = new HashSet<String>();      public UniqueIterator(Iterator<String> source) {         this.source = source;         advance();     }      private void advance() {         while (source.hasNext()) {             String nxt = source.next();             if (seenit.add(nxt)) {                 // found a unique value....                 nextval = nxt;                 return;             }         }         // no more unique values.         nextval = null;      }        @Override     public boolean hasNext() {         return nextval != null;     }      @Override     public String next() {         if (nextval == null) {             throw new NoSuchElementException();         }         try {             return nextval;         } finally {             advance();         }     }      @Override     public void remove() {         throw new UnsupportedOperationException();     }  } 
 
 
       
       
4
 
vote

Tiene un algoritmo de Time O (n) usando O (N) Space No veo cuánto mejor puede ser esto sin usar un almacén de datos externo o un 9988777655544339

Llamar a HaskAnT adelantará la entrada varias veces, lo que no es lo que desea. para solucionar la prueba si la siguiente ya está configurada:

  import java.io.BufferedReader; import java.io.IOException; import java.io.Reader; import java.util.Iterator; import java.util.NoSuchElementException;   @SuppressWarnings("javadoc") public class ReaderLineIterator implements Iterator<String> {      private final BufferedReader reader;     private String nextval;      public ReaderLineIterator(Reader reader) {         this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader :             new BufferedReader(reader);          advance();      }      private void advance() {         try {             nextval = reader.readLine();         } catch (IOException ioe) {             throw new IllegalStateException("Unable to read from reader.", ioe);         }     }      @Override     public boolean hasNext() {         return nextval != null;     }      @Override     public String next() {         if (nextval == null) {             throw new NoSuchElementException();         }         try {             return nextval;         } finally {             advance();         }     }      @Override     public void remove() {         throw new UnsupportedOperationException();     }  } 0  

Sin embargo, creo que import java.io.BufferedReader; import java.io.IOException; import java.io.Reader; import java.util.Iterator; import java.util.NoSuchElementException; @SuppressWarnings("javadoc") public class ReaderLineIterator implements Iterator<String> { private final BufferedReader reader; private String nextval; public ReaderLineIterator(Reader reader) { this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader : new BufferedReader(reader); advance(); } private void advance() { try { nextval = reader.readLine(); } catch (IOException ioe) { throw new IllegalStateException("Unable to read from reader.", ioe); } } @Override public boolean hasNext() { return nextval != null; } @Override public String next() { if (nextval == null) { throw new NoSuchElementException(); } try { return nextval; } finally { advance(); } } @Override public void remove() { throw new UnsupportedOperationException(); } } 1 no es la interfaz correcta para esto, en su lugar, considere usar un import java.io.BufferedReader; import java.io.IOException; import java.io.Reader; import java.util.Iterator; import java.util.NoSuchElementException; @SuppressWarnings("javadoc") public class ReaderLineIterator implements Iterator<String> { private final BufferedReader reader; private String nextval; public ReaderLineIterator(Reader reader) { this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader : new BufferedReader(reader); advance(); } private void advance() { try { nextval = reader.readLine(); } catch (IOException ioe) { throw new IllegalStateException("Unable to read from reader.", ioe); } } @Override public boolean hasNext() { return nextval != null; } @Override public String next() { if (nextval == null) { throw new NoSuchElementException(); } try { return nextval; } finally { advance(); } } @Override public void remove() { throw new UnsupportedOperationException(); } } 2

 

you have a O(n) time algorithm using O(n) space I don't see how much better this can be without using an external data store or a RandomAccessFile

calling hasNext will advance the input several times which is not what you want. to fix test if next is already set:

public boolean hasNext() {     try {         if(next!=null)return true;         String line;         while((line = r.readLine()) != null) {             if(values.add(line)) { // add() returns 'true' when it is not a duplicate value.                 next = line;                 return true;             }         }     } catch(IOException e) { }      return false; } 

however I believe that Iterator is not the right interface for this, instead consider using a FilteredReader

 
 

Relacionados problema

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

1  Retire todos los nodos que no se encuentren en ningún camino con suma> = k  ( Remove all nodes which dont lie in any path with sum k ) 
Dado un árbol binario, una ruta completa se define como un camino desde la raíz a una hoja. La suma de todos los nodos en ese camino se define como la suma d...

25  Algoritmo para transformar una palabra a otra a través de palabras válidas  ( Algorithm to transform one word to another through valid words ) 
He estado practicando retroceso y quería saber cómo puedo mejorar mi código. Por ejemplo, no quiero usarlo global. Además, no estoy seguro de si mi código fun...

5  Orden de número más grande en cadena  ( Largest number order in string ) 
Dada una cadena, suponiendo que la cadena sea solo números, reorganice la cadena a la que sea el mayor número posible. a continuación es mi solución al pr...

2  Dos formas de aleatorias aleatoriamente las tarjetas  ( Two ways to randomly shuffle cards ) 
Aquí hay dos implementaciones que escribí para aleatorizar las tarjetas. El primer método ( dt5 ) Selecciona una tarjeta aleatoria, luego lo quita al frent...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

35  Demasiados bucles en la aplicación de dibujo  ( Too many loops in drawing app ) 
Tengo un método que tiene muchos bucles: #ifndef __RUNES_STRUCTURES_H #define __RUNES_STRUCTURES_H /* Runes structures. */ struct Game { char board[2...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos