Javaの問題の時間制限は、問題をコーディング問題

Question

イム（--http参照：//www.codechef.com/FEB11/problems/THREECLR/）を超え以下

を自分のコード

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());} 
}} 

です私はIdeoneのようなオンラインジャッジでこのコードをチェックして、望ましい結果を得ています。しかし、私はこのコードを提出すると、私はタイムリミット超過エラーを取得します。私はIdeone上でこのコードを十分に大きな入力セットでテストし、実行に要した時間は1秒未満でした。それは私の人生からすべての幸福を使い果たしたようだバグまたはメモリリークを持っているようだ。 すべてのポインタ/ヒントを高く評価します。

おかげ

EDIT1 -

回答のみんなのおかげで、私は次の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() 

をそして、私のコードは、なんとしました上記スクリプトが提供する入力に対して実行するのに71052ミリ秒。私は今実行時間を少なくとも8000ミリ秒にまで下げなければなりません。 Imはrfeakによって提案されているようにHashMapsとHashSetを置き換えようと努力していますし、このシナリオでメモ化が役立つかどうかも疑問です。お知らせ下さい。

EDIT2 - 配列を使用して私のalgoを再コーディングしているようです。同じコードを別の時間に再送信するだけで、私はAccepted SolutionとTime Limitを超えることができます：Dもう少し最適化するためにハッシュマップを使用する別の方法があります。 助けを借りてくれてありがとう！

Answer 1

ローカルで実行するときにプログラムがどのくらいのメモリを使用しますか？

十分なメモリがない状態でJavaプログラムを実行している場合、ガベージコレクションに多くの時間を費やしている可能性があります。これはあなたの1秒の時間を破壊する可能性があります。

時間とメモリを節約する必要がある場合（決定するには...）、2つの方法があります。

をBitSetに置き換えます。同様のインタフェース、より高速な実装、そしてはるかに少ないメモリを使用します。特に私が問題に目にしている数字と一緒に。

Map<Integer,X>をX[]に置き換えます。整数キーは、単純に配列のint（プリミティブ）インデックスにすることができます。再び、より速く、より小さく。