Question Le moyen le plus rapide de comparer les bitsets (

Quelle est la manière la plus optimisée de mettre en œuvre un < opérateur pour std::bitset correspondant à la comparaison de la représentation entière non signée (cela devrait fonctionner pour les bits more than 64 bits)?

Une mise en œuvre 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 "manière la plus optimisée", je recherche des implémentations utilisant des opérations au niveau du bit et des astuces de métaprogrammation (et des choses comme ça).

EDIT: Je pense que j’ai trouvé l’astuce: la métaprogrammation des modèles pour la récursion au moment de la compilation et le décalage vers la droite afin de comparer les bits en plusieurs entiers longs longs non signés. Mais aucune idée claire de la façon de le faire ...


11
2018-01-20 22:06


origine


Réponses:


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;
}

En dehors de cela, il devrait être tout à fait impossible d’utiliser un plus grand nombre de bits par test car il n’existe pas de méthode standard pour y accéder. Vous pourriez comparer x.to_string() < y.to_string() et l'espoir pour les deux to_string() et la comparaison de chaînes à optimiser mieux que l'accès bit à bit à un bitset, mais c'est un long coup.


10
2018-01-20 22:17



Bien que vous disiez bit set, vous ne parlez pas vraiment de la comparaison arbitraire des entiers non signés avec une précision arbitraire. Si c'est le cas, alors vous n'allez probablement pas faire mieux si vous emballez GMP.

De leur site web:

GMP est soigneusement conçu pour être aussi rapide que possible, à la fois pour les petites   des opérandes et des opérandes é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 une emphase générale sur la vitesse.

Considérer leurs fonctions entières


4
2018-01-21 00:23



Je viens de regarder le code source, mais malheureusement (sauf si, je l'espère, je me trompe), ils ne semblent pas vous donner accès à un const & unsigned long pour un bloc de bits particulier. Si c'est le cas, vous pouvez effectuer une récursion de modèle et comparer chaque unsigned long plutôt que chaque bit dans un long non signé.

Après tout, si A < B, alors non seulement chacun des bits les plus significatifs a <= b, également chacun des blocs les plus significatifs A[i] <= B[i].

Je déteste le dire, mais je roulerais sans doute avec la récursion sur C ++ 11 std::array. Si vous avez accès aux blocs, vous pouvez créer une fonction récursive de modèle pour le faire assez facilement (et comme vous le savez sûrement, car vous demandez une métaprogrammation), le compilateur a de grandes chances de s’optimiser.

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

Excellente question, au fait.

===========

MODIFIER

Cela devrait prendre le temps de 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 de modèle. Je remplis un vecteur de bits puis je trie de manière répétée en utilisant le foncteur de comparaison spécifié.

Heureux piratage!

Sortie sur mon ordinateur:

RUNTIMES:
compilé g ++ -std = c ++ 11 -Wall -g test.cpp
    std :: bits 4530000 (6000000 original dans OP)
    Bloc par bloc 900000
    Modèle récursif 730000

compilé g ++ -std = c ++ 11 -Wall -g -O3 test.cpp
RUNTIMES:
    std :: bitset 700000 (740000 original dans OP)
    Bloc par bloc 470000
    Modèle récursif 530000

Code C ++ 11:

#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;
}

4
2018-01-20 22:25



Que diriez-vous de vérifier le plus haut bit de XOR?

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
}

Quelques idées pour fps peut être trouvé ici http://uwfsucks.blogspot.be/2007/07/fls-implementation.html.


2
2018-01-20 22:16



Si vous êtes disposé à adopter la solution si le jeu de bits STL change, vous pouvez utiliser

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();
}

le compilateur jette la branche non pertinente du si loin


2
2018-03-26 09:52