Intervista Coding Java Sorting

Question

Scrivere un programma java per leggere l'input da un file e quindi ordinare i caratteri all'interno di ogni parola. Dopo averlo fatto, ordina tutte le parole risultanti in ordine crescente e infine segui la somma dei valori numerici nel file.

• Rimuovere i caratteri speciali e smettere di parole durante l'elaborazione dei dati
• Misurare il tempo necessario per eseguire il codice

Diciamo che il contenuto del file è: Sachin Tendulkar ha segnato 18111 piste ODI e 14692 Esecuzioni di prova.

uscita: achins adeklnrtu ADN cdeors dio estt nrsu nrsu 32803

Tempo impiegato: 3 millisecondi

My Code prende 15milliseconds di eseguire .....

per favore mi suggeriscono un modo veloce per risolvere questo problema ...........

Codice:

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

L'unica cosa che vedo: la riga seguente è inutilmente costoso:

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

Questo perché print is inefficient, due to all the flushing going on. Invece, costruire l'intera stringa utilizzando una stringa builder, e poi ridurre a una chiamata di stampa.

Answer 2

Ho rimosso la lista e l'ho letta usando solo gli array, nella mia macchina il codice a 6 msec con il codice, usando solo gli array che richiedevano da 4 a 5 msec. Esegui questo codice nella tua macchina e fammi sapere l'ora.

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

Usa indexOf() per estrarre parole dalla stringa invece di split(" "). Migliora le prestazioni.

Vedi questa discussione: Performance of StringTokenizer class vs. split method in Java

Inoltre, cercare di aumentare la dimensione della produzione, copiare e incollare la linea Sachin Tendulkar ha segnato 18111 piste ODI e 14692 test viene eseguito. 50.000 volte nel file di testo e misurare le prestazioni. In questo modo, sarai in grado di notare una notevole differenza di tempo quando proverai diverse ottimizzazioni.

EDIT

Testato questo codice (utilizzato .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"); 

prestazioni usando 1 riga nel file di
tuo codice: 3 ms
mio codice: 2 ms

prestazioni utilizzando 50K righe nel file di
tuo codice: 45 ms
Il mio codice: 32 ms

Come si vede, la differenza è significativa quando la dimensione di ingresso aumenta. Si prega di testarlo sul proprio computer e condividere i risultati.

Answer 4

Ho eseguito lo stesso codice utilizzando un PriorityQueue anziché un elenco. Inoltre, come suggerito da nes1983, la prima creazione della stringa di output, invece di stampare ogni parola singolarmente, aiuta a ridurre il runtime.

Il mio runtime dopo queste modifiche è stato decisamente ridotto.

Answer 5

Ho modificato il codice come questo ulteriore includendo logica @Teja pure e portato a 1 millisecondo da 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); 

giallo piccola utility per eseguire il controllo per una stringa contenente numero invece di espressione regolare :

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

Tempo di inattività prima di chiamare l'operazione di System.out come questa sta bloccando l'operazione.