자바에서 대형 목록에 대한 최상의 목록 구현은 무엇입니까

Question

큰 요소 목록을 작성해야합니다 (최대 100,000 개까지 가능). 목록의 각 요소는 목록의 색인과 동일한 정수입니다. 그 후이 목록에서 Collections.shuffle을 호출해야합니다. 내 질문은 어떤 목록 구현 (자바 컬렉션 또는 아파치 컬렉션) 사용해야합니다. 내 직감은 ArrayList를 잘 사용할 수 있습니다. 모든 생각을 환영합니다. 감사합니다.

입력 해 주셔서 감사합니다. 나는 ArrayList를 고집하고 있다고 생각한다. 현재 initialCapacity param과 함께 ArrayList 생성자를 사용하고 있으며 목록의 크기를 전달합니다. 따라서 원래 목록이 100000이면 새 ArrayList (100000)로이 새 목록을 만듭니다. 따라서 어떤 크기 조정도되지 않으므로 배열을 만들고 asList를 수행하지 않아도된다고 생각합니다. 또한, 대부분의 아파치 컬렉션 GrowthList와 같은리스트 & LazyList는 RandomAccess를 구현하지 않습니다. 이것은 확실히 shuffle을 늦출 것이다 (javadocs에 따라). FastArrayList는 RandomAccess를 구현하지만 아파치는 "이 클래스는 플랫폼이 아니므로 일부 아키텍처에서는 예기치 않은 오류가 발생할 수 있습니다"라는이 클래스에 대한 참고 사항이 있습니다.

Answer 1

ArrayList는 대부분 목록 요소 당 최소 오버 헤드가 있으므로 최상의 선택이되어야합니다. 목록의 중간에있는 항목을 자주 삭제해야하는 경우 더 나쁜 선택 일 수 있습니다.

Answer 2

ArrayList<T> 괜찮을 수도 있습니다. 그렇지만 "최상의"어쨌든 어떤 기준을 사용하고 있습니까? 그리고 어쨌든 그것이 얼마나 좋을까요? 그 기준이 무엇이든간에 복잡성과 "선량"사이의 상충 관계는 무엇입니까? Collections.shuffle javadoc의에서 인용

Answer 3

:

이 방법은 선형 시간에 실행됩니다. 지정된리스트가 RandomAccess 인터페이스를 구현하지 않고 크고,이 구현은, 지정된리스트를 섞기 전에 배열에 덤프 해, 섞은 배열을리스트에 덤프합니다. 이렇게하면 "순차 액세스"목록을 임의로 배치 한 결과로 발생하는 2 차 동작을 피할 수 있습니다.

다른 필요가 없다면 RandomAccess를 구현하는 ArrayList와 함께 갈 것입니다.

Answer 4

ArrayList가 가장 적합한 목록입니다. 어레이 백킹은 셔플에 사용 된 요소 교환에 매우 효율적입니다.

그러나 실제로 성능을 중시하는 경우 int []를 사용하거나 int []를 기반으로하는 사용자 지정 목록을 사용하여 모든 목록 및 목록 표준 구현과 마찬가지로 정수로 boxing 및 unboxing하는 것이 좋습니다.

이것은 포인터의 순서를 바꾸기 때문에 문제가되지 않지만 필요하지 않을 때 100,000 개의 개체를 만듭니다. 작성하기 전에 목록의 크기를 알고 있다고 가정하면 프리미티브 배열을 래핑하는 새 List 클래스를 쉽게 만들 수 있습니다. java.util.List로 사용되는 경우, get 메소드의 리턴 값을 입력해야합니다.

Answer 5

Integer 배열을 만든 다음 Arrays.asList으로 배치하면 일반 ArrayList보다 훨씬 적은 오버 헤드가 발생합니다.

List<Integer> makeList(int size){ 
    if (size < 0) throw new IllegalArgumentException(); 
    Integer[] arr = new Integer[size]; 
    for (int i = 0; i < arr.length; ++i) arr[i] = i; 
    List<Integer> list = Arrays.asList(arr); 
    Collection.shuffle(list); 
    return list; 
} 

당신은 (일반적으로 인정 하듯이 절대적으로이 상황에서 아무것도 ...) 공간을 하나 개의 전체 int 가치를 저장하지만, 약간 빨라집니다 접근, ArrayList "진짜"보다 적은 범위 검사를 수행 않습니다.아마도 아무 것도 알지 못할 것입니다 :)

Answer 6

Javolution은 Java에서 가장 빠른 목록 구현을 가지고 있다고 주장합니다. 하지만이 라이브러리에서 임의의 구현을 찾을 수 없으므로 직접 작성해야합니다.

Answer 7

Google의 Guava 라이브러리에는 셔플 링 될 수있는 목록을 반환하는 Ints.asList() 메소드를 비롯하여 매우 멋진 기본 처리 기능이 있습니다.

코드는 신중하게 검토되었고 Google에서 많이 사용되었지만 구아바 프로젝트는 아직 초기 단계에 있습니다. SVN에서 코드를 검색하고 com.google.common.primitive 클래스를 빌드해야합니다.

Answer 8

메모리 매핑 된 파일 기반 목록 구현을 사용할 수도 있습니다. 이러한 구현에서는 목록이 메모리에 완전히 존재하지 않지만 거대한 목록의 섹션 만 메모리에서 활성화됩니다. 힙 공간 제한 (주로 32 비트 jvm)에 도달하는 경우 일반 파일 입출력보다 빠른 메모리 맵핑 파일을 사용하여 목록에서 데이터를 완벽하게 푸시해야 할 수 있습니다. 이러한 구현 중 하나는 google code에 설명되어 있으며 link에 설명되어 있습니다.

Answer 9

ArrayList 및 LinkedList보다 매우 빠른 GlueList이라는 새로 구현 된 목록 구현이 있습니다.