我正在编写一个问题(引用 --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 秒。它似乎有一个错误或内存泄漏似乎已经耗尽了我生活中所有的快乐。 任何指示/提示将不胜感激。

谢谢

编辑1——

感谢大家的回复，我使用以下 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 毫秒。 我正在按照 rfeak 的建议尝试替换 HashMaps 和 HashSets，我也想知道在这种情况下内存是否有帮助。请指教。

编辑2—— 使用数组重新编码我的算法似乎有效。只是，在不同时间重新提交相同的代码会给我接受的解决方案和超出时间限制:D 我已经想到了另一种使用 HashMap 进一步优化的方法。 非常感谢你们的帮助!

最佳答案

您的程序在本地运行时使用多少内存？

如果他们在没有足够内存的情况下运行您的 Java 程序，您可能会花费大量时间尝试进行垃圾回收。这可能会毁了你的 1 秒。

如果你需要节省时间和内存(待定......)，我有2个建议。

替换HashSet<Integer>与 BitSet .相似的界面，更快的实现，并且使用更少的内存。尤其是我在问题中看到的数字。

替换Map<Integer,X>用X[] - Integer 键可以简单地是数组中的 int(原始)索引。同样，速度更快，体积更小。

关于Java问题时间限制超出issue，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4903824/