.NET 데이터 구조 : ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary — 속도, 메모리 및 각각 사용시기? 실제로는 실제로

.NET에는 많은 복잡한 데이터 구조가 있습니다. 불행히도, 그들 중 일부는 매우 유사하며, 언제 사용하고 언제 사용해야하는지 잘 모르겠습니다. 내 C # 및 Visual Basic 책의 대부분은 어느 정도 그들에 대해 이야기하지만 실제로는 실제로 자세히 다루지 않습니다.

Array, ArrayList, List, Hashtable, Dictionary, SortedList 및 SortedDictionary의 차이점은 무엇입니까?

열거 할 수있는 것은 무엇입니까 (IList- ‘foreach’루프를 수행 할 수 있습니까)? 어느 것이 키 / 값 쌍 (IDict)을 사용합니까?

메모리 풋 프린트는 어떻습니까? 삽입 속도? 검색 속도?

언급 할만한 다른 데이터 구조가 있습니까?

메모리 사용 및 속도 (Big-O 표기법)에 대한 자세한 내용을 계속 찾고 있습니다.

답변

내 머리 꼭대기에서 :

  • Array*-구식 메모리 배열을 나타냅니다 type[]. 일반 배열 의 별칭과 같습니다 . 열거 할 수 있습니다. 자동으로 성장할 수 없습니다. 나는 매우 빠른 삽입 및 검색 속도를 가정합니다.

  • ArrayList-자동으로 성장하는 어레이. 더 많은 오버 헤드를 추가합니다. 열거 할 수 있습니다. 아마 일반 배열보다 느리지 만 여전히 꽤 빠릅니다. 이들은 .NET에서 많이 사용됩니다.

  • List-내 즐겨 찾기 중 하나-제네릭과 함께 사용할 수 있으므로 예를 들어 강력한 형식의 배열을 사용할 수 있습니다 List<string>. 그 외에는ArrayList

  • Hashtable-평범한 오래된 해시 테이블. O (1)에서 O (n)까지의 최악의 경우입니다. value 및 keys 속성을 열거하고 키 / val 쌍을 수행 할 수 있습니다.

  • Dictionary -위와 동일하게 제네릭을 통해 강력하게 입력됩니다. Dictionary<string, string>

  • SortedList-정렬 된 일반 목록. 물건을 넣을 위치를 알아야하기 때문에 삽입 속도가 느려졌습니다. 열거 할 수 있습니다. 아마도 검색 할 필요가 없기 때문에 검색시 동일하지만 삭제는 평범한 이전 목록보다 느립니다.

내가 사용하는 경향 List과 Dictionary모든 시간을 – 당신이 그들을 강하게 제네릭 타입 사용하기 시작하면, 그 정말 열심히 표준 제네릭이 아닌 사람에게 돌아갑니다.

다른 데이터 구조도 많이 KeyValuePair있습니다. 흥미로운 것들을 수행하는 데 사용할 SortedDictionary수 있고 유용한 것도 있습니다.

답변

가능하면 제네릭을 사용하십시오. 여기에는 다음이 포함됩니다.

  • ArrayList 대신 List
  • HashTable 대신 사전

답변

먼저 .NET의 모든 컬렉션은 IEnumerable을 구현합니다.

둘째, 제네릭이 프레임 워크 버전 2.0에 추가 되었기 때문에 많은 컬렉션이 중복되었습니다.

따라서 일반 컬렉션은 기능을 추가 할 가능성이 있지만 대부분 다음과 같습니다.

  • List는 일반적인 ArrayList 구현입니다.
  • 사전은 Hashtable의 일반적인 구현입니다

배열은 고정 된 크기의 모음으로, 주어진 색인에 저장된 값을 변경할 수 있습니다.

SortedDictionary는 키를 기준으로 정렬 된 IDictionary입니다. SortedList는 필수 IComparer를 기준으로 정렬 된 IDictionary입니다.

따라서 IDictionary 구현 (KeyValuePair를 지원하는 구현)은 다음과 같습니다. * Hashtable * Dictionary * SortedList * SortedDictionary

.NET 3.5에 추가 된 또 다른 컬렉션은 해시 셋입니다. 세트 조작을 지원하는 콜렉션입니다.

또한 LinkedList는 표준 연결 목록 구현입니다 (목록은 더 빠른 검색을위한 배열 목록입니다).

답변

다음은 몇 가지 일반적인 팁입니다.

  • foreach구현하는 유형에 사용할 수 있습니다 IEnumerable. IList기본적으로 IEnumberablewith Count및 Item(0부터 시작하는 인덱스를 사용하여 항목에 액세스) 속성입니다. IDictionary반면에 해시 가능 인덱스로 항목에 액세스 할 수 있습니다.

  • Array, ArrayList그리고 List모든 구현 IList.
    Dictionary, SortedDictionary및 Hashtable구현 IDictionary.

  • .NET 2.0 이상을 사용하는 경우 언급 된 유형의 일반 대응 물을 사용하는 것이 좋습니다.

  • 이러한 유형에 대한 다양한 작업의 시간 및 공간 복잡성에 대해서는 해당 설명서를 참조하십시오.

  • .NET 데이터 구조는 System.Collections네임 스페이스에 있습니다. 추가 데이터 구조를 제공하는 PowerCollection 과 같은 형식 라이브러리가 있습니다 .

  • 데이터 구조를 완전히 이해하려면 CLRS 와 같은 리소스를 참조하십시오 .

답변

.NET 데이터 구조 :

ArrayList와 List가 실제로 다른 이유에 대한 대화

배열

한 사용자가 말했듯이 배열은 “구식”컬렉션입니다 (예, 배열은의 일부는 아니지만 컬렉션으로 간주 됨 System.Collections). 그러나 다른 컬렉션, 즉 제목에 나열한 컬렉션 (여기서는 ArrayList 및 List (Of T))과 비교하여 배열에 대해 “오래된 학교”란 무엇입니까? 배열을보고 기본 사항부터 시작하겠습니다.

우선 Microsoft .NET의 어레이 는 “논리적으로 관련된 여러 항목을 단일 컬렉션으로 취급 할 수있는 메커니즘”입니다 (링크 된 기사 참조). 그게 무슨 뜻이야? 배열은 개별 주소 (요소)를 순차적으로 메모리에 시작 주소가있는 순서대로 저장합니다. 배열을 사용하면 해당 주소에서 시작하여 순차적으로 저장된 요소에 쉽게 액세스 할 수 있습니다.

그 외에도 101 개의 공통 개념을 프로그래밍하는 것과 달리 배열은 실제로 매우 복잡 할 수 있습니다.

배열은 단일 차원, 다차원 또는 들쭉날쭉 한 것일 수 있습니다 (들쭉날쭉 한 배열은 읽을 가치가 있습니다). 배열 자체가 동적 아니다 : 초기화되면, 어레이 N의 크기를 보유하기 위해서 충분한 공간 N 객체들의 수. 배열의 요소 수는 늘어나거나 줄어들 수 없습니다. Dim _array As Int32() = New Int32(100)배열이 100 개의 Int32 기본 유형 객체를 포함 할 수 있도록 메모리 블록에 충분한 공간을 예약합니다 (이 경우 배열은 0을 포함하도록 초기화 됨). 이 블록의 주소는로 반환됩니다 _array.

이 기사에 따르면 CLS ( 공용 언어 사양 )에서는 모든 배열이 0부터 시작해야합니다. .NET의 배열은 0이 아닌 배열을 지원합니다. 그러나 이것은 덜 일반적입니다. 제로 기반 어레이의 “공통성”의 결과로 Microsoft는 성능을 최적화하는 데 많은 시간을 보냈습니다 . 따라서 단일 차원의 0부터 시작하는 (SZ) 배열은 “특별한”배열이며 실제로는 다차원과 달리 배열의 최상의 구현입니다. SZ에는 배열을 조작하기위한 특정 중개 언어 명령어가 있기 때문입니다.

배열은 항상 참조에 의해 전달됩니다 (메모리 주소로)-중요한 배열 퍼즐 조각입니다. 경계 검사를 수행하는 동안 (오류가 발생 함) 배열에서 경계 검사를 비활성화 할 수도 있습니다.

다시 말하지만 배열에 대한 가장 큰 장애는 크기를 조정할 수 없다는 것입니다. 그것들은 “고정 된”용량을 가지고 있습니다. 히스토리에 ArrayList 및 List (Of T) 소개 :

ArrayList-일반이 아닌 목록

ArrayList를은 (함께 List(Of T)– 몇 가지 중요한 차이가 있지만, 여기에, 나중에 설명) – 아마도 (넓은 의미에서) 컬렉션의 다음뿐만 아니라 최고의 생각이다. ArrayList는 IList ( ‘ICollection’의 자손) 인터페이스 에서 상속합니다 . ArrayLists는 자체이다 부피가 더 필요 – 오버 헤드 – 목록보다.

IList구현시 ArrayList를 고정 크기 목록 (예 : Arrays)으로 처리 할 수 ​​있습니다. 그러나 ArrayLists에 의해 추가 된 추가 기능 외에,이 경우 ArrayLists (Array보다) 크기가 고정되어있는 ArrayLists를 사용하면 실질적으로 이점이 없습니다.

내 독서에서 ArrayLists는 들쭉날쭉해질 수 없습니다. “다차원 배열을 요소로 사용하는 것은 지원되지 않습니다”. 다시, ArrayLists의 관에 또 다른 손톱. ArrayLists는 또한 “유형”이 아닙니다. 즉, 모든 것 아래에서 ArrayList는 단순히 객체의 동적 배열입니다 Object[]. 이것은 ArrayLists를 구현할 때 많은 복싱 (암시 적) 및 언 박싱 (명시 적)이 필요하며 다시 오버 헤드에 추가됩니다.

불확실한 생각 : 나는 ArrayLists가 Arrays에서 List-type Collections로 이동하려는 시도에 대한 나쁜 자식 개념의 자식이라는 것을 교수들 중 한 사람으로부터 읽거나 들었다는 것을 기억합니다. 컬렉션과 관련하여 추가 개발이 완료되었으므로 더 이상 최선의 선택이 아닙니다.

List (Of T) : ArrayList가 된 (및 희망)

메모리 사용량의 차이는 (INT32의) 목록이 56 %를 소비 덜 같은 기본 유형을 포함하는 ArrayList에 비해 메모리 곳으로 크게 충분하다 (8메가바이트 위의 신사의 연결 시연에서 19메가바이트 대 : 다시 연결 여기에 ) – 비록 이는 64 비트 시스템에 의해 복합 된 결과입니다. 이 차이점은 실제로 두 가지를 보여줍니다. 첫 번째 (1), 박스형 Int32 유형 “object”(ArrayList)는 순수한 Int32 기본 유형 (List)보다 훨씬 큽니다. 둘째, 64 비트 시스템의 내부 작업으로 인해 차이가 기하 급수적으로 증가합니다.

차이점은 무엇이며 List (Of T)는 무엇입니까? MSDN 은 List(Of T)“… 인덱스로 액세스 할 수있는 강력한 형식의 개체 목록”으로 정의합니다 . 여기서 “강력한 형식의”비트가 중요합니다. List (Of T)는 형식을 ‘인식’하고 개체를 해당 형식으로 저장합니다. 따라서 는 형식이 아닌 형식 Int32으로 저장됩니다 . 이것은 권투와 박스 해제로 인한 문제를 제거합니다.Int32Object

MSDN은이 차이가 기본 형식을 저장하고 참조 형식을 저장할 때만 발생한다고 지정합니다. 너무 큰 차이는 500 개 이상의 요소에서 실제로 발생합니다. 더 흥미로운 점은 MSDN 설명서에 “ArrayList 클래스를 사용하는 대신 List (Of T) 클래스의 형식 별 구현을 사용하는 것이 유리하다는 것입니다.”

본질적으로 List (Of T)는 ArrayList이지만 더 좋습니다. ArrayList의 “일반적인”항목입니다. ArrayList와 마찬가지로 정렬 될 때까지 정렬되지 않을 수도 있습니다 (그림 참조). List (Of T)에도 일부 기능이 추가되었습니다.

답변

나는 질문에 동조한다-나는 선택이 어리둥절하다는 것을 발견했다. CLR 수준에서 동일한 작업을 수행하십시오). 여기에서 내가 수행 한 벤치마킹 결과를 볼 수 있습니다 (어떤 상황에서 어떤 데이터 유형을 사용하는 것이 가장 좋은지에 대한 설명도 있습니다).

답변

그들은 지능적으로 잘 설명되어 있습니다. System.Collections를 입력하십시오 . 또는 System.Collections.Generics (선호) 및 사용 가능한 항목에 대한 간단한 설명과 목록이 제공됩니다.