我是在一个编程竞赛的最后一个周末(资格赛一轮的ICPC),我试图做的是有关(其中包括)分解整数范围内的问题,0 <= i <= 1,000,000为素数.
我的第一个想法是"哦不,因为整数是在NP,我们需要找到一种方法来避免花时间在它上面." 我们在Java工作.作为主要是一个C程序员,我的第一反应是用一个脚本来预先计算所有的素数高达1,000,000,其格式与Java数组,并试图将其插入到我的代码.我的理由是它节省了我们在定时部分运行类似于Eratosthenes筛子的时间,通过类似n的因子减少时间复杂度,并通过它轻而易举.
然后我被"代码太大"错误命中,我的几十万个int数组被编译器拒绝了.由于竞争规则,无法将其读入文件,或将其存储在除包含具有main方法的类的.java文件之外的任何位置.
我尝试将它分解成类似100,000 int块的东西,但是因为它仍然太大而无法工作(除了Java 7文档之外我们没有任何东西可以查阅,而且我无法找到任何关于"代码太大"的内容错误信息).我们最终放弃了,尝试了另一种方法,并让它运作起来,但它最终耗费了我们总比赛时间的四分之一,并且显着损害了我们的分数.
所以,我的问题是:有什么理智的方法来解决这个问题与查找表？是不是不可能在Java程序中获得一个巨大的预编译查找表？
我也很好奇这种语言限制背后的原因......它是一种安全的东西,不知何故？为什么编译器会限制方法的字节码大小？
| 归档时间： |
|
| 查看次数： |
187 次 |
| 最近记录： |