Java开发网 - need help for out of memory problem

Java开发网

您没有登录

» Java开发网 » Java SE 综合讨论区

打印话题 寄给朋友 订阅主题

作者

need help for out of memory problem

dorrenchen

发贴: 298
积分: 30

于 2003-09-27 08:35

Hey, all:

I created a class calculating permutations, but my program always run out of memory (JVM peak out and end at around 75M Black Eye

when input element is more than 8. please help.

<code>
package recursive;

import java.util.Arrays;
import java.util.Hashtable;
import java.util.Set;
import java.util.TreeSet;

public class Permutation {
  private Hashtable cache; // used to store calculated result
  public int cacheHit, cachePut;

  public Permutation() {
    super();
    cache = new Hashtable();
  }

  /**
   * This function takes an array of input string, calculate all permutations using
   * all input elements, and return result as array of string too.
   *
   * For example, with input of {"a","b,"c"}, the output will be
   * {"abc", "acb", "bac", "bca", "cab", "cba"}.
   *
   * @param input string array that contains input elements.
   * @return Array of strings contains all permutations.
   */
  public String[] list(String[] input){
    if(input.length == 2){
      return new String[]{input[0] + input[1],input[1] + input[0]};
    }else{
      // ----- create key for caching
      Arrays.sort(input);
      StringBuffer keyB = new StringBuffer();
      for(int i=0; i<input.length; i++){
        keyB.append(input[i]);
      }
      String key = keyB.toString();
      keyB = null;

      /* for input of {"a","b,"c" .....},
       * calculation result is computed as preappend "a" to every string
       * in the result of recursive call list({"b,"c" .....})
       */
      String[] res = (String[])cache.get(key);
      if(res == null){
        Set set = new TreeSet();
        for(int i=0; i<input.length;i++){
          String head = input[i];

          String[] tail = new String[input.length-1];
          for(int j=0; j<input.length-1; j++){
            if(j < i){
              tail[j] = input[j];
            }else{
              tail[j] = input[j+1];
            }
          }

          /* debug
          System.out.print(head+"-");
          for(int z=0; z<tail.length; z++){
            System.out.print(tail[z]);
          }
          System.out.print(", ");
          */

          String[] sub = list(tail);
          for(int k=0; k<sub.length; k++){
            String s = head + sub[k];
            set.add Moon

;
          }
        }
        //System.out.println();

        res = new String[set.size()];
        set.toArray(res);
        cache.put(key, res);
        set = null;
        //System.out.println("put " + key);
        cachePut++;
      }else{
        //System.out.println("hit " + key);
        cacheHit++;
      }
      return res;
    }

  }

  public static void main(String[] args) {
    Permutation p = new Permutation();
    int len = 6;
    String[] input = new String[len];
    for(int i=0; i<len; i++){
      input[i] = ((char)('a'+i)) + "";
    }
    //input[1] = input[0];

    String[] res = p.list(input);
    System.out.println("input count:" + len + " permutations:" + res.length);
    System.out.println("cache put:"+ p.cachePut+ " hit:" + p.cacheHit);

    for(int i=0; i<res.length; i++){
      if(i%10 == 0){
        System.out.println();
      }
      System.out.print(res[i] + "\t");
    }


  }
}

</code>

Permutation.java (2.79k)

话题树型展开

人气	标题	作者	字数	发贴时间
4341	need help for out of memory problem	dorrenchen	3056	2003-09-27 08:35
2578	Re:need help for out of memory problem	archonLing	297	2003-09-27 09:17

已读帖子

新的帖子

被删除的帖子