Java 中的内存高效 sliding() 函数（类似于 Scala sliding() ）

Question

我正在尝试编写内存高效的 sliding() 方法。这是显示什么是幻灯片的简单示例：

public void sliding() {
    final LinkedList<String> strings = new LinkedList<>();
    strings.add("a");
    strings.add("b");
    strings.add("c");
    strings.add("d");
    strings.add("e");
    strings.add("f");

    final LinkedList<String> slide = new LinkedList<>();
    final int size = strings.size();

    for (int i = 1; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (j + i < size) {
                final StringBuilder builder = new StringBuilder();
                for (int k = j; k < i + j; k++) {
                    builder.append(" ").append(strings.get(k));
                }
                slide.add(builder.toString().trim());
            }
        }
    }

    System.out.println("slide = " + slide);
}

作为输入，我们有 [a,b,c,d,e,f]，作为输出，我们有所有可能的幻灯片：

[a, b, c, d, e, f, a b, b c, c d, d e, e f, a b c, b c d, c d e, d e f, a b c d, b c d e, c d e f, a b c d e, b c d e f]

我想编写函数，它将 array 和 slidesSize 作为参数，return 此 array 的所有幻灯片，长度为 slidesSize。这是示例：

private LinkedList<String> sliding(LinkedList<String> strings, int slidesSize) {
    final int size = strings.size();
    final LinkedList<String> slides = new LinkedList<>();
    for (int j = 0; j <= size; j++) {
        if (j + slicesSize <= size) {
            final StringBuilder builder = new StringBuilder();
            for (int k = j; k < slidesSize + j; k++) {
                builder.append(" ").append(strings.get(k));
            }
            slides.add(builder.toString().trim());
        }
    }
    return slides;
}

当前的问题是，如果我要为此计算所有幻灯片 strings:

    final LinkedList<String> strings = new LinkedList<>();
    final SecureRandom random = new SecureRandom();
    for (int i = 0; i < 600; i++) {
        final String e = new BigInteger(130, random).toString(32);
        strings.add(e);
    }

我得到：

java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:3332)
    at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:137)
    at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:121)
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:421)
    at java.lang.StringBuilder.append(StringBuilder.java:136)

Answer 1

首先，不要使用LinkedList。使用 ArrayList 在 99% 的情况下（包括你的）在 CPU 和内存方面都更有效率。

下一步是动态生成幻灯片，而不是将它们存储在内存中。这是一个涉及 AbstractList:

的示例实现

static List<String> sliding(final List<String> strings, final int slidesSize) {
    final int size = strings.size();
    if(size < slidesSize)
        return Collections.emptyList();
    return new AbstractList<String>() {
        @Override
        public String get(int j) {
            final StringBuilder builder = new StringBuilder();
            for (int k = j; k < slidesSize + j; k++) {
                if(k > j) builder.append(' ');
                builder.append(strings.get(k));
            }
            return builder.toString();
        }

        @Override
        public int size() {
            return size - slidesSize+1;
        }
    };
}

用法：

final List<String> strings = new ArrayList<>();
final SecureRandom random = new SecureRandom();
for (int i = 0; i < 600; i++) {
    final String e = new BigInteger(130, random).toString(32);
    strings.add(e);
}

for(String slide : sliding(strings, 100)) {
    System.out.println(slide);
}

如果你想要一个Java-8的解决方案，你可以很容易地生成幻灯片流：

int slideSize = 100;
IntStream.rangeClosed(0, strings.size()-slideSize)
        .mapToObj(idx -> String.join(" ", strings.subList(idx, idx+slideSize)))
        .forEach(System.out::println);

注意旧 List.subList 方法与新 String.join 方法的用法。

Java 中的内存高效 sliding() 函数（类似于 Scala sliding() ）

Memory efficient sliding() function in Java ( analogue to Scala sliding() )

java

scala

out-of-memory

heap-memory