어떤 소트 콜렉션 구현이 Java에서 메모리 공간이 가장 적은가?

Question

나는 읽기/쓰기 성능에 대해 과감히 신경 쓰지 않는다. (가능한 한 빨리 분명히 항상 좋다) 오히려 가능한 한 메모리 효율이 높은 정렬 된 컬렉션 구현을 찾고있다. 어떤 제안?

Answer 1

그럼 정확히 원하는 크기의 배열로 저장하고 정렬하십시오. O (n log n)의 1 회 작업. 그 이후의 각 검색은 O (log n)입니다. 정렬 된 배열을 Arrays.asList()를 사용하여 List에 쉽게 전달할 수 있습니다.

Answer 2

Fibonacci Heap으로 저장하지 않으시겠습니까? 그들은 빠르고, 작고, 효과적입니다. 너무 복잡하면 다른 여러 유형의 힙 구현을 살펴볼 수 있습니다. 많은 힙을 배열로 저장할 수 있습니다. 즉, 컬렉션에 개체가있는만큼의 저장 공간 만 필요합니다.

Answer 3

가장 작은 정렬 컬렉션은 ArrayList입니다. 기본 배열보다 훨씬 크지 않습니다. sort()을 호출하면 내용이 정렬됩니다.

Answer 4

TreeSet은 적절한 메모리 보존과 시간 성능을 제공합니다. O (log n) 삽입/찾아보기.

Answer 5

google-collections에서 ImmutableSortedSet은 사용자 요구 사항 ("정렬 된 컬렉션 구현")을 충족시키는 것으로 알고 있지만 수정할 수없는 가장 작은 것입니다.