将递归组合查找算法转换为迭代算法以避免 GC Overhead Limit Exceeded 错误

Question

此算法的目的是生成行程序列列表。每次旅行都有起点和终点。用户指定这两者，并且列表中的每个序列 return 算法最终必须以具有指定起点的行程开始，并以具有指定终点的行程结束。

我想出了一个算法，该算法 return 以具有指定起点的行程开始的每个可能序列（例如，对于起点 A，可能的第一趟行程包括 AB、AC、AD 等。 ).在获得该序列列表后，我的计划是删除所有不以具有指定结束的行程结束的序列（例如，对于结束 C，具有最终行程 BA、CD 和 DB 的序列将从列表中删除）。

public List<ArrayList<Trip>> getTripSequences(List<Trip> tripList, Location start, List<Trip> sequence) {

    List<ArrayList<Trip>> resultList = new ArrayList<ArrayList<Trip>>();

    getTripSequences(tripList, start, sequence, resultList);

    return resultList;
}

private void getTripSequences(List<Trip> tripList, Location start, List<Trip> sequence, List<ArrayList<Trip>> resultList) {
    if (tripList.isEmpty())
        return;

    else {
        for (Trip trip : tripList)

            if (trip.getStart().equals(start)) {

                // intermSq - an intermediary sequence
                ArrayList<Trip> intermSq = new ArrayList<Trip>();

                List<Trip> smallerList = new ArrayList<Trip>();

                smallerList.addAll(tripList);

                intermSq.addAll(sequence);

                intermSq.add(trip);

                resultList.add(intermSq);

                smallerList.remove(trip);

                resultList.addAll(getTripSequences(smallerList, trip.getEnd(), intermSq));      
            }   
     }
}

该算法适用于小行程列表。例如，输入以下可能的行程列表

AB, BA, BC, CA, CB

指定起始点 A 将 return 以下序列：

AB
AB BA
AB BC
AB BC CA
AB BC CB
AB BC CB BA

当然，在这一点之后，我必须删除所有未以正确结束位置结束的序列，但这似乎并不难。当我尝试将其用于具有比我在测试中使用的位置更多的位置的大量行程列表（即 A B C D）时，问题就出现了。我收到此错误：

java.lang.OutOfMemoryError: GC overhead limit exceeded

我是递归概念的新手，所以我没有预料到这个问题，但我现在明白为什么会这样了。我正在尝试决定我应该做什么而不是这个。

这个算法的迭代版本会是什么样子？迭代会使用足够少的内存吗？
仅增加堆大小来避免此错误是个好主意吗？

我试图完全重写算法来解决主要问题（即生成具有指定起点和终点的序列），但我非常卡住。

如有任何帮助，我将不胜感激！

编辑这里是算法中用到的类

public class Location {

    private String continent;
    private String country;

    public Location(){
        super();
    }

    public Location(String continent, String country) {
        super();
        this.continent = continent;
        this.country = country;
    }

    public String getContinent() {
        return continent;
    }

    public void setContinent(String continent) {
        this.continent = continent;
    }

    public String getCountry() {
        return country;
    }

    public void setCountry(String country) {
        this.country = country;
    }   
}

public class Trip {

    private Location start;
    private Location end;

    public Location getStart() {
        return start;
    }

    public void setStart(Location start) {
        this.start = start;
    }

    public Location getEnd() {
        return end;
    }

    public void setEnd(Location end) {
        this.end = end;
    }
}

编辑以下生成器创建了一个列表，其大小与导致我的错误的列表相同。

public class Tester {

    public Trip makeTrip(Location start, Location end) {
        Trip trip = new Trip();
        trip.setStart(start);
        trip.setEnd(end);
        return trip;
    }

    public static void main(String[] args) {

    Tester tester = new Tester();

    ArrayList<Location> locations = new ArrayList<Location>();

    locations.add(new Location("A", "A"));
    locations.add(new Location("B", "B"));
    locations.add(new Location("C", "C"));
    locations.add(new Location("D", "D"));
    locations.add(new Location("E", "E"));
    locations.add(new Location("F", "F"));
    locations.add(new Location("G", "G"));
    locations.add(new Location("H", "H"));
    locations.add(new Location("I", "I"));
    locations.add(new Location("J", "J"));
    locations.add(new Location("K", "K"));
    locations.add(new Location("L", "L"));
    locations.add(new Location("M", "M"));
    locations.add(new Location("N", "N"));
    locations.add(new Location("O", "O"));
    locations.add(new Location("P", "P"));
    locations.add(new Location("Q", "Q"));
    locations.add(new Location("R", "R"));
    locations.add(new Location("S", "S"));
    locations.add(new Location("T", "T"));

    int i = 0;

    Random random = new Random();

    ArrayList<Trip> trips = new ArrayList<Trip>();

    while (i++ < 54) {
        trips.add(tester.makeTrip(locations.get(random.nextInt(20)), locations.get(random.nextInt(20))));
    }

    System.out.println(trips.size());

    for (Trip trip : trips)

    System.out.println(trip.getStart().getCountry() + trip.getEnd().getCountry());
    }
}

Answer 1

听起来像是一个经典的记忆问题。

检查您的代码：您在 for 循环中递归调用 getTripSequences 函数。这根本不是最佳选择。
将内存大小增加到 -Xmx512m 甚至 -Xmx1024m

Answer 2

使用库 (Combinatoricslib) 的数学组合是否使用了相同的算法

这是代码，它使用的内存少得多，但仍然需要很长时间，因为使用蛮力，尝试所有可能的组合并过滤符合规则的组合。

你需要 java 8 来编译这个，检查是否适合你的需要。

The Lib

Algorithm refactored

Answer 3

java.lang.OutOfMemoryError: GC overhead limit 超出不是 "real" 内存不足错误。这意味着 GC 正在尝试运行，但它花费了太长时间来弄清楚它可以清理什么，所以它放弃了。我之前运行在各种复杂的情况下遇到过这个问题，在这些情况下，GC 很难弄清楚它可以释放什么并且是一个边界错误。解决方法是使用JVM参数-XX:-UseGCOverheadLimit。由于您正在执行一些非常昂贵的操作，您可能仍然会遇到内存错误，但它可能会找到一些空闲 space 让您继续。

此外，将这两个变量定义 intermSq 和 smallerList 从 for 循环的中间拉出作为一个小的优化。如果它可能很大，您可能还需要考虑将它们初始化为正确的大小，否则您会进行大量内存改组。

将递归组合查找算法转换为迭代算法以避免 GC Overhead Limit Exceeded 错误

Converting recursive combination-finding algorithm to iterative to avoid GC Overhead Limit Exceeded error

java

iteration

recursion

combinations

garbage-collection