C#에서 빠른 삽입/삭제 및 무작위 선택을 허용하는 설정

Question

빠른 삽입/삭제 및 균일 무작위 선택을 허용하기 위해 C#에서 사용할 수있는 데이터 구조는 무엇입니까? 목록은 요소별로 느린 삭제 (매번 요소의 색인을 찾아야하기 때문에)이지만 HashSet은 요소를 임의로 선택할 수 없습니다 (목록에 복사하지 않고).

데이터 구조 지속적으로 업데이트되므로 삽입 및 삭제는 온라인 절차 여야합니다. 삽입, 삭제, 랜덤 선택을 모두 O (log n)로 만드는 방법이있는 것처럼 보입니다.

개체에 할당 된 임의의 정수 키를 가진 이진 검색 트리에서 이러한 모든 문제를 해결할 수 있지만 C# 표준 라이브러리에서 적절한 클래스를 찾을 수 없습니다. 사용자 정의 이진 검색 트리를 작성하지 않고이를 해결할 표준 방법이 있습니까?

Answer 1

이미 C# BCL에 BST가 있고 SortedDictionary<TKey, TValue>이라고합니다. 키 값 쌍이 필요하지 않고 단일 항목을 원할 경우 SortedSet<T> (SortedSet은 .NET 4.0에 있음)을 사용할 수 있습니다.

예를 들어 SortedDictionary<int, WhateverValueType>을 원합니다. 비록 당신이 "균일 무작위 선택"이라고 말할 때 당신이 정확히 무엇인지 확신 할 수는 없지만.

물론, Dictionary<TKey, TValue>은 O (1)이며 훨씬 빠릅니다. 그래서 당신이 정렬 된 키 순서가 필요하다면, 나는 그것을 사용할 것입니다.

업데이트 : 필요에 따라 효율적으로 조정할 수 있습니다. 데이터 구조에서 임의의 인접 인덱스로 점프 할 수있게하려면 얼마나 자주 삽입/삭제할 것입니까? 자주 (O (n log n)) 후에 배열을 사용하고 Sort()를 사용하거나 항상 순서대로 삽입/삭제 (O (n)) 할 수 있습니다.

또는 당신이 Dictionary<int, YourType> 포장 및 병렬 List<int>을 유지하고 이후 모든 추가/삭제 업데이트 할 수 있습니다 :

_dictionary.Add(newIndex, newValue); 
_indexes.Add(newIndex); 

을 그리고 단지 조회의 목록에서 임의의 인덱스를 액세스 할 수 있습니다. 좋은 점은이 방법에서 실제로 Add()가 ~ O (1) (목록 크기가 조정되지 않지만 일부는 피할 수있는 초기 용량을 설정할 수 있음)이지만 O (n) .

조회가 불편하거나 삭제/삽입에 시간이 많이 걸리는 경우가 있습니다. 문제는 모든 액세스 시간 컨테이너가 연속적이지 않다는 것입니다. 듀얼 List<int>/Dictionary<int, YourValue> 콤보를 사용하면 꽤 좋은 믹스를 얻을 수 있습니다.

업데이트 2 : 우리의 계속 된 토론 에서처럼 절대 성능이 요구 사항이라면 자신 만의 행운을 빕니다. 생각 해보니 재미 있었고, 내가 다른 것을 생각하면 업데이트 할 것입니다.

Answer 2

이진 검색 나무와 SortedDictionary 또는 SortedSet 같은 파생 구조, 키를 비교 에 의해 작동한다.

개체는 그 자체로는 비교할 수 없지만 개체 ID와 해시 값을 제공합니다. 따라서 올바른 데이터 구조는 HashSet입니다. 참고 : Dictionary<int,YourType>은 제거가 선형 검색 (O (n))이되고 제거한 후 임의의 문제를 해결하지 않기 때문에 적절하지 않습니다.

• 삽입 (1)
• 제거 (1)

• RandomElement은 O (N) 인 O이다 O이다. 그것은 쉽게 구현 될 수 있습니다.

  set.ElementAt(random.Next(set.Count)) 
  

  중간 목록에 복사 할 필요가 없습니다.

Answer 3

나는이 질문은 3 세 이상 실현, 그러나 다만이 페이지 건너 사람들을 위해 :

당신이 정렬 된 데이터 세트의 항목을 보관할 필요가없는 경우, 당신이 할 수있는 List<ItemType>을 사용해주세요.

삽입 및 임의 선택은 O (1)입니다. 마지막 항목을 삭제하려는 항목의 위치로 옮기고 끝에서 제거하여 O (1)에서 삭제할 수 있습니다.

코드 :

using System; // For the Random 
using System.Collections.Generic; // The List 

// List: 
List<ItemType> list = new List<ItemType>(); 

// Add x: 
ItemType x = ...; // The item to insert into the list 
list.Add(x); 

// Random selection 
Random r = ...; // Probably get this from somewhere else 
int index = r.Next(list.Count); 
ItemType y = list[index]; 

// Remove item at index 
list[index] = list[list.Count - 1]; // Copy last item to index 
list.RemoveAt(list.Count - 1); // Remove from end of list 

편집 : 물론는 List<ItemType> 당신이 알아야 인덱스에서 요소를 제거합니다. 무작위 요소를 제거하려면 위의 예제에서와 같이 임의의 인덱스를 사용할 수 있습니다. 특정 항목을 제거하려는 경우 항목을 해당 색인에 매핑하는 Dictionary<ItemType,int>을 유지할 수 있습니다. 이 색인을 추가, 제거 및 업데이트하는 작업은 모두 O (1) (상각)에서 수행 할 수 있습니다.

이로 인해 모든 작업에서 O (1) (상각 된 금액)의 복잡성이 발생합니다.