Ho cercato in giro e non sono riuscito a trovare le specifiche del tempo di esecuzione per bitset :: count(). Qualcuno sa cosa sia (O (n) o migliore) e dove trovarlo?Qual è la prestazione del metodo STL bitset :: count()?
MODIFICA Con STL mi riferisco solo alla libreria di modelli standard.
Ho letto questo file (C: \ cygwin \ lib \ gcc \ i686-pc-cygwin \ 3.4.4 \ include \ C++ \ bitset) sul mio computer.
vedere questi
/// 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, questo è dove si specifica _Nw:
template<size_t _Nw>
struct _Base_bitset
Così è O (n) nell'attuazione gcc. Concludiamo che le specifiche non lo richiedono meglio di O (n). E nessuno sano di mente lo implementerà in un modo peggiore di quello. Possiamo quindi tranquillamente supporre che si tratti nel caso peggiore O (n). Forse meglio ma non puoi mai contare su questo.
Tuttavia non è una specifica! : P –
@ tomalak-geretkal Nell'implementazione di gcc, questo è O (n). Concludiamo che le specifiche non lo richiedono meglio di O (n). E nessuno sarebbe così stupido da implementarlo in un modo peggiore di quello. Possiamo quindi tranquillamente supporre che sia sempre almeno O (n). Forse meglio ma non puoi mai contare su questo. – Haozhun
@Gene: Anche se in questo caso sono d'accordo, questo non risponde in modo rigoroso alla domanda originale di quali sono le specifiche di prestazione. Tuttavia, è una buona deduzione. –
"implementazione di riferimento di SIG eseguito in tempo lineare rispetto al numero di byte necessari per memorizzare i bit. Lo fa creando una matrice statica di 256 numeri interi. Il valore memorizzato all'indice ith nell'array è il numero di bit impostato nel valore i. "
Questo potrebbe essere accurato, ma solo un avvertimento qui che cplusplus.com è noto per essere pieno di errori. –
Inoltre, sarebbe una descrizione di una certa implementazione. –
@DavidThornley: Infatti, cplusplus.com è molto confuso (oserei dire, confuso?) Sulla biblioteca in generale. Usa il termine "STL" chiaramente insinuando che in realtà significa la libreria standard C++, ma poi le persone sui forum parlano dell'effettivo STL. –
io non sono sicuro che stai andando a trovare una specifica per questo, dal momento che lo STL in genere non richiedono un certo livello di prestazioni. Ho notato che è "veloce", circa 1 ciclo per bit nelle dimensioni dell'insieme. Ovviamente puoi leggere il codice della tua particolare implementazione per scoprire cosa aspettarti.
L'STL richiede in genere determinati livelli di prestazioni asintotiche (big-O). –
Non riesco ad essere sicuro di cosa intendiate realmente con "STL" qui, a causa di un uso scorretto del termine nella comunità C++.
L'++ standard C (2003) fa alcun mandato per l'esecuzione di std::bitset::count() (o, di fatto, tutti i membri di std::bitset per quanto posso vedere).
Non riesco a trovare alcun riferimento che suggerisca un mandato per le prestazioni di STL bitset::count().
Penso che qualsiasi implementazione sensata fornirà questo in tempo costante (o al peggio lineare), però. Tuttavia, questa è solo una sensazione. Controlla il tuo per scoprire cosa otterrai effettivamente.
Puoi condividere le altre cose a cui fa riferimento STL nel contesto del C++? – yasouser
Lo stesso commento che ti ho dato [qui] (http://stackoverflow.com/questions/2297164/stl-deque-accessing-by-index-is-o1/4694218#4694218). C'è un tempo per la pedanteria, non è questo. Commenta la domanda se vuoi chiarire l'uso di "STL" da parte di OP, ma non farne parte della tua risposta e fingere di essere in qualche modo incapace di capire cosa volesse dire, è arrogante e pretenzioso. * Spiega * le cose all'OP, non limitarti a dire "Non posso ottenerlo, non è strettamente definito!" – GManNickG
@GMan Avrei pensato di sottolineare che la sua domanda era vaga e quindi fornire una risposta per ENTRAMBI delle due cose che avrebbe potuto chiedere riguardo sarà sufficiente. Non vedo come dichiarare che non posso fare qualcosa è "arrogante"; leggere un dizionario E non è come se la mia risposta fosse "Non so cosa intendi, riprova". –
Quello che Tomalak ha menzionato (ma non è riuscito a * spiegare * perché è apparentemente insicuro e ha bisogno di affermare la propria conoscenza rispetto ad altri) è che STL (Standard Template Library) è un termine ambiguo. Alcuni di noi nella comunità C++ si sono espansi su questo nella [info-wiki per il tag] (http://stackoverflow.com/tags/stl/info), che dovrebbe chiarire il commento della fonte Tomalak. In breve, dovresti solo dire "libreria standard" o "stdlib", ma sapremo cosa intendi quando dici STL. – GManNickG
@GMan: Nessuna necessità di attacchi personali. Non sono i benvenuti qui su StackOverflow. Si prega di regolare il tono in futuro. –