Algoritmo de diferencia de cadena -- java campo con performance campo con algorithm campo con strings camp codereview Relacionados El problema

String difference algorithm


4
vote

problema

Español

Me gustaría obtener un comentario sobre el código a continuación. ¿Hay alguna manera de mejorar su rendimiento? Tal vez usted conozca los valores de entrada que podrían imprimir una mala salida? La idea del código es contar caracteres únicos de run()2 que no se enumeran en run()3 .

IDEONON.com URL

  run()4  
Original en ingles

I would like to get a feedback about the code below. Is there any way to improve its performance? Maybe you know input values that might print bad output? The idea of the code is to count unique characters from s2 that are not listed in s1.

Ideone.com URL

class Combine {     public static void main(String[] args) throws IOException {         BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));         String s1 = bi.readLine();         String s2 = bi.readLine();          String usedCharacters = "";          for(int i = 0; i < s2.length(); i++) {             String c = Character.toString(s2.charAt(i));             if(!usedCharacters.contains(c) && !s1.contains(c))                  usedCharacters += c;         }          System.out.println(usedCharacters.length());     } } 
           

Lista de respuestas

2
 
vote
vote
La mejor respuesta
 

No hay ningún requisito para informar a los personajes en ningún orden en particular. Como resultado, hay algunos trucos que podemos hacer para mejorar el rendimiento.

Otros trucos para usar son:

  • Trabajo usando primitivos char[] matrices en lugar de cadenas.
  • use mejores nombres de variables

Clasificación de los datos es un buen primer paso:

      char[] expect = bi.readLine().toCharArray();     char[] search = bi.readLine().toCharArray();   

Ahora los ordenamos a ambos:

  Arrays.sort(expect); Arrays.sort(search);   

Luego, nos dirigimos a través de los valores search , y busques caracteres que no aparecen en expect :

  StringBuilder usedCharacters = new StringBuilder(); int searchPos = 0; while (searchPos < search.length) {     int expectPos = Arrays.binarySearch(expect, search[searchPos]);     if (expectPos < 0) {         usedCharacters.append(search[searchPos]);     }     // advance to the next character, may be duplicates.     searchPos++;     while (searchPos < search.length && search[searchPos - 1] == search[searchPos]) {         searchPos++;     } }  return usedCharacters.toString();   

Ahora, ¿cómo se relacionará esto en términos de rendimiento?

Sus bucles de código actuales a través de cada carácter de búsqueda, que es una operación $ O (N) $. Para cada personaje, luego hace una búsqueda a través de personajes previamente buscados, y también los caracteres no buscados. La combinación de estos dos bucles conduce a una operación $ O (NM) $.

En contraste, los ordenadores en los datos de entrada son $ O (n log {n}) $, y $ o (m log {m}) $ y las búsquedas posteriores son $ O ( n log {m}) $

El resultado final será mucho más favorable que $ O (NM) $

 

There is no requirement to report the characters in any particular order. As a result, there's some tricks we can do to improve the performance.

Other tricks to use are:

  • work using primitive char[] arrays instead of Strings.
  • use better variable names

Sorting the data is a good first step:

    char[] expect = bi.readLine().toCharArray();     char[] search = bi.readLine().toCharArray(); 

Now we sort them both:

Arrays.sort(expect); Arrays.sort(search); 

Then, we loop through the search values, and look for characters that do not appear in expect:

StringBuilder usedCharacters = new StringBuilder(); int searchPos = 0; while (searchPos < search.length) {     int expectPos = Arrays.binarySearch(expect, search[searchPos]);     if (expectPos < 0) {         usedCharacters.append(search[searchPos]);     }     // advance to the next character, may be duplicates.     searchPos++;     while (searchPos < search.length && search[searchPos - 1] == search[searchPos]) {         searchPos++;     } }  return usedCharacters.toString(); 

Now, how will this relate in terms of performance?

Your current code loops through each search character, which is an \$O(n)\$ operation. For each character, it then does a search through previously searched characters, and also the unsearched characters. The combination of these two loops leads to a \$O(nm)\$ operation.

In contrast, the sorts on the input data are \$O(n \log{n})\$, and \$O(m \log{m})\$ and the subsequent searches are \$O(n \log{m})\$

The end result will be much more favourable than \$O(nm)\$

 
 
 
 
1
 
vote

Aparte de no usar un mejor algoritmo, hay dos comedores de eficiencia en su código:

  String usedCharacters = ""; ... in loop     usedCharacters += c;   

Esto copia todo el contenido y agrega un solo carácter.

  String c = Character.toString(s2.charAt(i)); ... ....contains(c)   

Está convirtiendo un char en un String char[] expect = bi.readLine().toCharArray(); char[] search = bi.readLine().toCharArray(); 0 . Si bien no hay char[] expect = bi.readLine().toCharArray(); char[] search = bi.readLine().toCharArray(); 1 , 99887766555443312 hace el trabajo.


Una solución simple y eficiente podría ir así:

      char[] expect = bi.readLine().toCharArray();     char[] search = bi.readLine().toCharArray(); 3  

Esto necesita un byte por un posible carácter (hay $ 2 ^ {16} $ de ellos), es decir, 64 kIB. Si le importa, use un 99887776655443314 en su lugar, lo que necesita un bit en lugar de byte y crece según sea necesario (hasta 8 kIB si se producen caracteres muy extraños).

La complejidad es char[] expect = bi.readLine().toCharArray(); char[] search = bi.readLine().toCharArray(); 5 , difícil de batir dado que debe mirar a cada personaje.

 

Apart from not using a better algorithm, there are two efficiency eaters in your code:

String usedCharacters = ""; ... in loop     usedCharacters += c; 

This copies the whole content and adds a single character.

String c = Character.toString(s2.charAt(i)); ... ....contains(c) 

You're converting a char into a String just to be able to use contains(String). While there's no contains(char), indexOf(char) > -1 does the job.


A simple and efficient solution could go like this:

boolean[] seen = new boolean[Character.MAX_VALUE]; // one slot per char StringBuilder result = new StringBuilder();  for (int i=0; i<s1.length; ++i) {     char c = s1.charAt(i);     seen[c] = true; }  for (int i=0; i<s2.length; ++i) {     char c = s2.charAt(i);     if (!seen[c]) {          result.append(c);         seen[c] = true;         } } 

This needs one byte per a possible character (there are \$2^{16}\$ of them), i.e., 64 KiB. If you care, use a BitSet instead, which needs a single bit instead of byte and grows as needed (up to 8 KiB if very strange characters occur).

The complexity is O(s1.length() + s2.length()), hard to beat given that you must look at each character.

 
 
1
 
vote

Enfoque 1:

Traverse primero cadena y almacena las ocurrencias de los caracteres presentes en un hashmap o una matriz booleana.

Traverse a través de la segunda matriz S2 y cuenta la aparición única de sus caracteres.

Enfoque 2:

También puede usar el conjunto de árboles Java para obtener ocurrencias únicas ordenadas de cada cadena y comparar el carácter por carácter o usar char[] expect = bi.readLine().toCharArray(); char[] search = bi.readLine().toCharArray(); 6 en el conjunto de caracteres ordenado.

 

Approach 1:

Traverse first string and store the occurrences of the characters present either in a HashMap or Boolean array.

Traverse through the second array S2 and count the unique occurrence of its characters.

Approach 2:

You can also use the java TreeSet to get sorted single occurrences of each string and compare character by character or use StringUtils.difference on the sorted character set.

 
 
   
   

Relacionados problema

9  Convierta una contraseña a una cadena fonética para usuarios finales  ( Convert a password to a phonetic string for end users ) 
Tanto como lo odio, a veces proporcionar contraseñas a las personas debe hacerse electrónicamente. Cuando hago eso, trato de eliminar cualquier ambigüedad que...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

8  Conversión de STD :: Chrono :: Time_Point to / from std :: string  ( Converting stdchronotime point to from stdstring ) 
Considere estas funciones que permitan convertir checkOnline.sh4 a / FROM checkOnline.sh5 Con un formato Fecha de fecha ". checkOnline.sh6 con uso:...

11  Optimizando el corrector de anagramas Java (comparar 2 cadenas)  ( Optimizing java anagram checker compare 2 strings ) 
Un anagrama es como una mezcla de las letras en una cadena: pots es un anagrama de detener wilma es un anagrama de ilwma Estoy pasando por el ...

10  Función recursiva que genera las permutaciones de una cadena  ( Recursive function that generates the permutations of a string ) 
Estoy buscando una revisión de mi función recursiva que genere las permutaciones de una cadena. ¿Hay mejores formas de hacer esto? var permutations = []; ...

2  Función para borrar un carácter en una cadena  ( Function to erase a character in a string ) 
void chrrem (char arr[], size_t len, size_t pos) { memmove(arr + pos, arr + (pos + 1), (len - pos) + 1); } Se supone que es simplemente rápido. Borra...

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...

1  Imprima todos los tamaños posibles de subsecuencias de cadena en C  ( Print out all possible sizes of subsequences of string in c ) 
Por ejemplo, dada una cadena "abcdefghijk", quiero que mi función se imprima: a, b, c, d, e, f, g, h, i, j, k. ab, bc, cd, de, ef, fg, gh, hi, ij, jk ab...

3  Implementación más portátil de Tolower ()  ( More portable tolower implementation ) 
Me estoy desafiando a intentar intentar escribir una función que sea tan eficiente, portátil y a prueba de fallas posible. La función es muy simple y solo con...

18  Invirtiendo una cadena  ( Reversing a string ) 
Tuve esto como una pregunta de entrevista, y el entrevistador señaló esto. Esto es lo que escribí: //C# Syntax here public string Reverse(string s) { c...




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