0

我正在研究 Project Euler 问题 14，但我不明白问题是什么。在程序运行大约 8 秒后，我不断收到运行时错误——可能是 ArrayList 变得太大，但我该如何避免这种情况呢？

import java.util.ArrayList;

public class Problem14 
{
    public static void main(String[] args) 
    {

        ArrayList<ArrayList<Long>>listOfLists=new ArrayList<ArrayList<Long>>();

        for (long c=2; c<1000000; c++)
        {
            ArrayList<Long>tempList=new ArrayList<Long>();
            long h=c;
            while (h!=1)
            {
                tempList.add(h);
                if (h%2==0)
                    h/=2;
                else
                    h=((3*h)+1);
            }
            tempList.add(1l);
            listOfLists.add(tempList);
        }

        long maxLength=0;
        long maxPos=0;

        for (int currList=0; currList<listOfLists.size(); currList++)
        {
            long currLength=(listOfLists.get(currList).size());
            if(currLength>maxLength)
            {
                maxLength=currLength;
                maxPos=currList+1;
            }
        }
        System.out.println("The longest sequence is "+maxLength+" numbers
                long. Its position is "+maxPos);
    }
}
4

5 回答 5

4

您已用尽可用堆内存运行 JVM。问题线是

ArrayList<Long>tempList=new ArrayList<Long>();

这是一个运行一百万次并被保留的循环内部，因此您已经创建了一百万个数组列表。您需要更好的数据结构或使用 -Xmx 的更多内存。

本着 Euler 项目的精神，您应该寻找一种避免列表列表的方法。

于 2012-12-19T18:49:52.033 回答
1

您不需要列表列表。你甚至不需要清单。

如果您查看内部列表，则添加所有值，然后您使用的只是 size()。这意味着您真正需要的就是循环迭代的次数，即一个计数器。你可以存储这是一个列表但是..

一旦确定了所有长度，您对列表所做的一切就是找到最大的。您可以随时记录最大的长度，而不是将长度存储在列表中。

这意味着您不需要使用 List Of Long 对象列表，而是需要迄今为止最大的迭代次数以及起始值。

完成这些更改后，您可以进一步优化代码。

于 2012-12-19T20:02:57.563 回答
0

由于问题定义，很少有想法：

首先，您不需要为您的号码保存所有链，这意味着根本不需要列表列表。您只需要保存它产生的数字和链长度。由于最大。它只是两个整数而不是大量列表。

顺便说一句，您可以添加缓存以节省已计算序列的长度。例如 Map 将包含它产生的链的数量和长度，这样你重写你的算法，在计算一个数字的链长度之前，它会检查缓存是否存在。它节省了很多时间。

于 2012-12-19T18:59:06.990 回答
0

使用 -Xmx 参数增加 JVM 内存

于 2012-12-19T18:48:19.737 回答
-1

我假设您没有在命令行上编码。如果您只是使用 -Xmx 参数（然后是数字）将起作用......如果不是，您可以在 Eclipse 中添加类似的参数。右键单击您运行项目的类，进入“运行方式”，然后“运行配置”

在那里你应该看到和“参数”标签......在那里添加你的 -Xmx 标签和一个数字

-Xmx 2048

可能有用...祝你一切顺利

于 2012-12-19T19:34:46.927 回答