Puis-je vérifier en C (++) si un tableau est tout 0 (ou faux)?

Question

chèque Puis-je en C (++) si un tableau est tout 0 (ou faux) sans itérer / boucle sur chaque valeur unique et sans allouer un nouveau tableau de la même taille (à l'utilisation memcmp)?

J'abuser un tableau de bools d'avoir de grandes bitsets arbitraires à l'exécution et faire quelques bitflipping dessus

Answer 1

Vous pouvez utiliser la condition suivante:

(myvector.end() == std::find(myvector.begin(), myvector.end(), true))

De toute évidence, à l'intérieur, cette boucle sur toutes les valeurs.

L'alternative (qui devrait vraiment éviter les boucles) est de remplacer toutes les fonctions d'accès en écriture, et de garder trace de savoir si true n'a jamais été écrit à votre vecteur.

UPDATE

Les commentaires de Lie Ryan décrit ci-dessous une méthode plus robuste de le faire, basé sur le même principe.

Answer 2

Si ce n'est pas triée, non. Comment qualifieriez-vous planifier sur la réalisation de cela? Vous auriez besoin d'inspecter tous les éléments pour voir si elle est 0 ou non! memcmp, bien sûr, vérifierait également tous les éléments. Il serait tout simplement beaucoup plus cher, car il lit un autre tableau aussi bien.

Bien sûr, vous pouvez précoce dès que vous touchez un élément non-0.

Votre seule option serait d'utiliser SIMD (qui vérifie techniquement encore chaque élément, mais en utilisant moins d'instructions), mais vous ne le faites généralement que dans un tableau générique.

(BTW, ma réponse suppose que vous avez un exemple simple tableau C / C ++ statique. Si vous pouvez spécifier quel type de tableau que vous avez, nous pourrions être plus précis).

Answer 3

Si vous savez que cela va être une exigence, vous pourriez construire une structure de données consistant en un réseau (éventuellement dynamique) et un nombre ou en cellules non nulles. Il est évident que le réglage des cellules doit être prélevée à travers, mais ce qui est naturel en C ++ avec la surcharge, et vous pouvez utiliser un type opaque c.

Answer 4

Supposons que vous avez un tableau d'éléments N, vous pouvez faire une vérification de bits contre un ensemble de vecteurs de base.

Par exemple, vous avez un tableau de 15 éléments que vous souhaitez tester.

On peut tester contre un zéro tableau 8 de l'élément, un ensemble de zéro à 4 éléments, un zéro tableau 2 de l'élément et un zéro tableau 1 de l'élément.

Il vous suffit de répartir ces éléments une fois étant donné que vous connaissez la taille maximale des tableaux que vous souhaitez tester. En outre, le test peut être effectué en parallèle (et avec l'ensemble intrinsèque si nécessaire).

Une nouvelle amélioration en terme d'allocation de mémoire peut être fait avec l'aide de seulement une matrice de 8 éléments depuis un zéro tableau 4 de l'élément est simplement la première moitié de la matrice zéro 8-élément.

Answer 5

Pensez à utiliser boost::dynamic_bitset à la place. Il a un membre de none et plusieurs autres std::bitset comme les opérations, mais sa longueur peut être réglée à l'exécution.

Answer 6

Non, vous pouvez comparer les tableaux avec memcmp, mais vous ne pouvez pas comparer une valeur par rapport à un bloc de mémoire.

Qu'est-ce que vous pouvez faire est d'utiliser des algorithmes en C ++, mais qui implique toujours une boucle interne.

Answer 7

Vous n'avez pas à itérer sur l'ensemble de chose, juste arrêter en boucle sur la première valeur non nulle.

Je ne peux pas penser à un moyen de vérifier un ensemble de valeurs autres que les inspecter à tour de rôle - vous pouvez jouer à des jeux avec la vérification de la mémoire sous-jacente comme quelque chose de plus grand que bool (par exemple de __int64), mais l'alignement est alors un problème.

EDIT: Vous pouvez garder un décompte séparé des bits de consigne, et vérifier que est non nul. Il faudrait faire attention à l'entretien de ce fait, de sorte que la fixation d'un bit de jeu n'a pas ++ et ainsi de suite.

Answer 8

Knittl,

Je ne pense pas que vous avez accès à une fantaisie matériel DMA sur l'ordinateur cible? Parfois, des supports matériels DMA exactement l'opération dont vous avez besoin, à savoir « Est cette région de la mémoire tout à zéro? » Ce genre de comparaison avec accélération matérielle est une solution commune en traitant avec un grand bit-tampons. Par exemple, certains contrôleurs RAID utilisent ce mécanisme pour le contrôle de parité.