프로그램 효율성 및 java.lang.OutOfMemoryError : Java 힙 공간

Question

마지막 두 번째 요소가 제거 될 때까지 모든 두 번째 요소를 제거하는 것이 문제입니다. (요소가 원으로 놓여 있다고 가정 할 때)

내 프로그램은 작은 값의 n에서는 잘 작동하지만 큰 값을 사용하면 java.lang.OutOfMemoryError: Java heap space이라는 메시지가 나타납니다.

내 코드를보다 효율적으로 만들고이 오류를 해결하기 위해 내가해야 할 일을 도와 줄 수 있습니까?

감사합니다!

import java.util.*; 

public class ArrayLists { 
    public static void main(String[] args) { 
     ArrayList myList = new ArrayList(); 
     int n = 23987443; 
     for (int i = 1; i <= n; i = i + 2) { 
      myList.add("" + i); 
     } 

     Object x = myList.get(myList.size() - 1); 
     Object y = myList.get(myList.size() - 1); 
     while (myList.size() != 1) { 
      if (x == y) { 
       for (int i = 0; i <= myList.size() - 1; i++) { 
        myList.remove(i); 
       } 
      } 
      else { 
       x = y; 
       for (int i = 1; i <= myList.size() - 1; i++) { 
        myList.remove(i); 
       } 
      } 
      y = myList.get(myList.size() - 1); 
     } 
     System.out.println("Winner:" + myList); 
    } 
} 

Answer 1

문제에 대한 해답은 폐쇄 형으로 계산을위한 사용자가 목록의 요소 수를 작성하는 경우는 다음과 같이 될 수있다 :

N = 2^m + L

를 m은을이고 (2)의 최대 전력 등이 2^m = N <

그 승자는 2 * L + w = ​​1

그래서 여기

보다 효율적인 프로그램이다

012,354

N의 값에 대한 대답 : 나는 솔루션으로 자신을 오지 않았다

Winner:[14420455] 

이 정직하게, 그러나 책 "콘크리트 수학"의 요세푸스 문제에 대한 책을 읽은 기억하고 (구글은 발견 할 것이다 PDF, 체크 아웃 섹션 1.3)

Answer 2

거대한 문자열 목록을 작성 중입니다. 따라서 모든 목록을 담을 수있을만큼 충분한 메모리가 필요합니다. 그 목록이 실제로 포함 된 내용이기 때문에,

int n = 23987443; 
List<String> myList = new ArrayList<String>(23987443); 

당신은 또한 대신 List<Integer>을 사용할 수 있습니다 : 당신은 적은 목록을 확대 임시 복사본을 피하고, 적절한 크기의 목록을 초기화하여 소모 만들 수 있습니다.

그러나 거대한 문자열 목록에는 많은 메모리가 필요합니다. 예를 들어

java -Xmx1024m ... 

(힙 1024 MB)와 힙 크기를 확대

Answer 3

이 적은 메모리를 사용하지만 O(N * log N) 대신

public static void main(String[] args) { 
    // for (int n = 1; n < 400; n++) { 
    int n = 23987443; 
    System.out.print(n + ": "); 
    result(n); 
    // } 
} 

private static void result(int n) { 
    List<Integer> myList = new ArrayList<>(), myList2 = new ArrayList<>(); 
    for (int i = 1; i <= n; i = i + 2) { 
     myList.add(i); 
    } 

    Integer x = myList.get(myList.size() - 1); 
    Integer y = myList.get(myList.size() - 1); 
    while (myList.size() != 1) { 
     if (x == y) { 
      for (int i = 1; i < myList.size(); i += 2) { 
       myList2.add(myList.get(i)); 
      } 
     } else { 
      x = y; 
      for (int i = 0; i <= myList.size() - 1; i += 2) { 
       myList2.add(myList.get(i)); 
      } 
     } 
     List<Integer> tmp = myList2; 
     myList2 = myList; 
     myList = tmp; 
     myList2.clear(); 

     y = myList.get(myList.size() - 1); 
     // System.out.println("\t" + myList); 
    } 
    System.out.println("Winner:" + myList.get(0)); 
} 

O(N^2 * log N)의 주이기 때문에 조금 더 빠른 견적입니다 : ArrayList<Integer> 대신 TIntArrayList를 사용하면 약 1/5의 메모리가 사용됩니다.