Prestasie wanneer daar gekyk word vir duplikate

Question

Ek het aan 'n projek gewerk waar ek deur 'n versameling data moet herhaal en inskrywings moet verwyder waar die "primêre sleutel" gedupliseer is.Ek het probeer om 'n

List<int>

en

Dictionary<int, bool>

Met die woordeboek het ek effens beter werkverrigting gevind, alhoewel ek nooit die Booleaanse gemerk met elke inskrywing nodig het nie.My verwagting is dat dit is omdat 'n Lys vir geïndekseerde toegang toelaat en 'n Woordeboek nie.Wat ek gewonder het is, is daar 'n beter oplossing vir hierdie probleem.Ek hoef nie weer toegang tot die inskrywings te kry nie, ek hoef net op te spoor watter "primêre sleutels" ek gesien het en seker te maak dat ek net optelwerk doen op inskrywings wat 'n nuwe primêre sleutel het.Ek gebruik C# en .NET 2.0.En ek het geen beheer oor die herstel van die invoerdata om die duplikate van die bron te verwyder nie (ongelukkig!).En so jy kan 'n gevoel hê vir skaal, in die algemeen kyk ek vir duplikate ongeveer 1 000 000 keer in die toepassing, maar in subgroepe van nie meer as ongeveer 64 000 wat uniek hoef te wees nie.

Answer 1

Hulle het die HashSet klas in NET 3.5 bygevoeg. Maar ek dink dit sal wees op gelyke voet met die woordeboek. As jy minder as sê 'n 100 elemente sal 'n Lys waarskynlik beter presteer.

Answer 2

Wysig:Maak nie saak my kommentaar nie.Ek het gedink jy praat van C++.Ek het geen idee of my pos relevant is in die C# wêreld nie..

'n Hash-tabel kan 'n bietjie vinniger wees.Binêre bome (dit is wat in die woordeboek gebruik word) is geneig om relatief stadig te wees as gevolg van die manier waarop toegang tot die geheue verkry word.Dit is veral waar as jou boom baie groot word.

Maar, voordat jy jou datastruktuur verander, het jy probeer om 'n pasgemaakte poeltoewyser vir jou woordeboek te gebruik?Ek wed dat die tyd nie spandeer word om die boom self te deurkruis nie, maar in die miljoene toekennings en deallokasies wat die woordeboek vir jou sal doen.

Jy sal dalk 'n faktor 10-spoedverhoging sien wat net 'n eenvoudige swembadtoewyser in die woordeboeksjabloon inprop.Afaik boost het 'n komponent wat direk gebruik kan word.

Nog 'n opsie:As jy weet dat daar net 64 000 inskrywings in jou heelgetalle bestaan, kan jy dit na 'n lêer skryf en 'n perfekte hash-funksie daarvoor skep.Op hierdie manier kan jy net die hash-funksie gebruik om jou heelgetalle in die 0 tot 64.000-reeks te karteer en 'n bietjie-skikking te indekseer.

Seker die vinnigste manier, maar minder buigsaam.Jy moet jou perfekte hash-funksie oordoen (kan outomaties gedoen word) elke keer as jou stel heelgetalle verander.

Answer 3

Ek het nie regtig kry wat jy vra.

In die eerste plek is net die teenoorgestelde van wat jy sê. Die woordeboek het toegang ( 'n hash tafel) geïndekseer terwyl de Lys nie het.

As jy reeds die data in 'n woordeboek dan al die sleutels is uniek, daar kan wees geen duplikate.

Ek susspect jy die data wat gestoor word in 'n ander tipe data en jy dit stoor in die woordeboek. As dit die geval is die invoeging van die data sal saam met twee dictionarys.

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

Answer 4

As jy die nagaan vir uniekheid van heelgetalle, en die verskeidenheid van heelgetalle is beperk genoeg dan kan jy net gebruik om 'n skikking.

Vir 'n beter verpakking wat jy kan 'n bitmap datastruktuur implementeer (basies 'n skikking, maar elke int in die skikking verteenwoordig 32 SY in die sleutel ruimte deur gebruik te maak van 1 bietjie per sleutel). Op dié manier as jy maksimum aantal is 1000000 jy net nodig het ~ 30.5KB geheue vir die data struktuur.

Voer van 'n bitmap sou wees O (1) (per tjek) wat is moeilik om te klop.

Answer 5

Daar was 'n vraag 'n rukkie terug op verwydering van duplikate van 'n skikking . Vir die doel van die vraag prestasie was nie veel van 'n oorweging nie, maar wil jy dalk 'n blik op die antwoorde as hulle jou 'n paar idees kan gee. Ook, kan ek af basis wees hier, maar as jy probeer om duplikate van die skikking verwyder dan 'n LINQ opdrag soos Enumerable.Distinct kan jy beter prestasie as iets wat jy jouself skryf gee. As dit blyk dat daar 'n manier om te kry LINQ besig met NET 2.0 so dit mag dalk 'n roete werd ondersoek.

Answer 6

As jy gaan 'n Lys te gebruik, gebruik die 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 );
       }
   } 
} 

Jy kan ook hierdie gebruik vir enige soort waarvoor jy kan 'n IComparer definieer met behulp van 'n oorlading: BinarySearch (T item, IComparer )