가장 긴 공통 Subseqence

내가 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined 가장 긴 공통 Subseqence

에 설명 된대로 두 목록의 가장 긴 일반적인 서브를 발견 재귀 알고리즘을 쓰기 위해 노력하고있어 그것은 재귀가 종료 결코 내가 뭘하는지 알아낼 수 없습니다 나타납니다 기타

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2) { 
    return getLongestSequence(list1, list2, list1.size(), list2.size()); 
} 

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2, int list1index, int list2index) { 

    if (list1index == 0 || list2index == 0) { 
     return new ArrayList<ActionType>(); 
    } 

    if (list1.get(list1index-1).equals(list2.get(list2index-1))) { 
     List<ActionType> retVal = getLongestSequence(list1, list2, list1index-1, list2index-1); 
     retVal.add(list1.get(list1index-1)); 
     return retVal; 
    } else { 
     List<ActionType> ret1 = getLongestSequence(list1, list2, list1index, list2index-1); 
     List<ActionType> ret2 = getLongestSequence(list1, list2, list1index-1, list2index); 

     if (ret1.size() > ret2.size()) { 
      return ret1; 
     } else { 
      return ret2; 
     } 
    } 
}

알아내는 데 도움이되는 모든 도움이됩니다. 고맙습니다.

출처

2013-10-19 Ares

디버깅을 시도했습니다. 작은 목록에서는 잘 작동하지만 큰 목록 (~ 1000 개 요소)에서 사용하면 계속 실행됩니다. 비효율적이고 일부 단계는 여러 번 실행되지만 거의 하루 동안 지속적으로 실행되고 있음을 알고 있습니다. – Ares

ActionType 항목 대신 int의 작은 목록을 사용하여 코드를 시도했습니다. 그것은 잘 동작했기 때문에 복잡성/재귀 깊이에 관한 질문 일뿐입니다. 이미 스택 오버 플로우가 발생 했습니까, 아니면 완료되지 않았습니까? –

나는 알고리즘이 결국 완성 될 것이라고 생각하지만, 큰 입력에 대해서는 어느 정도 시간이 걸릴 것으로 보인다. 크기 'n'과 'm'의 입력에 대해서는 'O (n * m)'시간이 필요합니다. 'n = m = 1000'의 경우, 1 시간 이상이 될 것이라고는 기대하지 않지만, 일정한 요소가 테스트를 거치지 않고 무엇인지 말하기는 어렵습니다. –

문제는 복잡합니다. 암기를 구현하면 런타임이 하루 이상에서 수초로 단축되었습니다. 1300 요소 길이 ActionType이 열거입니다 - 내 실행에

, 원래의 목록은 1100입니다

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2) { 
    lcsMemorize = new HashMap<Integer, List<ActionType>>(); 
    return getLongestSequence(list1, list2, list1.size(), list2.size()); 
} 

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2, int list1index, int list2index) { 

    List<ActionType> retVal = lcsMemorize.get(list1index + list2index * 1000000); 

    if (retVal != null) { 
     return retVal; 
    } else if (list1index == 0 || list2index == 0) { 
     retVal = new ArrayList<ActionType>(); 
    } else if (list1.get(list1index-1).equals(list2.get(list2index-1))) { 
     List<ActionType> returned = getLongestSequence(list1, list2, list1index-1, list2index-1); 

     retVal = new ArrayList<ActionType>(returned); 
     retVal.add(list1.get(list1index-1)); 
    } else { 
     List<ActionType> ret1 = getLongestSequence(list1, list2, list1index, list2index-1); 
     List<ActionType> ret2 = getLongestSequence(list1, list2, list1index-1, list2index); 

     if (ret1.size() > ret2.size()) { 
      retVal = ret1; 
     } else { 
      retVal = ret2; 
     } 
    } 

    lcsMemorize.put(list1index + list2index * 1000000, retVal); 

    return retVal; 
}

참고 : 여기에

업데이트 된 알고리즘이다. 이 방법은 많은 메모리를 사용합니다. JVM 힙 크기를 4GB로 늘려야했습니다.

출처

2013-10-21 06:43:54 Ares

답변

관련 문제