Java의 재귀 알고리즘에서 "완료된 작업" 수를 유지하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/34669

문제

나는 문자열을 문자별로 단계별로 실행하고 이를 구문 분석하여 트리와 같은 구조를 만드는 재귀 알고리즘을 가지고 있습니다.나는 파서가 현재 있는 문자 인덱스를 추적할 수 있기를 원하지만(오류 메시지의 경우) 여러 반환 유형을 처리하기 위해 튜플과 같은 것을 구현하는 데는 관심이 없습니다.

메서드 외부에서 선언하고 재귀 메서드에 전달한 Integer 유형을 사용해 보았지만 그것이 최종이기 때문에 반환할 때 재귀 호출 증분은 "잊혀졌습니다".(정수 값이 증가하면 값으로 전달된 객체 참조 지점이 새 객체를 가리키게 되기 때문입니다)

내 코드를 오염시키지 않는 작업과 유사한 것을 얻을 수 있는 방법이 있습니까?

도움이 되었습니까?

해결책

의사 가변 정수 "해킹"을 이미 발견했으므로 이 옵션은 어떻습니까?

별도의 Parser 클래스를 만드는 것이 합리적입니까?이렇게 하면 현재 상태를 멤버 변수에 저장할 수 있습니다.아마도 스레드 안전 문제를 어떻게 처리할 것인지 생각해야 할 것입니다. 이 특정 응용 프로그램에는 과잉일 수 있지만 귀하에게는 효과가 있을 수 있습니다.

다른 팁

일종의 해킹이지만 때때로 저는 이와 같은 작업을 수행하기 위해 변경 가능한 AtomicInteger를 사용합니다.또한 크기 1의 int[]가 전달되는 경우도 보았습니다.

현재 사용하고 있는 솔루션은 다음과 같습니다.

int[] counter = {0};

그런 다음 재귀 알고리즘에 전달합니다.

public List<Thing> doIt (String aString, int[] counter) { ... }

그리고 그것을 증가시키고 싶을 때 :

counter[0]++;

매우 우아하지는 않지만 작동합니다 ...

정수는 변경할 수 없습니다. 즉, 인수로 전달하면 동일한 항목에 대한 참조가 아닌 복사본이 생성됩니다.(설명).

원하는 동작을 얻으려면 Integer only mutable과 같은 클래스를 직접 작성할 수 있습니다.그런 다음 이를 재귀 함수에 전달하면 재귀 내에서 증가하고 재귀가 끝난 후 다시 액세스하면 여전히 새 값을 유지합니다.

편집하다:int[] 배열을 사용하는 것은 이 방법의 변형입니다.Java에서는 배열도 기본 요소나 불변 클래스처럼 복사되지 않고 참조로 전달됩니다.

doIt 메소드가 호출될 때마다 증가하는 정적 int 클래스 변수를 사용할 수 있습니다.

다음을 수행할 수도 있습니다.

private int recurse (int i) {

    if (someConditionkeepOnGoing) {
        i = recurse(i+1);
    }

    return i;
}

솔직히 말해서 저는 함수를 다시 코딩하여 루프를 사용하는 선형 알고리즘으로 만들겠습니다.이렇게 하면 매우 큰 문자열을 단계별로 실행하는 경우 힙 공간이 부족해질 가능성이 없습니다.또한 개수를 추적하기 위해 추가 매개변수가 필요하지 않습니다.

이는 또한 모든 문자에 대해 함수 호출을 수행할 필요가 없기 때문에 알고리즘을 더 빠르게 만드는 결과를 가져올 수도 있습니다.

물론 재귀적이어야 하는 특별한 이유가 없다면 말이죠.

내가 생각할 수 있는 한 가지 가능성은 클래스의 멤버 변수에 개수를 저장하는 것입니다.물론 이는 대중이 doIt 메소드는 단일 스레드에서만 호출됩니다.

또 다른 옵션은 공용 메서드를 리팩터링하여 개인 도우미 메서드를 호출하는 것입니다.개인 메소드는 목록을 매개변수로 사용하고 개수를 반환합니다.예를 들어:

public List<Thing> doIt(String aString) {
    List<Thing> list = new ArrayList<Thing>();
    int count = doItHelper(aString, list, 0);
    // ...
    return list;
}

private int doItHelper(String aString, List<Thing> list, int count) {
    // ...
    // do something that updates count
    count = doItHelper(aString, list, count);
    // ...
    return count;
}

이는 공개적으로 오류 처리를 수행할 수 있다고 가정합니다. doIt 방법은 이후 count 변수는 실제로 호출자에게 다시 전달되지 않습니다.그렇게 해야 한다면 물론 예외를 던질 수도 있습니다.

public List<Thing> doIt(String aString) throws SomeCustomException {
    List<Thing> list = new ArrayList<Thing>();
    int count = doItHelper(aString, list, 0);
    // ...
    if (someErrorOccurred) {
        throw new SomeCustomException("Error occurred at chracter index " + count, count);
    }
    return list;
}

알고리즘이 실제로 어떻게 작동하는지 자세히 알지 못하면 이것이 도움이 될지 여부를 알기가 어렵습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top