6 Question: Le moyen le plus rapide de comparer des bits (<opérateur sur des bits)?

question créée à Mon, Jan 20, 2014 12:00 AM

Quel est le moyen le plus optimisé d'implémenter un opérateur < pour std::bitset correspondant à la comparaison de la représentation entière non signée (cela devrait fonctionner pour des bits de more than 64 bits)?

Une implémentation triviale serait:

 
template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
    for (int i = N-1; i >= 0; i--) {
        if (x[i] && !y[i]) return false;
        if (!x[i] && y[i]) return true;
    }
    return false;
}

Quand je dis "la manière la plus optimisée", je recherche des implémentations utilisant des opérations au niveau des bits et des astuces de métaprogrammation (et des choses comme ça).

EDIT: Je pense avoir trouvé l’astuce: la métaprogrammation de modèles pour la récursion à la compilation et le décalage de bits correct pour comparer les bits en tant que plusieurs entiers longs non signés. Mais aucune idée claire de la façon de le faire ...

    
11
  1. A propos de votre idée en utilisant bitshift correct: Cela créerait beaucoup d'objets intermédiaires et to_ullong devra vérifier si les valeurs décalées ne correspondent dans un unsigned long long pour chaque contrôle, créant ainsi un peu de frais généraux. Je doute que cela soit plus rapide, bien que seul un repère puisse le prouver.
    2014-01-20 22: 39: 24Z
  2. Copiez le code pour std :: bitset, renommez-le, donnez-lui une méthode pour accéder à un mot à la fois.
    2014-01-20 23: 04: 40Z
  3. @ brianbeuning Si vous copiez le code malgré tout, vous pouvez simplement fournir un operator< qui a accès aux éléments internes.
    2014-01-21 09: 05: 56Z
  4. @ Vincent J'ai mis à jour avec les exécutions ci-dessous: bit-sage (plus de votes actuels, bloc et modèle récursif, bloc par modèle).
    2014-01-22 16: 55: 25Z
6 réponses                              6                         

L’optimisation évidente serait

 
template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
    for (int i = N-1; i >= 0; i--) {
        if (x[i] ^ y[i]) return y[i];
    }
    return false;
}

À part cela, il devrait être pratiquement impossible d'utiliser plus de bits par test car il n'y a pas de moyen conforme à la norme pour y accéder. Vous pouvez évaluer x.to_string() < y.to_string() et espérer que la comparaison de chaînes et de chaînes soit mieux optimisée que l’accès au niveau des bits à un to_string(), mais c’est un long plan.

    
10
2014-01-20 22: 17: 07Z
  1. @ dyp Qui sait. C'est une question de performance, donc à la fin, il faudrait la comparer. Et cela pourrait changer avec chaque version du compilateur. Si vous envisagez de "petits" bits, vous pouvez également vous spécialiser pour 49 bits en utilisant bitset, mais je suppose que l'esprit de cette question s'apparente davantage à quelques centaines de bits.
    2014-01-20 22: 21: 58Z
  2. + 1 Pour une solution de sa taille, il est difficile de faire mieux. Pour la version de modèle de récursion, voir ci-dessous.
    2014-01-22 16: 48: 54Z
  3. Notez que même si to_ullong exposerait un membre std::bitset<N>, la commande lexicographique des conteneurs standard et .data() est difficile à optimiser à l'aide de cette connaissance. La chose la plus tentante à faire serait de faire une comparaison d’entier sur la représentation du mot sous-jacent, mais cela correspond en réalité à un ordre colexicographique inverse . Vous pouvez utiliser std::tuple comme std::lexicographical_compare(rbegin(R.data), rend(R.data), rbegin(L.data), rend(L.data)). Le "reverse" correspond à l'inversion L /R et le "co" aux itérateurs inverses en "reverse colexicographic".
    2014-08-10 11: 30: 11Z

Bien que vous disiez bit set, ne parlez-vous pas vraiment de comparaison d'entiers non signés à précision arbitraire. Si tel est le cas, vous ne ferez probablement pas mieux alors que l’emballage des BPF.

À partir de leur site Web:

GMP est soigneusement conçu pour être aussi rapide que possible, aussi bien pour les petits   opérandes et pour les opérands énormes. La vitesse est atteinte en utilisant   fullwords comme type arithmétique de base, en utilisant des algorithmes rapides, avec   code d'assemblage hautement optimisé pour les boucles internes les plus courantes   beaucoup de processeurs, et par un accent général mis sur la vitesse.

Envisagez de leurs fonctions entières

    
4
2014-01-21 00: 49: 39Z

Je n’ai fait que regarder le code source, mais malheureusement (à moins que, sauf erreur, je me trompe), ils ne semblent pas vous donner l’accès sur place à un operator<(L, R) pour un bloc de bits particulier. Si tel est le cas, vous pouvez alors effectuer une récursion de modèles et comparer efficacement chaque const & unsigned long plutôt que chaque bit dans un long signe.

Après tout, si unsigned long, alors non seulement chacun des bits de poids fort A < B, mais aussi chacun des blocs de poids fort a <= b.

Je n'aime pas le dire, mais je roulerais probablement moi-même en utilisant la récursion sur le A[i] <= B[i] de C ++ 11. Si vous avez accès aux blocs, alors vous pouvez créer une fonction de modèle récursive pour le faire assez facilement (et comme vous le savez sûrement depuis que vous demandez une métaprogrammation), donnez au compilateur une excellente occasion d’optimiser.

Dans l’ensemble, ce n’est pas une bonne réponse, mais c’est ce que je ferais.

Excellente question, au fait.

============

MODIFIER

Cela devrait prendre en compte trois approches: celle avec les votes les plus récents, la stratégie de bloc que j'ai décrite et une variante récursive du modèle. Je remplis un vecteur avec des bits puis trie de manière répétée en utilisant le foncteur comparateur spécifié.

Joyeux piratage!

Sortie sur mon ordinateur:

 std::array

Code C ++ 11:

 
RUNTIMES:
compiled g++ -std=c++11 -Wall -g test.cpp
    std::bitset         4530000 (6000000 original in OP)
    Block-by-block      900000
    Template recursive  730000

compiled g++ -std=c++11 -Wall -g -O3 test.cpp
RUNTIMES:
    std::bitset         700000 (740000 original in OP)
    Block-by-block      470000
    Template recursive  530000
    
4
2014-01-22 16: 59: 27Z

Pourquoi ne pas vérifier le bit le plus élevé de XOR?

 
#include <iostream>
#include <bitset>
#include <algorithm>
#include <time.h>

/* Existing answer. Note that I've flipped the order of bit significance to match my own */
template<std::size_t N>
class BitByBitComparator
{
public:
  bool operator()(const std::bitset<N>& x, const std::bitset<N>& y) const
  {
    for (int i = 0; i < N; ++i) {
      if (x[i] ^ y[i]) return y[i];
    }
    return false;
  }
};

/* New simple bit set class (note: mostly untested). Also note bad
   design: should only allow read access via immutable facade. */
template<std::size_t N>
class SimpleBitSet
{
public:
  static const int BLOCK_SIZE = 64;
  static const int LOG_BLOCK_SIZE = 6;
  static constexpr int NUM_BLOCKS = N >> LOG_BLOCK_SIZE;
  std::array<unsigned long int, NUM_BLOCKS> allBlocks;
  SimpleBitSet()
  {
    allBlocks.fill(0);
  }
  void addItem(int itemIndex)
  {
    // TODO: can do faster
    int blockIndex = itemIndex >> LOG_BLOCK_SIZE;
    unsigned long int & block = allBlocks[blockIndex];
    int indexWithinBlock = itemIndex % BLOCK_SIZE;
    block |= (0x8000000000000000 >> indexWithinBlock);
  }
  bool getItem(int itemIndex) const
  {
    int blockIndex = itemIndex >> LOG_BLOCK_SIZE;
    unsigned long int block = allBlocks[blockIndex];
    int indexWithinBlock = itemIndex % BLOCK_SIZE;
    return bool((block << indexWithinBlock) & 0x8000000000000000);
  }
};

/* New comparator type 1: block-by-block. */
template<std::size_t N>
class BlockByBlockComparator
{
public:
  bool operator()(const SimpleBitSet<N>& x, const SimpleBitSet<N>& y) const
  {
    return ArrayCompare(x.allBlocks, y.allBlocks);
  }

  template <std::size_t S>
  bool ArrayCompare(const std::array<unsigned long int, S> & lhs, const std::array<unsigned long int, S> & rhs) const
  {
    for (int i=0; i<S; ++i)
      {
    unsigned long int lhsBlock = lhs[i];
    unsigned long int rhsBlock = rhs[i];
    if (lhsBlock < rhsBlock) return true;
    if (lhsBlock > rhsBlock) return false;
      }
    return false;
  }
};

/* New comparator type 2: template recursive block-by-block. */
template <std::size_t I, std::size_t S>
class TemplateRecursiveArrayCompare;

template <std::size_t S>
class TemplateRecursiveArrayCompare<S, S>
{
public:
  bool operator()(const std::array<unsigned long int, S> & lhs, const std::array<unsigned long int, S> & rhs) const
  {
    return false;
  }
};

template <std::size_t I, std::size_t S>
class TemplateRecursiveArrayCompare
{
public:
  bool operator()(const std::array<unsigned long int, S> & lhs, const std::array<unsigned long int, S> & rhs) const
  {
    unsigned long int lhsBlock = lhs[I];
    unsigned long int rhsBlock = rhs[I];
    if (lhsBlock < rhsBlock) return true;
    if (lhsBlock > rhsBlock) return false;

    return TemplateRecursiveArrayCompare<I+1, S>()(lhs, rhs);
  }
};

template<std::size_t N>
class TemplateRecursiveBlockByBlockComparator
{
public:
  bool operator()(const SimpleBitSet<N>& x, const SimpleBitSet<N>& y) const
  {
    return TemplateRecursiveArrayCompare<x.NUM_BLOCKS, x.NUM_BLOCKS>()(x.allBlocks, y.allBlocks);
  }
};

/* Construction, timing, and verification code */
int main()
{
  srand(0);

  const int BITSET_SIZE = 4096;

  std::cout << "Constructing..." << std::endl;

  // Fill a vector with random bitsets
  const int NUMBER_TO_PROCESS = 10000;
  const int SAMPLES_TO_FILL = BITSET_SIZE;
  std::vector<std::bitset<BITSET_SIZE> > allBitSets(NUMBER_TO_PROCESS);
  std::vector<SimpleBitSet<BITSET_SIZE> > allSimpleBitSets(NUMBER_TO_PROCESS);
  for (int k=0; k<NUMBER_TO_PROCESS; ++k)
    {
      std::bitset<BITSET_SIZE> bs;
      SimpleBitSet<BITSET_SIZE> homemadeBs;
      for (int j=0; j<SAMPLES_TO_FILL; ++j)
    {
      int indexToAdd = rand()%BITSET_SIZE;
      bs[indexToAdd] = true;
      homemadeBs.addItem(indexToAdd);
    }

      allBitSets[k] = bs;
      allSimpleBitSets[k] = homemadeBs;
    }

  clock_t t1,t2,t3,t4;
  t1=clock();

  std::cout << "Sorting using bit-by-bit compare and std::bitset..."  << std::endl;
  const int NUMBER_REPS = 100;
  for (int rep = 0; rep<NUMBER_REPS; ++rep)
    {
      auto tempCopy = allBitSets;
      std::sort(tempCopy.begin(), tempCopy.end(), BitByBitComparator<BITSET_SIZE>());
    }

  t2=clock();

  std::cout << "Sorting block-by-block using SimpleBitSet..."  << std::endl;
  for (int rep = 0; rep<NUMBER_REPS; ++rep)
    {
      auto tempCopy = allSimpleBitSets;
      std::sort(tempCopy.begin(), tempCopy.end(), BlockByBlockComparator<BITSET_SIZE>());
    }

  t3=clock();

  std::cout << "Sorting block-by-block w/ template recursion using SimpleBitSet..."  << std::endl;
  for (int rep = 0; rep<NUMBER_REPS; ++rep)
    {
      auto tempCopy = allSimpleBitSets;
      std::sort(tempCopy.begin(), tempCopy.end(), TemplateRecursiveBlockByBlockComparator<BITSET_SIZE>());
    }

  t4=clock();

  std::cout << std::endl << "RUNTIMES:" << std::endl;
  std::cout << "\tstd::bitset        \t" << t2-t1 << std::endl;
  std::cout << "\tBlock-by-block     \t" << t3-t2 << std::endl;
  std::cout << "\tTemplate recursive \t" << t4-t3 << std::endl;
  std::cout << std::endl;

  std::cout << "Checking result... ";
  std::sort(allBitSets.begin(), allBitSets.end(), BitByBitComparator<BITSET_SIZE>());
  auto copy = allSimpleBitSets;
  std::sort(allSimpleBitSets.begin(), allSimpleBitSets.end(), BlockByBlockComparator<BITSET_SIZE>());
  std::sort(copy.begin(), copy.end(), TemplateRecursiveBlockByBlockComparator<BITSET_SIZE>());
  for (int k=0; k<NUMBER_TO_PROCESS; ++k)
    {
      auto stdBitSet = allBitSets[k];
      auto blockBitSet = allSimpleBitSets[k];
      auto tempRecBlockBitSet = allSimpleBitSets[k];

      for (int j=0; j<BITSET_SIZE; ++j)
    if (stdBitSet[j] != blockBitSet.getItem(j) || blockBitSet.getItem(j) != tempRecBlockBitSet.getItem(j))
      std::cerr << "error: sorted order does not match" << std::endl;
    }
  std::cout << "success" << std::endl;

  return 0;
}

Vous trouverez ici quelques idées pour

bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
    return y[fls(x^y)]
}

int fls(const std::bitset<N>& n) {
    // find the last set bit
}
http: //uwfsucks.blogspot. be /2007/07 /fls-implementation.html .     
2
2014-01-20 22: 44: 52Z
  1. Bonne idée, sauf que l'opérateur moins n'est pas défini pour les bitsets ...
    2014-01-20 22: 54: 24Z
  2. Problème: l'optimisation de fps nécessite un accès interne au jeu de bits au même titre que la question d'origine.
    2014-01-21 00: 21: 18Z

Si vous souhaitez adopter la solution en cas de modification du jeu de bits STL, vous pouvez utiliser

.  fls

le compilateur jette la branche non pertinente de if away

    
2
2016-03-26 09: 52: 24Z

Eh bien, il y a le bon vieux

template<int n>
bool compare(bitset<n>& l, bitset<n>& r){
  if(n > 64){
  typedef array<long, (n/64)> AsArray;
  return *reinterpret_cast<AsArray*>(&l)
       < *reinterpret_cast<AsArray*>(&r);
    }//else
  return l.to_ulong() < r.to_ulong();
}
. C'est fragile en ce sens que cela dépend de la mise en œuvre de memcmp. Et pourrait donc être inutilisable. Mais il est raisonnable de supposer que le modèle crée un tableau opaque de std::bitset s. Et n'a pas d'autres champs de comptabilité.  int

Ceci déterminera de manière unique un ordre pour

template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
    int cmp = std::memcmp(&x, &y, sizeof(x));
    return (cmp < 0);
}
s. Mais cela pourrait ne pas être un ordre intuitif humain. Cela dépend des bits utilisés pour quel ensemble d'index de membre. Par exemple, l'index 0 pourrait être le LSB du premier entier de 32 bits. Ou ce pourrait être le LSB du premier octet de 8 bits.

Je vivement recommande des tests unitaires pour vérifier que cela fonctionne réellement pour l'utilisation qui en est faite. ; - >

    
0
2018-09-15 18: 49: 56Z
bitset
source placée ici