java - 生成大型列表的笛卡尔积时出现 OutOfMemoryError

Question

我正在尝试使用以下代码生成 Java 中的 List 的笛卡尔积:

private static List<List<String>> getCartesian(List<List<String>> initialList) {
    List<List<String>> result = new ArrayList<List<String>>();
    result.add(new ArrayList<String>());
    for (List<String> first : initialList) {
        List<List<String>> temporaryList = new ArrayList<List<String>>();
        for (List<String> second : result) {
            for (String word : first) {
                List<String> tmp2 = new ArrayList<String>(second);
                tmp2.add(word);
                temporaryList.add(tmp2);
            }
        }
        result = temporaryList;
    }
    return result;
}

使用大型列表时出现以下错误:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

我该怎么做才能使其适用于大数据？

Answer 1

您应该尽量避免使用ArrayList对于这样的事情。生成结果所需的所有信息都包含在原始 List<List<String>> 中。 ，因此无需同时将所有答案都存储在内存中。

以下代码生成一个等于 getCartesian 的列表，但它并没有将所有内容存储在一个大的 ArrayList 中。相反，它会复制所有原始列表并根据请求计算单个答案。

public static List<List<String>> getCartesian2(List<List<String>> lists) {
    long size = 1;
    final List<List<String>> copy = new ArrayList<List<String>>();
    for (List<String> list : lists) {
        size *= list.size();
        if (size > Integer.MAX_VALUE)
            throw new IllegalArgumentException();
        copy.add(new ArrayList<String>(list));
    }
    final int fSize = (int) size;
    return new AbstractList<List<String>>() {
        @Override
        public int size() {
            return fSize;
        }
        @Override
        public List<String> get(int i) {
            if (i < 0 || i >= fSize)
                throw new IndexOutOfBoundsException();
            String[] arr = new String[copy.size()];
            for (int j = copy.size() - 1; j >= 0; j--)  {
                List<String> list = copy.get(j);
                arr[j] = list.get(i % list.size());
                i /= list.size();
            }
            return Arrays.asList(arr);
        }
    };
}