Java problema de límite de tiempo excedido tema

Question

Im un problema de codificación (--http referencia: //www.codechef.com/FEB11/problems/THREECLR/)

La continuación es mi código

import java.io.*; 
import java.util.*; 


public class Main { 

static String ReadLn (int maxLg) // utility function to read from stdin 
    { 
     byte lin[] = new byte [maxLg]; 
     int lg = 0, car = -1; 
     String line = ""; 

     try 
     { 
      while (lg < maxLg) 
      { 
       car = System.in.read(); 
       if ((car < 0) || (car == '\n')) break; 
       lin [lg++] += car; 
      } 
     } 
     catch (IOException e) 
     { 
      return (null); 
     } 

     if ((car < 0) && (lg == 0)) return (null); // eof 
     return (new String (lin, 0, lg)); 
    } 

public static boolean iscontains(HashMap<Integer,HashSet<Integer>> resultmap,HashSet<Integer> b, int index) 
{ 
    boolean result=false; 
    for(Iterator<Integer> iter = b.iterator();iter.hasNext();) 
     { int tmp=Integer.valueOf(iter.next().toString()); 
      if(resultmap.get(index).contains(tmp)) 
        result=true;     
     } 

    return result; 
} 


public static void main(String[] args) throws InterruptedException, FileNotFoundException { 
    try { 

    HashMap<Integer,HashSet<Integer>> pairlist = new HashMap<Integer,HashSet<Integer>>(); 
    String input=null; 
    StringTokenizer idata; 
    int tc=0; 
    input=Main.ReadLn(255); 
    tc=Integer.parseInt(input); 
    while(--tc>=0) 
    { 
     input=Main.ReadLn(255); 
     idata = new StringTokenizer (input);idata = new StringTokenizer (input); 
     int dishnum= Integer.parseInt(idata.nextToken()); 
     int pairnum= Integer.parseInt(idata.nextToken()); 
     while (--pairnum>=0) 
     { 
      input=Main.ReadLn(255); 
      idata = new StringTokenizer (input);idata = new StringTokenizer (input); 
      int dish1=Integer.parseInt(idata.nextToken()); 
      int dish2=Integer.parseInt(idata.nextToken()); 
      if(pairlist.containsKey((Integer)dish1)) 
      { 
       HashSet<Integer> dishes=new HashSet<Integer>(); 
       dishes=pairlist.get(dish1); 
       dishes.add(dish2); 
       pairlist.put(dish1, dishes); 
      } 
      else 
      { 
       HashSet<Integer> dishes=new HashSet<Integer>(); 
       dishes.add(dish2); 
       pairlist.put(dish1, dishes); 
      } 
     } 
     int maxrounds=1; 
     HashMap<Integer,HashSet<Integer>> resultlist = new HashMap<Integer,HashSet<Integer>>(); 
     HashSet<Integer> addresult=new HashSet<Integer>(); 
     addresult.add(1); 
     resultlist.put(1,addresult); 
     System.out.print("1"); 
     for(int i=2;i<=dishnum;i++) 
     { 
      boolean found_one=false; 
      boolean second_check=false; 
      int minroundnum=maxrounds; 
      boolean pairlistcontains=false; 
      pairlistcontains=pairlist.containsKey(i); 
      for(int j=maxrounds;j>=1;j--) 
      { 
       if(!found_one){ 
       if(pairlistcontains) 
       { 
        if(!iscontains(resultlist,pairlist.get((Integer) i),j)) 
        { 
         for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();) 
         { 
          if(pairlist.get(resultiter.next()).contains(i)) 
           second_check=true; 
         } 
         if(second_check==false) 
         { 
          found_one=true; 
          minroundnum=j; 
          j=0; 
          //second_check=false; 
         } 
        } 

       } 
       else 
       { 
        for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();) 
        { 
         if(pairlist.get(resultiter.next()).contains(i)) 
          second_check=true; 
        } 
        if(second_check==false) 
        { 
         found_one=true; 
         minroundnum=j; 
         j=0; 
         //second_check=false; 
        } 

       } 
       second_check=false; 


      } 
     } 
      if((minroundnum==maxrounds)&&(found_one==false)) 
       { 
       ++minroundnum; 
       ++maxrounds; 
       } 
      else 
      { 
       found_one=false; 
      } 
      HashSet<Integer> add2list=new HashSet<Integer>(); 
      if(resultlist.containsKey(minroundnum)) 
      { 
       add2list=resultlist.get(minroundnum); 
       add2list.add(i); 
      } 
      else 
      { 
       add2list.add(i); 
      } 
      resultlist.put(minroundnum,add2list); 
      System.out.print(" "); 
      System.out.print(minroundnum); 


     } 
     if((tc !=-1)) 
      System.out.println(); 

    } 


    } 
    catch(Exception e){System.out.println(e.toString());} 
}} 

Revisé este código en jueces en línea como Ideone y obtuve los resultados deseados. Pero cuando envío este código, obtengo un error de Límite de tiempo excedido. He probado este código en Ideone con un conjunto suficientemente grande de entrada y el tiempo necesario para ejecutar fue menor a 1 segundo. Parece tener un error o una pérdida de memoria que parece haber agotado toda la felicidad de mi vida. Cualquier punteros/consejos sería muy apreciado.

Gracias

EDIT1 -

Gracias por las respuestas chicos, me encontré con el código con la entrada generada por la siguiente secuencia de comandos Python -

import random 
filename="input.txt" 
file=open(filename,'w') 
file.write("50") 
file.write("\n") 
for i in range(0,50): 
     file.write("500 10000") 
     file.write("\n") 
     for j in range(0,10000): 
       file.write(str(random.randrange(1,501))+" "+str(random.randrange(1,501))) 
       file.write("\n") 
file.close() 

Y mi código tomaron la friolera 71052 milisegundos para ejecutar en la entrada proporcionada por el script anterior. Ahora tengo que bajar el tiempo de ejecución a 8000 milisegundos por lo menos. Estoy trabajando en probar la sustitución de los HashMaps y los HashSets como lo sugiere rfeak y también me pregunto si la memoria ayudaría en este escenario. Por favor avise.

EDIT2 - Recodificar mi algo utilizando matrices parece haber funcionado. Sin embargo, volver a enviar el mismo código en diferentes momentos me da una solución aceptada y un límite de tiempo excedido: D Tengo pensado otra forma de usar hashmaps para optimizar un poco más. ¡Gracias a todos por la ayuda chicos!

Answer 1

¿Cuánta memoria usa su programa cuando se ejecuta localmente?

Si están ejecutando su programa Java sin suficiente memoria, podría estar pasando mucho tiempo intentando recolectar la basura. Esto podría destruir tu 1 segundo vez.

Si necesita ahorrar tiempo y memoria (Por determinar ...), tengo 2 sugerencias.

Reemplazar con BitSet. Interfaz similar, implementación mucho más rápida y usa mucha menos memoria. Especialmente con los números que veo en el problema.

Reemplace Map<Integer,X> con X[] - La clave Entero puede simplemente ser un índice int (primitivo) en su matriz. De nuevo, más rápido y más pequeño.