带有递归的字符串的java排列无法完成，超过9个字符抛出OfMemoryError

Question

我有一个递归方法，可以在给定的String中找到所有可能的字符组合。递归方法可以完美地处理任何包含9个或更少字母的String。它在大约4秒内用9个字母完成递归方法。然而，一旦有超过9个字母，它就会遇到问题。该方法运行了大约2分钟，大量GC行被写入日志，当进程最终完成时，我得到一个Throwing OutOfMemoryError异常。9个字母以上的字符串要求多少？这一切都是在AsyncTask上完成的

以下是stacktrace：

07-29 12:24:39.335 17389-17389/com.example.test.apptest W/art: Throwing OutOfMemoryError "Failed to allocate a 76 byte allocation with 4194304 free bytes and 12MB until OOM; failed due to fragmentation (required continguous free 4096 bytes for a new buffer where largest contiguous free 0 bytes)" (recursive case)
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art: "main" prio=5 tid=1 Runnable
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   | group="main" sCount=0 dsCount=0 obj=0x73e1e258 self=0xb40f4500
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   | sysTid=17389 nice=0 cgrp=default sched=0/0 handle=0xb77e1c00
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   | state=R schedstat=( 0 0 0 ) utm=899 stm=114 core=1 HZ=100
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   | stack=0xbf326000-0xbf328000 stackSize=8MB
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   | held mutexes= "mutator lock"(shared held)
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   native: #00 pc 0058bd02  /system/lib/libart.so (art::DumpNativeStack(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, int, char const*, art::ArtMethod*, void*)+226)
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   native: #01 pc 0055285e  /system/lib/libart.so (art::Thread::ThrowOutOfMemoryError(char const*)+542)
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   native: #02 pc 0029b6cd  /system/lib/libart.so (art::gc::Heap::ThrowOutOfMemoryError(art::Thread*, unsigned int, art::gc::AllocatorType)+1559)
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   native: #03 pc 002a4a62  /system/lib/libart.so (art::gc::Heap::AllocateInternalWithGc(art::Thread*, art::gc::AllocatorType, unsigned int, unsigned int*, unsigned int*, unsigned int*, art::mirror::Class**)+5218)
07-29 12:24:39.344 17389-17389/com.example.test.apptest W/art:   native: #04 pc 001ade47  /system/lib/libart.so (art::mirror::PrimitiveArray<int>::Alloc(art::Thread*, unsigned int)+2423)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:   native: #05 pc 0054dd6e  /system/lib/libart.so (_jobject* art::Thread::CreateInternalStackTrace<false>(art::ScopedObjectAccessAlreadyRunnable const&) const+298)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:   native: #06 pc 0047fc31  /system/lib/libart.so (art::Throwable_nativeFillInStackTrace(_JNIEnv*, _jclass*)+52)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:   native: #07 pc 0002475e  /data/dalvik-cache/x86/system@framework@boot.oat (Java_java_lang_Throwable_nativeFillInStackTrace__+98)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.Throwable.nativeFillInStackTrace!(Native method)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.Throwable.fillInStackTrace(Throwable.java:166)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.Throwable.<init>(Throwable.java:95)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.Error.<init>(Error.java:48)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.VirtualMachineError.<init>(VirtualMachineError.java:46)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.OutOfMemoryError.<init>(OutOfMemoryError.java:44)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.AbstractStringBuilder.enlargeBuffer(AbstractStringBuilder.java:95)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.AbstractStringBuilder.append0(AbstractStringBuilder.java:146)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.StringBuilder.append(StringBuilder.java:216)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at com.安卓.internal.os.RuntimeInit.Clog_e(RuntimeInit.java:61)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at com.安卓.internal.os.RuntimeInit.-wrap0(RuntimeInit.java:-1)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at com.安卓.internal.os.RuntimeInit$UncaughtHandler.uncaughtException(RuntimeInit.java:94)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.ThreadGroup.uncaughtException(ThreadGroup.java:693)
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:     at java.lang.ThreadGroup.uncaughtException(ThreadGroup.java:690)
07-29 12:24:39.346 17389-17389/com.example.test.apptest I/Process: Sending signal. PID: 17389 SIG: 9

以及递归方法：

//Initial permutation method
public void permutation(String lettersToCombine) {
  permutation("", lettersToCombine);
}

//Recursion method to find all combinations of letters in a given string.
private void permutation(String prefix, String passedLetters) {

    //Set int to the size of the String passed.
    int lengthOfPassedLetters = passedLetters.length();
    //Add the prefix to the ArrayList. 
    if (lengthOfPassedLetters == 0) myList.add(prefix);
    //Loop through this the amount of times of the size of passed letters.
    for (int i = 0; i < lengthOfPassedLetters; i++) {
        /*Call this same method every time the loop is entered. Setting prefix to the character at position of i
        prefix is passed into the method for first argument. For the second argument another String is passed containing
        the second argument made up of the letters already processed and the letters left too.
        */
        permutation(prefix + passedLetters.charAt(i), passedLetters.substring(0, i) + passedLetters.substring(i + 1,
                lengthOfPassedLetters));
    }

Answer 1

背后的真正问题是字符串对象直到方法完成才显示。当然，这是递归的，所以直到最后一个方法调用结束它才会结束

1. 我建议使用StringBuilder
2. 也许是阵列
3. 您可以尝试设置本地 将变量设置为null
4. 我建议你使用循环

如果您仍然无法解决它，我将尝试帮助您编写一些代码

package pruebas;

import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.function.Consumer;

/**
 *
 * @author Oscar
 */
public class Permutations {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        new PermutatedResult("ABCDEFGHIJKLMNÑOPQRSTUVWXYZ").printPermutations();
    }

}

class PermutatedResult {

    private String input;

    public PermutatedResult(String input) {
        this.input = input;
    }

    public void printPermutations() {

        deferredProcess(s -> System.out.println(s));
    }

    public String[] getPermutations() {
        ArrayList<String> list = new ArrayList<String>((int)Math.pow(2, input.length()));
        deferredProcess(s -> list.add(s));

        return list.toArray(new String[input.length()]);
    }

    public void deferredProcess(Consumer<String> actionForEverySolution) {

        int length = input.length();
        long combinations = (long) Math.pow(2, length);

        StringBuilder combination = new StringBuilder(length);
        for (long i = 0; i < combinations; i++) {

            for (int j = 0; j < length; j++) {

                if (((i >> j) & 1) == 1) {
                    combination.append(input.charAt(j));
                }
            }
            actionForEverySolution.accept(combination.toString());
            combination.setLength(length);
        }
    }
}

下面是一些代码，明天我将优化/重构并解释它。它适用于64个长度的字符串，但由于它是一个bruteforce算法，因此需要一个will

编辑：

一些代码可以使用近ant长度（Integer.MAX_值）并且非常快（14秒内2**27个组合）。在代码中，我使用了一个迭代器，以避免存储所有的组合并保存RAM。因此，您必须遍历PermutatedResult以获取值并使用它们。如果您想要超过该长度，这是可能的，但是我们需要一个字节[]，而不是一个字节[]。如果算法仍然需要很多时间，我可以尝试使用多线程来加速和优化它

package pruebas;

import java.util.Iterator;

public class Permutations {

    public static void main(String[] args) {

        PermutatedResult result = new PermutatedResult("ABCDEFGHIJKLMNÑOPQRSTUVWXYZ");

        int combinaciones = 0;
        while (result.hasNext()) {
            combinaciones++;
            result.next(); // This line or the next
            //System.out.println(result.next());
        }
        System.out.println(combinaciones);
    }
}

class PermutatedResult implements Iterator<String> {

    private char[] input;
    private Boolean next;
    private byte[] lastCombination;
    private StringBuilder combination;

    public PermutatedResult(String input) {

        /* Some checks, but we need more */
        if (input == null || input.length() == 0) {
            this.next = false;
            return;
        }

        double posibleCombinations = input.length();

        /* Max length of an array... */
        if (posibleCombinations < Integer.MAX_VALUE) {

            this.input = input.toCharArray();
            this.lastCombination = new byte[(int) posibleCombinations];
            this.combination = new StringBuilder(this.input.length);
            this.next = true;
            this.nextCombination();
        }
    }

    @Override
    public boolean hasNext() {
        return this.next;
    }

    @Override
    public String next() {

        if (!next)
            return null;

        combination.setLength(0);

        for (int i = 0; i < input.length; i++) {

            if (lastCombination[i] == 1) /* If we have to use the letter at this position... */
                combination.append(input[i]);
        }

        this.nextCombination();
        return combination.toString();
    }

    private void nextCombination() {

        int remainder = 1;
        int length = lastCombination.length;
        int sum;

        /* Sum 1 to the bits -> 1111 + 1 = 10000 */
        for (int i = 0; remainder == 1 && i < length; i++) {
            sum = ++lastCombination[i];
            remainder = sum >> 1; // This will got the remainder -> 1 + 1 = 10 so shifting (10 >> 1) we got 1 as remainder.
            lastCombination[i] = (byte) (sum & 1); // With this we only take the last bit so 1 + 1 = 10 -> 10 & 1 = 0
        }

        next = remainder != 1; // If there is some remainder we end all the array and finish
    }
}

Answer 2

要计算字符串的排列，我们需要n！callstack，其中n是字符串的长度。调用堆栈是有限制的。这就是为什么极客在使用递归之前警告您

Answer 3

您的代码在内存方面非常不足。10个字母的排列是10！~350万-这使您可以估计一直在创建和销毁的字符串对象，从而导致内存碎片

failed due to fragmentation (required continguous free 4096 bytes for a new buffer where largest contiguous free 0 bytes)