ich einen Cache-Auswurf Methode zu schreiben, die im Wesentlichen wie folgt aussieht:Ist <Collection> .Count Teuer zu verwenden?
while (myHashSet.Count > MAX_ALLOWED_CACHE_MEMBERS)
{
EjectOldestItem(myHashSet);
}
Meine Frage ist, wie Count bestimmt: ist es nur ein private oder protected int, oder sie durch Zählen der Elemente jeweils berechnet Zeit es heißt?
Von http://msdn.microsoft.com/en-us/library/ms132433.aspx:
den Wert dieser Eigenschaft Abrufen ist ein O (1) -Operation.
Dies garantiert, dass der Zugriff auf die Count nicht über die gesamte Sammlung iterieren wird.
Edit: wie viele andere Plakate vorgeschlagen, IEnumerable<...>.Count() ist jedoch nicht garantiert sein O (1). Verwenden Sie vorsichtig!
IEnumerable<...>.Count() ist eine in definierte Erweiterungsmethode. Die aktuelle Implementierung führt einen expliziten Test durch, wenn die gezählte IEnumerable<T> tatsächlich eine Instanz von ist und wenn möglich ICollection<T>.Count verwendet. Sonst durchläuft es die IEnumerable<T> (mögliche faule Auswertung zu erweitern) und zählt Elemente einzeln.
Ich habe jedoch in der Dokumentation nicht gefunden, ob es garantiert ist, dass IEnumerable<...>.Count() O (1) verwendet, wenn möglich, habe ich nur die Implementierung in .NET 3.5 mit Reflector überprüft.
Notwendige späte Zugabe: viele beliebte Container nicht von Collection<T> abgeleitet, aber dennoch ihre Count Eigenschaft ist O (1) (das heißt, nicht über die gesamte Auflistung durchlaufen). Beispiele sind HashSet<T>.Count (das ist wahrscheinlich das, was das OP fragen wollte), Dictionary<K, V>.Count, LinkedList<T>.Count, List<T>.Count, Queue<T>.Count, Stack<T>.Count und so weiter.
Alle diese Sammlungen implementieren ICollection<T> oder einfach nur ICollection, so dass ihre Count eine Implementierung von ICollection<T>.Count (oder ICollection.Count). Es ist nicht erforderlich, dass eine Implementierung von ICollection<T>.Count eine O (1) -Operation ist, aber die oben erwähnten tun dies gemäß der Dokumentation.
(Hinweis beiseite: einige Behälter, zum Beispiel, Queue<T>, implementieren nicht-generic ICollection aber nicht ICollection<T>, so dass sie "erben" die Count Eigenschaft nur von von ICollection.)
Sollte ich meinen eigenen Ratschlag genommen haben und die Sammlung
@Bob: Gern geschehen. – Vlad
Bitte beachten Sie, dass es eine Verlängerungsmethode Count() gibt, die auf IEnumerables funktioniert. Das ist * nicht * garantiert O (1). –
Im Falle eines HashSet es ist nur ein internes int Feld und sogar SortedSet (ein binärer Baum basierte Set für .net 4) hat seine Zählung in einem internen Bereich.
Es ist ein interner Wert und wird nicht berechnet. Die documentation besagt, dass das Abrufen des Werts eine O (1) -Operation ist.
Es ist eine interne int, die jedes Mal inkrementiert wird, wenn ein neues Element zur Sammlung hinzugefügt wird.
Ihre Frage spezifiziert keine spezifische Collection-Klasse so ...
Es ist auf der Collection-Klasse ab. ArrayList hat eine interne Variable, die die Zählung verfolgt, ebenso wie List. Es ist jedoch implementierungsspezifisch und könnte je nach Art der Sammlung theoretisch bei jedem Aufruf neu berechnet werden.
Ja. Bei "Sammlung" ist die Klasse O (1) wie der Dokumentstatus. Wenn Sie über ICollection die Schnittstelle sprechen, hängt es wirklich von der Implementierung ab. –
@John - Es ist schwer zu sagen, wie er den Titel formuliert hat. War
Wie andere bemerkt haben, wird Count beibehalten, wenn die Sammlung geändert wird. Dies ist fast immer der Fall bei jeder Sammlungsart im Framework. Dies unterscheidet sich erheblich von der Verwendung der Count-Erweiterungsmethode für IEnumerable, die die Auflistung jedes Mal aufzählt. Die Count-Eigenschaft ist bei den neueren Auflistungsklassen nicht virtuell, was bedeutet, dass der Jitter den Aufruf des Access-Zählers inline einschließen kann, was praktisch dasselbe bedeutet wie das Zugreifen auf ein Feld. Mit anderen Worten, sehr schnell.
+1 für die Angabe, dass die Verlängerungsmethode IEnumerable <>. Count() unterschiedlich ist. Natürlich prüft die Erweiterungsmethode, ob das Enumerable eine Auflistung mit einer O (1) -Zählung ist, bevor es tatsächlich nummeriert wird, aber es ist definitiv etwas zu beachten. – Tanzelax
Nach Reflector wird implementiert, wie
public int Count{ get; }
so wird es durch den abgeleiteten Typ definiert
Nur eine kurze Nachricht. Beachten Sie, dass es zwei Möglichkeiten gibt, eine Auflistung in .NET 3.5 zu zählen, wenn System.Linq verwendet wird. Bei einer normalen Sammlung sollte die Verwendung der Eigenschaft Count aus den bereits in anderen Antworten beschriebenen Gründen die erste Wahl sein.
Eine alternative Methode ist über die Erweiterungsmethode LINQ .Count() ebenfalls verfügbar. Das Interessante an .Count() ist, dass es bei jedem aufzählbaren Element aufgerufen werden kann, unabhängig davon, ob die zugrunde liegende Klasse ICollection implementiert oder nicht, oder ob es eine Count-Eigenschaft besitzt. Wenn Sie jedoch jemals .Count() aufrufen, beachten Sie, dass es sich über die Sammlung iterieren wird, um eine Zählung dynamisch zu generieren. Dies führt im Allgemeinen zu O (n) -Komplexität.
Der einzige Grund, warum ich dies bemerken wollte, ist, dass es mit IntelliSense oft einfach ist, versehentlich die Count() - Erweiterung anstelle der Count-Eigenschaft zu verwenden.
Gute Frage. Ich würde eine interne int hoffen, da es in den meisten Fällen ziemlich einfach wäre, aber ich weiß es nicht. – Tarka