Ich suchte und konnte die Leistungszeitspezifikationen für Bitset :: count() nicht finden. Weiß jemand, was es ist (O (n) oder besser) und wo es zu finden ist?Was ist die Leistung der STL bitset :: count() Methode?
BEARBEITEN Mit STL beziehe ich mich nur auf die Standardvorlagenbibliothek.
Ich habe diese Datei (C: \ cygwin \ lib \ gcc \ i686-pc-cygwin \ 3.4.4 \ include \ C++ \ bitset) auf meinem Computer gelesen.
Siehe diese
/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }
size_t
_M_do_count() const
{
size_t __result = 0;
for (size_t __i = 0; __i < _Nw; __i++)
__result += __builtin_popcountl(_M_w[__i]);
return __result;
}
BTW, das ist, wo _Nw angegeben ist:
template<size_t _Nw>
struct _Base_bitset
So ist es O (n) in gcc Umsetzung. Wir schließen daraus, dass die Spezifikation es nicht besser als O (n) erfordert. Und niemand, der vernünftig denkt, wird es schlimmer machen. Wir können dann sicher annehmen, dass es im schlimmsten Fall O (n) ist. Vielleicht besser, aber darauf können Sie sich nie verlassen.
Das ist aber keine Spezifikation! : P –
@ tomalak-geretkal In der gcc-Implementierung ist dies O (n). Wir schließen daraus, dass die Spezifikation es nicht besser als O (n) erfordert. Und niemand wäre so dumm, es auf schlimmere Weise zu implementieren. Wir können dann sicher annehmen, dass es immer mindestens O (n) ist. Vielleicht besser, aber darauf können Sie sich nie verlassen. – Haozhun
@Gene: Während ich in diesem Fall zustimme, entspricht dies nicht der ursprünglichen Frage, was die Leistungsspezifikationen sind. Es ist jedoch ein guter Abzug. –
„Referenzimplementierung des SGI läuft in linearer Zeit in Bezug auf die Anzahl von Bytes, die Bits zu speichern, benötigt wird. Es tut dies, indem ein statisches Array von 256 ganzen Zahlen zu schaffen. Den Wert bei Ith Index gespeichert im Array ist die Anzahl der Bits, die im Wert i gesetzt sind. "
Das mag zwar stimmen, aber nur eine Warnung hier, dass cplusplus.com ist bekannt dafür, mit Fehlern durchsetzt zu sein. –
Darüber hinaus wäre das eine Beschreibung einer bestimmten Implementierung. –
@DavidThornley: In der Tat, cplusplus.com ist sehr verwirrend (wage ich zu sagen, verwirrt?) Über die Bibliothek im Allgemeinen. Es benutzt den Begriff "STL", der klar andeutet, dass es wirklich die C++ - Standardbibliothek bedeutet, aber dann sprechen die Leute in den Foren über die tatsächliche STL. –
Ich bin nicht sicher, dass Sie eine Spezifikation für das finden werden, da die STL typischerweise nicht ein gewisses Maß an Leistung erfordern. Ich habe Hinweise gesehen, dass es "schnell" ist, etwa 1 Zyklus pro Bit in der Größe des Sets. Sie können natürlich den Code Ihrer speziellen Implementierung lesen, um herauszufinden, was Sie erwarten können.
Die STL erfordert typischerweise bestimmte asymptotische Leistungsstufen (big-O). –
Ich kann nicht sicher sein, was Sie wirklich mit "STL" hier meinen, wegen eines vorherrschenden Missbrauchs des Begriffs in der C++ Gemeinschaft.
Der C++ Standard (2003) macht kein Mandat für die Durchführung von std::bitset::count() (oder in der Tat, alle Mitglieder der std::bitset soweit ich sehen kann).
Ich kann keinen Hinweis finden, der ein Mandat für die Leistung der STL bitset::count() entweder vorschlägt.
Ich denke, dass jede vernünftige Umsetzung dieses in Konstante (oder im schlimmsten Fall linear) Zeit zur Verfügung stellen wird, though. Dies ist jedoch nur ein Gefühl. Überprüfen Sie Ihre, um herauszufinden, was Sie tatsächlich bekommen.
Können Sie mitteilen, auf welche anderen Dinge sich STL im Zusammenhang mit C++ bezieht? – yasouser
Gleicher Kommentar wie ich Ihnen [hier] (http://stackoverflow.com/questions/2297164/stl-deque-accessing-by-index-is-o1/4694218#4694218) gegeben habe. Es gibt eine Zeit für Pedanterie, das ist es nicht. Beantworten Sie die Frage, ob Sie die Verwendung von "STL" durch OP erklären möchten, aber machen Sie es nicht zu Ihrer Antwort und stellen Sie sich vor, dass Sie irgendwie nicht verstehen können, was er meinte, es ist arrogant und protzig. * Erklären Sie dem OP Dinge, sagen Sie nicht einfach: "Ich kann das unmöglich bekommen, es ist nicht genau definiert!" – GManNickG
@GMan Ich hätte daran gedacht, darauf hinzuweisen, dass seine Frage vage war und dann eine Antwort für BEIDES der beiden Dinge zu geben, nach denen er hätte fragen können. Ich sehe nicht, dass es "arrogant" ist, zu erklären, dass ich nichts tun kann; lese ein Wörterbuch. Und es ist nicht so, als ob meine ganze Antwort "Ich weiß nicht was du meinst, versuche es noch einmal" war. –
Was Tomalak erwähnt (aber nicht * erklären * konnte, weil er anscheinend unsicher ist und sein Wissen gegenüber anderen behaupten muss) ist, dass STL (Standard Template Library) ein mehrdeutiger Begriff ist. Einige von uns in der C++ - Community haben dies im [info-wiki für das Tag] (http://stackoverflow.com/tags/stl/info) erweitert, was den Kommentar der Quelle Tomalak verdeutlichen soll. Kurz gesagt, Sie sollten einfach "Standard-Bibliothek" oder "StdLib" sagen, aber wir werden wissen, was Sie meinen, wenn Sie STL sagen. – GManNickG
@GMan: Keine Notwendigkeit für persönliche Angriffe. Sie sind hier auf StackOverflow nicht willkommen. Bitte passen Sie Ihren Ton in Zukunft an. –