C# Zeitkomplexität von Array [T] .Contains (T Artikeln) vs HashSet <T> .Contains (T Artikel)

Question

HashSet(T).Contains(T) (geerbt von ICollection<T>.Contains(T)) hat eine Zeitkomplexität von O (1).
Also, ich frage mich, was die Komplexität eines Klassen-Member-Array mit Ganzzahlen wäre, wie ich O (1) erreichen will und nicht die existence checks von HashSet(T).Add(T) benötigen.

Da built-in types sind nicht in der .NET-Referenzquelle gezeigt, ich keine Chance haben der Suche nach der Array Implementierung von IList(T).Contains(T) gefunden.

Alle (weiter) lesen Material oder Referenz würde sehr geschätzt werden.

Answer 1

Sie können den Quellcode von Array mit jedem Reflektor sehen (vielleicht auch online, nicht überprüft).IList.Contains ist einfach:

Array.IndexOf(this,value) >= this.GetLowerBound(0); 

Und Array.IndexOfArray.IndexOf<T> nennt, die nach einer Reihe von Konsistenzprüfungen, zu

umleitet

EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count) 

Und dass man endlich tut:

int num = startIndex + count; 
for (int index = startIndex; index < num; ++index) 
{ 
    if (this.Equals(array[index], value)) 
     return index; 
} 
return -1; 

Also nur Schleifen über Array mit durchschnittlicher Komplexität O(N). Natürlich war das von Anfang an klar, aber nur um mehr Beweise zu liefern.

Answer 2

Sie können tatsächlich die Quelle für List<T> sehen, aber Sie müssen es online nachschlagen. Hier ist one source.

Jede reine Liste/Array bool Contains(T item) Überprüfung ist O (N) Komplexität, weil jedes Element überprüft werden muss. .NET ist keine Ausnahme. (Wenn Sie eine Datenstruktur entworfen haben, die sich als Liste manifestiert, aber auch eine Bloom-Filter-Hilfsdatenstruktur enthält, wäre das eine andere Geschichte.)

Answer 3

Array-Quellcode ist in reference source verfügbar und kann mit ILSpy de-kompiliert werden.

In Referenzquelle, finden Sie in Zeile 2753 dann 2809:

// ----------------------------------------------------------- 
// ------- Implement ICollection<T> interface methods -------- 
// ----------------------------------------------------------- 

... 

[SecuritySafeCritical] 
bool Contains<T>(T value) { 
    //! Warning: "this" is an array, not an SZArrayHelper. See comments above 
    //! or you may introduce a security hole! 
    T[] _this = JitHelpers.UnsafeCast<T[]>(this); 
    return Array.IndexOf(_this, value) != -1; 
} 

Und IndexOf endet auf dieser IndexOf oben, die eine O (n) Algorithmus ist.

internal virtual int IndexOf(T[] array, T value, int startIndex, int count) 
{ 
    int endIndex = startIndex + count; 
    for (int i = startIndex; i < endIndex; i++) { 
     if (Equals(array[i], value)) return i; 
    } 
    return -1; 
} 

Diese Methoden sind auf einer speziellen Klasse SZArrayHelper in derselben Quelldatei, und wie in Zeile 2721 erläutert, ist dies die Umsetzung Ihrer für suchen.

// This class is needed to allow an SZ array of type T[] to expose IList<T>, 
// IList<T.BaseType>, etc., etc. all the way up to IList<Object>. When the following call is 
// made: 
// 
// ((IList<T>) (new U[n])).SomeIListMethod() 
// 
// the interface stub dispatcher treats this as a special case, loads up SZArrayHelper, 
// finds the corresponding generic method (matched simply by method name), instantiates 
// it for type <T> and executes it. 

Über O (1) Komplexität zu erreichen, können Sie es zu einem HashSet umwandeln sollte:

var lookupHashSet = new HashSet<T>(yourArray); 
... 
var hasValue = lookupHashSet.Contains(testValue); 

Natürlich ist diese Umwandlung ist ein O (n) -Operation. Wenn Sie nicht viele Nachschlagewerke zu tun haben, ist es strittig.

Hinweis from documentation auf diesem Konstruktor:

Wenn Sammlung Duplikate enthält, wird die Menge eines jeden einzelnen Element enthalten. Es wird keine Ausnahme ausgelöst. Daher ist die Größe der resultierenden Menge nicht identisch mit der Größe der Sammlung.