logo标签列表

Java问题：时间限制超出问题

javaalgorithmexecution-time
6

我正在编写一个问题（参考链接 -- 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毫秒。我正在尝试替换HashMaps和HashSets，正如rfeak建议的那样，并且也在思考在这种场景下使用记忆化是否有帮助。请给予建议。
编辑2 - 重新编写我的算法，使用数组似乎已经奏效。不过，有时候重新提交相同的代码会得到接受的解决方案和超时限制:D 我已经想到了另一种使用HashMaps进一步优化的方法。 感谢大家的帮助！
3
你有没有考虑过他们正在给它输入更大的数据，而你的代码处理它需要太长时间了？ - MK.
你知道他们提交的数据集有多大吗？你能获取到那个数据集吗？ - Mark Robinson
1
你能解释一下代码背后的思想以及它的复杂度吗？你尝试过在没有 try/catch 行的情况下提交代码吗？你永远不应该向在线评测机提交带有错误检查的代码。这只会减慢程序的运行速度，而且一个值得尊敬的评测机永远不会提供错误数据给你。 - IVlad
当没有捕获到异常时，try/catch块是免费的，不是吗？他没有进行错误检查，而是进行了（某种程度上的）异常吞噬。 - maaartinus
@IVlad -- 感谢您的建议。然而，删除异常检查并没有帮助。代码背后的基本思想是，我在哈希映射中存储所有与输入中提供的链接相关的菜肴，并默认将第一道菜分配给第1轮，并维护一个结果的哈希映射<Integer，Arraylist>，表示哪些菜肴在哪一轮出现（轮次是哈希映射的键）。现在，对于每道菜，我从最高轮值开始迭代哈希映射，检查以下2个条件-- 条件见下一条评论。 - Jcoder
显示剩余2条评论
1个回答
7
当您在本地运行程序时，它使用多少内存？
如果他们在没有足够内存的情况下运行Java程序，则您可能会花费大量时间尝试进行垃圾回收。这可能会破坏您的1秒时间。
如果您需要节省时间和内存（待确定...），我有两个建议。
用BitSet替换HashSet。类似的接口，更快的实现，并且使用的内存更少。特别是对于我在问题中看到的数字。
将Map替换为X[] - Integer键可以简单地是int（原始）索引到您的数组中。同样，更快，更小。
一定要摆脱 HashSet 和 Map。问题中给出的数字都足够小，可以使用数组（或者 BitSet 可能比数组更快，但我认为在这里不需要）就足够了。 - IVlad
谢谢您的建议。我对BitSet的实现不是很清楚。JavaDoc说它们包含数字的位表示，并支持对它们进行逻辑操作。我不希望主要在输入数据上进行这种操作，但如果这是最实用和最好的方法，我肯定会尝试一下。请给予建议。 - Jcoder
1
@JCoder - 忽略它如何描述其内部表示。最好把BitSet看作是一组int（原始类型）的集合。这个集合要么包含一个整数，要么不包含。要查看是否包含某个整数，请调用BitSet.get（someInt）。要将整数放入集合中，请调用BitSet.set（someInt）。以这种方式，它的行为与Set<Integer>完全相同。 ...现在，如果您真的对为什么它比Set<Integer>小感兴趣，我可以补充我的答案。 - rfeak
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接