SortedHashTable in C#

Question

내가하려는 것은 NP 완료 문제에 대한 경험적 접근법을 구현하는 것입니다. 객체의 목록 (일치)에 각각 두 가지 점수가 있습니다. 목록의 첫 번째 요소를 점수 desc로 정렬 한 다음 목록에서 제거합니다. 그런 다음 첫 번째 요소에 바인딩 된 모든 요소가 제거됩니다. 나는 더 이상 요소가 없을 때까지 목록을 반복합니다.

는 그래서 기본적으로 다음과 같은 특성 ahve해야 효율적으로이 문제를 해결할 수있는 데이터 구조가 필요
1. 일반 항상
3. 빠른 키 액세스를 가지고 분류되어
2

지금은 SortedSet<T>이 가장 적합하게 보입니다.

질문은 : 내 경우에는 가장 적합한 선택입니까? 내가 필요로 무엇

List result = new List();
while (sortedItems.Any())
{
var first = sortedItems.First();
result.Add(first);
sortedItems.Remove(first);
foreach (var dependentFirst in first.DependentElements)
{
sortedItems.Remove(dependentFirst);
}
}

은 정렬 된 해시 테이블 같은 것입니다. 힙 및 세트 - - 정렬 된 항목을 유지하기 위해 힙, 삭제 된 항목을 유지하기 위해 설정 메신저 실수하지 않으면

Answer 1

, 당신은 당신이 두 개의 데이터 구조를 사용한다고 생각이

  var dictionary = new Dictionary<string, int>(); 
      dictionary.Add("car", 2); 
      dictionary.Add("apple", 1); 
      dictionary.Add("zebra", 0); 
      dictionary.Add("mouse", 5); 
      dictionary.Add("year", 3); 
      dictionary = dictionary.OrderBy(o => o.Key).ToDictionary(o => o.Key, o => o.Value); 

Answer 2

같은 것을 원한다. 힙을 항목으로 채운 다음 맨 위 항목을 제거하고 해당 항목과 모든 종속 항목을 세트에 추가하십시오. 두 번째 것을 제거하십시오 - 이미 세트에있는 경우이를 무시하고 세 번째 세트로 이동하십시오. 그렇지 않으면 세트와 그 부속 요소를 세트에 추가하십시오.

항목을 세트에 추가 할 때마다 항목을 사용하여 계획하고있는 모든 작업을 수행하십시오.

여기의 복잡성은 O (NlogN)입니다. 어쨌든 항목 목록을 정렬해야하므로 이보다 더 좋아지지는 않을 것입니다. 더 나은 성능을 얻으려면 각 항목에 '제거됨'부울을 추가하고 세트를 사용하여 제거 된 항목을 추적하는 대신 true로 설정하십시오. 이것이 당신에게 해당되는지 나는 모른다.

Answer 3

나는 당신이 단지 목록을 삭제하고 싶지는 않지만 각 항목이 제거 될 때 어떤 것을하고 싶다고 가정합니다.

var toDelete = new HashSet<T>(); 
foreach (var item in sortedItems) 
{ 
    if (!toDelete.Contains(item)) 
    { 
     toDelete.Add(item); 
     // do something with item here 
    } 
    foreach (var dependentFirst in item.DependentElements) 
    { 
     if (!toDelete.Contains(item)) 
     { 
      toDelete.Add(dependentFirst); 
      // do something with item here 
     } 
    } 
} 
sortedItems.RemoveAll(i => toDelete.Contains(i));