문제

저는 데이터 모음을 반복하고 "기본 키"가 중복된 항목을 제거해야 하는 프로젝트를 진행하고 있습니다.나는

List<int>

그리고 

Dictionary<int, bool>

각 항목에 부울 태그를 붙일 필요가 전혀 없음에도 불구하고 사전을 사용하면 약간 더 나은 성능을 발견했습니다.내 예상으로는 목록은 색인화된 액세스를 허용하고 사전은 허용하지 않기 때문일 것입니다.제가 궁금했던 점은 이 문제에 대한 더 나은 해결책이 있느냐는 것입니다.항목에 다시 액세스할 필요는 없습니다. 내가 본 "기본 키"만 추적하고 새 기본 키가 있는 항목에 대해서만 추가 작업을 수행하면 됩니다.저는 C#과 .NET 2.0을 사용하고 있습니다.그리고 소스에서 중복 항목을 제거하기 위해 입력 데이터를 수정하는 방법을 제어할 수 없습니다(불행히도!).확장에 대한 느낌을 가질 수 있도록 전체적으로 저는 응용 프로그램에서 약 1,000,000번 정도 중복을 확인하고 있지만 고유해야 하는 약 64,000개 이하의 하위 집합에서는 중복을 확인합니다.

도움이 되었습니까?

해결책

.NET 3.5에 HashSet 클래스를 추가했습니다.그러나 나는 그것이 사전과 동등할 것이라고 생각한다.요소가 100개 미만이라면 목록이 더 나은 성능을 발휘할 것입니다.

다른 팁

편집하다:내 의견은 신경 쓰지 마세요.나는 당신이 C++에 대해 이야기하고 있다고 생각했습니다.내 게시물이 C# 세계와 관련이 있는지 전혀 모르겠습니다.

해시 테이블이 조금 더 빠를 수 있습니다.이진 트리(사전에서 사용되는 것)는 메모리에 액세스하는 방식으로 인해 상대적으로 느린 경향이 있습니다.나무가 매우 커지면 특히 그렇습니다.

그러나 데이터 구조를 변경하기 전에 사전에 사용자 정의 풀 할당자를 사용해 보셨나요?나는 트리 자체를 탐색하는 데 시간이 소요되는 것이 아니라 사전이 수행할 수백만 개의 할당 및 할당 해제에 시간이 소요될 것이라고 확신합니다.

간단한 풀 할당자를 사전 템플릿에 연결하기만 하면 속도가 10배 향상되는 것을 볼 수 있습니다.Afaik Boost에는 직접 사용할 수 있는 구성 요소가 있습니다.

또 다른 옵션:정수에 64,000개의 항목만 존재한다는 것을 알고 있다면 이를 파일에 쓰고 이에 대한 완벽한 해시 함수를 만들 수 있습니다.그렇게 하면 해시 함수를 사용하여 정수를 0에서 64.000 범위로 매핑하고 비트 배열을 인덱싱할 수 있습니다.

아마도 가장 빠른 방법이지만 유연성이 떨어집니다.정수 집합이 변경될 때마다 완벽한 해시 함수를 다시 실행해야 합니다(자동으로 수행 가능).

나는 당신이 무엇을 요구하는지 정말로 이해하지 못합니다.

첫째, 당신이 말하는 것과 정반대입니다.사전에는 색인화된 액세스(해시 테이블)가 있지만 목록에는 그렇지 않습니다.

사전에 이미 데이터가 있는 경우 모든 키는 고유하므로 중복될 수 없습니다.

나는 당신이 다른 데이터 유형에 저장된 데이터를 가지고 있고 그것을 사전에 저장하고 있다고 생각합니다.이 경우 데이터 삽입은 두 개의 사전에서 작동합니다.

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}

정수의 고유성을 확인하고 정수 범위가 충분히 제한되어 있는 경우 배열을 사용할 수 있습니다.

더 나은 패킹을 위해 비트맵 데이터 구조(기본적으로 배열이지만 배열의 각 int는 키당 1비트를 사용하여 키 공간의 32 int를 나타냄)를 구현할 수 있습니다.이렇게 하면 최대 수가 1,000,000인 경우 데이터 구조에 ~30.5KB의 메모리만 필요합니다.

비트맵의 성능은 O(1)(검사당)이며 이는 극복하기 어렵습니다.

얼마전에 질문이 있었는데 배열에서 중복 제거.질문의 목적상 성능은 크게 고려되지 않았지만 몇 가지 아이디어를 줄 수 있으므로 답변을 살펴보는 것이 좋습니다.또한 여기서는 기본이 아닐 수도 있지만 배열에서 중복 항목을 제거하려는 경우 다음과 같은 LINQ 명령을 사용하세요. 열거 가능.고유 직접 작성하는 것보다 더 나은 성능을 제공할 수 있습니다.결과적으로 얻을 수 있는 방법이 있습니다. .NET 2.0에서 작업하는 LINQ 따라서 이것은 조사해 볼 가치가 있는 경로일 수 있습니다.

목록을 사용하려면 BinarySearch를 사용하세요.

 // initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
}

오버로드를 사용하여 IComparer를 정의할 수 있는 모든 유형에 대해 이를 사용할 수도 있습니다.BinarySearch( T 항목, IComparer< T > );

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top