.NET 컬렉션 클래스

Question

파트 목록 등의 관련 데이터 그룹은 배열 (Array of Parts)을 사용하거나 Collection을 사용하여 처리 할 수 ​​있습니다. 배열을 사용하는 경우 컬렉션과 비교할 때 삽입, 삭제 및 기타 작업은 성능에 영향을 미친다는 것을 알고 있습니다. 배열이 내부적으로 컬렉션에 사용되지 않는다는 뜻입니까? 그렇다면 List, Collection 등의 컬렉션에 사용되는 데이터 구조는 무엇입니까?

내부적으로 컬렉션을 처리하는 방법은 무엇입니까?

Answer 1

간단한 컬렉션을 구현하는 두 가지 기본 방법이 있습니다

• 연속 배열
• 연결리스트

연속 배열은 당신이 언급 한 작업에 대한 성능 단점이 때문에의 메모리 공간 컬렉션은 컬렉션의 내용에 따라 사전 할당되거나 할당됩니다. 따라서 삭제 또는 삽입은 전체 배열을 연속적으로 적절한 순서로 유지하기 위해 많은 배열 요소를 이동해야합니다.

컬렉션의 항목을 연속적으로 메모리에 저장할 필요가 없으므로 연결된 목록에서 이러한 문제가 제거됩니다. 대신 각 요소는 하나 이상의 다른 요소에 대한 참조를 포함합니다. 따라서 삽입이 이루어지면 문제의 항목은 메모리의 어느 위치에서나 생성되고 컬렉션에 이미 들어있는 요소 중 하나 또는 두 개의 참조 만 수정해야합니다. 예를 들어

:

LinkedList<object> c = new LinkedList<object>(); // a linked list 
object[] a = new object[] { }; // a contiguous array 

물론 이것은 단순화된다. LinkedList<>의 내부 구조는 의심 할 여지없이 단순한 단일 또는 이중 연결 목록보다 복잡하지만 기본 구조입니다.

Answer 2

List<T>은 내부 배열을 사용합니다. 내부 배열의 전체 내용을 한 방향으로 이동해야하기 때문에 목록 시작 부분 근처에서 항목을 제거/삽입하는 것은 목록 끝 부분에서 동일한 작업을 수행하는 것보다 비용이 많이 듭니다. 또한 내부 목록이 가득 차면 항목을 추가하려고하면 더 큰 새 배열이 만들어지고 내용이 복사되고 이전 배열은 삭제됩니다.

클래스는 매개 변수없는 생성자와 함께 사용되는 경우 List<T>을 내부적으로 사용합니다. 따라서 랩핑으로 인한 오버 헤드를 제외하고는 성능 측면에서 동일합니다. (본질적으로 다른 레벨의 간접 참조는 대부분의 시나리오에서 무시할 수 있습니다.)

LinkedList<T>은 링크 된 목록입니다. 이것은 삽입/제거 속도를 위해 반복 속도를 희생합니다. 반복은 포인터에서 포인터로의 포인터를 무한히 횡단하는 것을 의미하므로 전체적으로 더 많은 작업이 필요합니다. 포인터 탐색과는 별도로 두 노드를 서로 가까이 배치하지 않아도 CPU RAM 캐시의 효율성을 떨어 뜨릴 수 있습니다.

그러나 노드를 삽입하거나 제거하는 데 필요한 시간은 목록의 상태에 관계없이 동일한 수의 작업이 필요하기 때문에 일정합니다. (제거 할 항목을 실제로 찾거나 삽입 지점을 찾기 위해 목록을 탐색하기 위해 수행해야하는 작업은 고려하지 않습니다.)

무언가가있는 경우 컬렉션에 대한 주된 관심사가 테스트중인 경우 컬렉션, HashSet<T> 대신 사용할 수 있습니다.세트에 항목을 추가하는 것은 목록과 링크 된 목록에 삽입하는 것 사이의 비교적 빠른 것입니다. 항목 제거는 상대적으로 빠릅니다. 그러나 실제로는 조회 시간에 있습니다. HashSet<T>에 항목이 포함되어 있으면 전체 목록을 반복 할 필요가 없습니다. 평균적으로 모든 목록 또는 연결된 목록 구조보다 빠르게 수행됩니다.

그러나 HashSet<T>에는 동일한 항목이 포함될 수 없습니다. 귀하의 요구 사항 중 일부로 동일하다고 여겨지는 항목 (Object.Equals(Object) 오버로드 또는 IEquatable<T> 구현)이 컬렉션에 독립적으로 공존하는 경우 HashSet<T>을 사용할 수 없습니다. 또한 HashSet<T>은 게재 신청서를 보장하지 않으므로 어떤 종류의 주문 유지가 중요한 경우 HashSet<T>을 사용할 수 없습니다.

Answer 3

일부 컬렉션 클래스는 내부적으로나 링크 된 목록이나 유사한 것을 사용할 수 있다고 생각합니다. 배열 대신 System.Collections 네임 스페이스의 컬렉션을 사용하면 업데이트 작업을 수행하는 데 코드 작성 시간을 추가로 쓸 필요가 없습니다.

배열은 항상 더 가볍고 아주 좋은 검색 알고리즘을 알고 있다면 더 효율적으로 사용할 수도 있지만 대부분 시스템의 클래스를 사용하여 바퀴를 다시 만들지 않아도됩니다. . 수집. 이 클래스는 프로그래머가 이미 작성되고 조정 된 코드를 수백 번 반복 작성하는 것을 방지하기 위해 만들어 졌으므로 배열을 직접 조작하여 성능을 크게 향상시킬 수는 없습니다.

추가, 제거 또는 편집이 많이 필요하지 않은 정적 컬렉션이 필요한 경우 콜렉션이 수행하는 추가 메모리가 필요하지 않으므로 배열을 사용하는 것이 좋습니다.