J'ai cherché autour de là et n'a pas pu trouver les spécifications de l'heure de la performance pour Bitset :: Count (). Est-ce que quelqu'un sache ce qu'il est (O (n) ou mieux) et où le trouver?
5 Réponses :
"La mise en œuvre de référence de SGI fonctionne en temps linéaire par rapport à la Nombre d'octets nécessaires pour stocker le morceaux. Cela le fait en créant un Tableau statique de 256 entiers. Les valeur stockée sur ith index dans le tableau est le nombre de bits définis dans la valeur i. "
Cela peut bien être précis, mais juste un avertissement ici que Cplusplus.com est bien connu pour être criblé d'erreurs.
De plus, ce serait une description d'une certaine mise en œuvre.
@Davidthornley: En effet, Cplusplus.com est très déroutant (osez-moi dire, confus?) À propos de la bibliothèque en général. Il utilise le terme "stl" insinuant clairement que cela signifie vraiment la bibliothèque standard C ++, mais les gens sur les forums parlent de la STL.
Merci pour le lien. Je l'ai vu avant de poster la question, mais il manquait des pointeurs vers une spécification claire.
Je ne suis pas sûr que vous allez trouver une spécification pour cela, car la STL n'exige pas généralement un certain niveau de performance. J'ai vu des indices que c'est "rapide", environ 1 cycle par bit dans la taille de l'ensemble. Vous pouvez bien sûr lire votre code de votre implémentation pour savoir à quoi vous attendre.
La STL nécessite généralement certains niveaux de performances asymptotiques (Big-O).
J'ai lu ce fichier (C: \ CYGWIN \ LIB \ GCC \ I686-PC-CYGWIN \ 3.4.4 \ Inclure \ C ++ \ Bitset) sur mon ordinateur.
Voir ces
template<size_t _Nw>
struct _Base_bitset
Ce n'est pas une spécification cependant! : P
@ Tomalak-Geretkal dans la mise en œuvre de la GCC, c'est O (n). Nous concluons que la spécification ne le nécessite pas mieux que O (n). Et personne ne serait si stupide de le mettre en œuvre d'une manière pire que cela. Nous pouvons ensuite supposer que c'est toujours au moins O (n). Peut-être mieux mais vous ne pouvez jamais compter sur cela.
@Gene: tandis que dans ce cas, je suis d'accord, cela ne répond pas strictement à la question initiale de ce que sont les spécifications de la performance. Cependant, c'est une bonne déduction.
@ Tomalak-Geretkal: Merci pour votre conseil.
Je ne peux pas être sûr de ce que vous entendez vraiment par "stl" ici, en raison d'une mauvaise utilisation du terme de la communauté C ++.
La norme C ++ (2003) ne fait aucun mandat pour la performance de Je ne trouve aucune référence suggérant un mandat pour la performance du Je pense que toute mise en œuvre sane fournira ceci en constante (ou au pire linéaire), cependant. Cependant, c'est simplement un sentiment. Vérifiez le vôtre pour savoir ce que vous obtiendrez réellement.
std :: bitset :: compte () (ou, en fait, des membres de std :: Bitset autant que je puisse voir).
Bitset de STL :: Comptoir () non plus.
Pouvez-vous partager les autres choses que STL se réfère dans le contexte de C ++?
Même commentaire que je vous ai donné ici . Il y a un temps pour la pédantisme, ce n'est pas ça. Commentaire sur la question Si vous souhaitez clarifier l'utilisation de l'OP de «STL», mais ne faites pas partie de votre réponse et que vous vous fontignez d'être incapable de comprendre ce qu'il voulait dire, c'est arrogant et prétentieux. Expliquez des choses à l'OP, ne dis pas que "Je ne peux pas éventuellement obtenir ceci, ce n'est pas strictement défini!"
@Gman J'aurais pensé souligner que sa question était vague puis fournissait une réponse pour les deux choses qu'il aurait pu poser de la question à laquelle il suffira de suffire. Je ne vois pas comment déclarer que je ne peux pas faire quelque chose est "arrogant"; lire un dictionnaire. Et ce n'est pas comme si toute ma réponse était "Je ne sais pas ce que tu veux dire, essayez à nouveau".
L'algorithme que nous suivons est de compter tous les bits qui sont définis sur 1. Maintenant, si nous voulons compter sur ce bitset pour un numéro N, nous passerons par le journal (n) +1 chiffres.
Par exemple: Pour le numéro 13, nous obtenons 1101 comme bitset.
Journal naturel de 13 = 2.564 (environ) 3
Nombre de bits = 3 + 1 = 4
pour n'importe quel nombre N (décimal) We Loop Lock (n) +1 fois .
Une autre approche serait la suivante: si vous analysez la ligne fonctionnelle N = (N & (N-1)); Vous constaterez que cela réduit essentiellement le nombre de bits de droite à gauche. La commande serait donc un nombre de bits de jeu total. Par exemple: 13 = 1101 1101 & 1100 = 1100 1100 et 1011 = 1000 1000 & 0111 = 0 O (nombre de bits de jeu), O (log (n) +1 ) Pire des cas
Ce que Tomalak a mentionné (mais omis de expliquer parce qu'il est apparemment peu sûr d'être sûr et doit affirmer ses connaissances sur les autres) est que STL (la bibliothèque de modèles standard) est un terme ambigu. Certains d'entre nous dans la communauté C ++ se sont étendus à ce sujet dans le info-wiki pour la balise , qui devrait clarifier la source Tomalak commenter. En bref, vous devriez simplement dire «bibliothèque standard» ou «stdlib», mais nous saurons ce que vous voulez dire lorsque vous dites STL.
@Gman: Pas besoin d'attaques personnelles. Ils ne sont pas les bienvenus ici sur Stackoverflow. Veuillez ajuster votre ton à l'avenir.