递归字符串的排列无法完成超过9个字符 - 抛出OutOfMemoryError

Question

我有一个递归方法，查找给定String中字符的所有可能的组合。递归方法适用于包含9个字母或更少的任何String。它在4秒左右完成9个字母的递归方法。但是，一旦有超过9个字母就会遇到问题。该方法运行大约2分钟，有大量的GC行写入日志，当过程最终完成时，我得到一个Throwing OutOfMemoryError异常。是否有超过9个字母的字符串要求太多？这全部在AsyncTask上完成。

这里是堆栈跟踪：

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.android.internal.os.RuntimeInit.Clog_e(RuntimeInit.java:61) 
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:  at com.android.internal.os.RuntimeInit.-wrap0(RuntimeInit.java:-1) 
07-29 12:24:39.345 17389-17389/com.example.test.apptest W/art:  at com.android.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

背后的真正问题是String对象没有disponse直到方法完成。当然，这是递归的，所以它不会结束，直到最后的方法调用结束。

1. 我建议使用StringBuilder。
2. ¿可能与数组？
3. 您可以尝试将您的本地 变量设置为空。
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个长度的字符串，但它需要一个意愿，因为它是一个强力算法。

编辑：

某些代码与邻近蚂蚁长度（Integer.MAX_VALUE的）工作，并是如此之快（2组** 27的组合14秒）。在代码中，我使用迭代器来存储所有组合并保存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

您的代码在内存方面非常ineffecient。 10个字母的排列是10！约3.5百万 - 这给你一个估计的字符串对象的创建和销毁所有的时间导致内存碎片。

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

Answer 3

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