Entrevista Codificación Java Clasificación

Question

Escriba un programa java para leer la entrada de un archivo, y luego ordene los caracteres dentro de cada palabra. Una vez que haya hecho eso, ordene todas las palabras resultantes en orden ascendente y finalmente seguidas por la suma de valores numéricos en el archivo.

• Quitar los caracteres especiales y dejar de palabras durante el procesamiento de los datos
• Medir el tiempo necesario para ejecutar el código

Digamos que el contenido del archivo es: Sachin Tendulkar anotó 18111 carreras ODI y 14692 Pruebas corre

de salida: achins adeklnrtu adn cdeors dio ESTT nrsu nrsu 32803

tiempo empleado: 3 milisegundos

Mi Código toma 15milliseconds ejecutar .....

por favor me sugiere ninguna forma rápida de solucionar este problema ...........

Código:

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.util.*; 

public class Sorting { 

    public static void main(String[] ags)throws Exception 
    { 
     long st=System.currentTimeMillis(); 
     int v=0; 
     List ls=new ArrayList(); 
     //To read data from file 
     BufferedReader in=new BufferedReader(
       new FileReader("D:\\Bhive\\File.txt")); 
     String read=in.readLine().toLowerCase(); 
     //Spliting the string based on spaces 
     String[] sp=read.replaceAll("\\.","").split(" "); 
     for(int i=0;i<sp.length;i++) 
     { 
      //Check for the array if it matches number 
      if(sp[i].matches("(\\d+)")) 
       //Adding the numbers 
       v+=Integer.parseInt(sp[i]); 
      else 
      { 
       //sorting the characters 
       char[] c=sp[i].toCharArray(); 
       Arrays.sort(c); 
       String r=new String(c); 
       //Adding the resulting word into list 
       ls.add(r); 
      } 
     } 
     //Sorting the resulting words in ascending order 
     Collections.sort(ls); 
     //Appending the number in the end of the list 
     ls.add(v); 
     //Displaying the string using Iteartor 
     Iterator it=ls.iterator(); 
     while(it.hasNext()) 
      System.out.print(it.next()+" "); 
     long time=System.currentTimeMillis()-st; 
     System.out.println("\n Time Taken:"+time); 
    } 
} 

Answer 1

La única cosa que veo: la siguiente línea es innecesariamente caro:

System.out.print(it.next()+" "); 

Eso es porque print is inefficient, due to all the flushing going on. En su lugar, construir toda la cadena utilizando un constructor de cadena, y luego se reducen a una llamada de impresión.

Answer 2

Eliminé la lista y la leí usando Arrays solamente, en mi máquina el código a 6 mseg con su código, usando Arrays solo toma de 4 a 5 mseg. Ejecute este código en su máquina y avíseme la hora.

import java.io.BufferedReader; 

import java.io.FileReader; 

import java.util.*; 

public class Sorting { 
public static void main(String[] ags)throws Exception 
{ 
    long st=System.currentTimeMillis(); 
    int v=0; 
    //To read data from file 
    BufferedReader in=new BufferedReader(new FileReader("File.txt")); 
    String read=in.readLine().toLowerCase(); 
    //Spliting the string based on spaces 
    String[] sp=read.replaceAll("\\.","").split(" "); 
    int j=0; 
    for(int i=0;i<sp.length;i++) 
    { 
     //Check for the array if it matches number 
     if(sp[i].matches("(\\d+)")) 
      //Adding the numbers 
      v+=Integer.parseInt(sp[i]); 
     else 
     { 
      //sorting the characters 
      char[] c=sp[i].toCharArray(); 
      Arrays.sort(c); 
      read=new String(c); 
      sp[j]= read; 
      j++; 
     } 
    } 
    //Sorting the resulting words in ascending order 
    Arrays.sort(sp); 
    //Appending the number in the end of the list 
    //Displaying the string using Iteartor 
    for(int i=0;i<j; i++) 
     System.out.print(sp[i]+" "); 
     System.out.print(v); 
    st=System.currentTimeMillis()-st; 
    System.out.println("\n Time Taken:"+st); 
} 

} 

Answer 3

Uso indexOf() para extraer palabras de su cadena en lugar de split(" "). Mejora el rendimiento.

Ver este tema: Performance of StringTokenizer class vs. split method in Java

Además, trate de aumentar el tamaño de la salida, copiar y pegar la línea Sachin Tendulkar anotó carreras 18111 14692 ODI y prueba de rachas. 50,000 veces en el archivo de texto y mida el rendimiento. De esta forma, podrá ver una diferencia de tiempo considerable cuando pruebe diferentes optimizaciones.

EDITAR

Probado este código (utilizado .indexOf())

 long st = System.currentTimeMillis(); 
     int v = 0; 
     List ls = new ArrayList(); 
     // To read data from file 
     BufferedReader in = new BufferedReader(new FileReader("D:\\File.txt")); 
     String read = in.readLine().toLowerCase(); 
     read.replaceAll("\\.", ""); 
     int pos = 0, end; 
     while ((end = read.indexOf(' ', pos)) >= 0) { 
      String curString = read.substring(pos,end); 
      pos = end + 1; 
     // Check for the array if it matches number 
      try { 
       // Adding the numbers 
       v += Integer.parseInt(curString); 
      } 
      catch (NumberFormatException e) { 
       // sorting the characters 
       char[] c = curString.toCharArray(); 
       Arrays.sort(c); 
       String r = new String(c); 
       // Adding the resulting word into TreeSet 
       ls.add(r); 
      } 
     } 
     //sorting the list 
     Collections.sort(ls); 
     //adding the number 
     list.add(v); 
     // Displaying the string using Iteartor 
     Iterator<String> it = ls.iterator(); 
     while (it.hasNext()) { 
      System.out.print(it.next() + " "); 
     } 
     long time = System.currentTimeMillis() - st; 
     System.out.println("\n Time Taken: " + time + " ms"); 

rendimiento usando 1 línea en el archivo
Su código: 3 ms
mi código: 2 ms

rendimiento usando 50K líneas en el archivo de
Su código: 45 ms
Mi código: 32 ms

Como se ve, la diferencia es significativa cuando el tamaño de entrada aumenta las. Por favor, pruébela en su máquina y comparta los resultados.

Answer 4

Ejecuté el mismo código usando PriorityQueue en lugar de List. Además, como lo sugirió nes1983, construir primero la cadena de salida, en lugar de imprimir cada palabra individualmente, ayuda a reducir el tiempo de ejecución.

Mi tiempo de ejecución después de estas modificaciones se redujo definitivamente.

Answer 5

I han modificado el código como este aún más mediante la inclusión de lógica @Teja así y dio lugar a 1 milisegundo de 2 millisescond:

long st=System.currentTimeMillis(); 
    BufferedReader in=new BufferedReader(new InputStreamReader(new FileInputStream("D:\\Bhive\\File.txt"))); 
    String read= in.readLine().toLowerCase(); 
    String[] sp=read.replaceAll("\\.","").split(" "); 
    int v=0; 
    int len = sp.length; 
    int j=0; 
    for(int i=0;i<len;i++) 
    { 
      if(isNum(sp[i])) 
      v+=Integer.parseInt(sp[i]); 
      else 
      { 
       char[] c=sp[i].toCharArray(); 
       Arrays.sort(c); 
       String r=new String(c); 
       sp[j] = r; 
       j++; 
      } 
     } 
     Arrays.sort(sp, 0, len); 
     long time=System.currentTimeMillis()-st; 
     System.out.println("\n Time Taken:"+time); 
     for(int i=0;i<j; i++) 
     System.out.print(sp[i]+" "); 
     System.out.print(v); 

Escrito pequeña utilidad para llevar a cabo para el control de una cadena contiene número en lugar de expresión regular :

private static boolean isNum(String cs){ 
    char [] s = cs.toCharArray(); 
    for(char c : s) 
    { 
     if(Character.isDigit(c)) 
     { 
     return true; 
     } 
    } 
    return false; 
} 

Calcule el tiempo antes de llamar al funcionamiento de System.out ya que este está bloqueando la operación.