Nieuporządkowana (hash) mapa od zestawu bitów do zestawu bitów przy doładowaniu

Question

Chcę użyć pamięci podręcznej, zaimplementowanej przez zwiększenie liczby unordered_map, z dynamic_bitset do dynamic_bitset. Problem polega oczywiście na tym, że nie ma domyślnej funkcji skrótu z zestawu bitów. Nie wydaje się to być problemem konceptualnym, ale nie wiem, jak opracować szczegóły techniczne. Jak mam to zrobić?

Answer 1

że nieoczekiwany roztworu. Okazuje się, że boost ma opcję na #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. Kiedy to jest zdefiniowane, prywatni członkowie, włączając w to m_bits, stają się publiczni (wydaje mi się, że jest tam do czynienia ze starymi kompilatorami lub czymś podobnym).

Więc teraz mogę używać @ odpowiedź KennyTM za, zmienił się trochę:

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {    
     return boost::hash_value(bs.m_bits); 
    } 
} 

Answer 2

Istnieje funkcja to_block_range polegająca na tym, że kopiuje poza słowami, które zestaw bitów składa się w jakimś buforze. Aby uniknąć faktycznego kopiowania, możesz zdefiniować własny "wynikowy iterator", który przetwarza pojedyncze słowa i oblicza ich wartość. Re. jak obliczyć hash: patrz np. funkcja skrótu FNV.

Niestety, projekt dynamic_bitset jest IMHO, braindead, ponieważ nie daje bezpośredni dostęp do leżącego poniżej bufora (nawet jako const).

Answer 3

To jest feature request.

Można było wdrożyć niezbyt wydajne unikalny mieszania przekształcając bitset z wektorem czasowego:

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     std::vector<B, A> v; 
     boost::to_block_range(bs, std::back_inserter(v)); 
     return boost::hash_value(v); 
    } 
} 

Answer 4

Nie możemy bezpośrednio obliczyć hash ponieważ bazowe dane dynamic_bitset jest prywatna (m_bits)

ale możemy łatwo finezja przeszłość (obalić!) C++ specyfikacja systemu dostęp bez obu

• hacking na kod lub
• udając kompilator jest niezgodnych (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

klucz jest funkcja szablon to_block_range który jest friend do dynamic_bitset. Specjalizacje tej funkcji mają również dostęp do jej prywatnych danych (tj. m_bits).

Otrzymany kod nie może być prostsze

namespace boost { 


// specialise dynamic bitset for size_t& to return the hash of the underlying data 
template <> 
inline void 
to_block_range(const dynamic_bitset<>& b, size_t& hash_result) 
{ 
    hash_result = boost::hash_value(bs.m_bits); 
} 

std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) 
{    
    size_t hash_result; 
    to_block_range(bs, hash_result); 
    return hash_result; 
} 
} 

Answer 5

proponowane rozwiązanie samo generuje mieszania w następującej sytuacji.

#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS 

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {    
     return boost::hash_value(bs.m_bits); 
    } 
} 

boost::dynamic_biset<> test(1,false); 

auto hash1 = boost::hash_value(test); 

test.push_back(false); 

auto hash2 = boost::hash_value(test); 

// keep continue... 

test.push_back(false); 

auto hash31 = boost::hash_value(test); 

// magically all hash1 to hash31 are the same! 

proponowane rozwiązanie jest czasami niewłaściwe dla mapy skrótów.

Przeczytałem kod źródłowy zestawu dynamicznego, dlaczego tak się stało i zdałem sobie sprawę, że dynamiczny_bitset przechowuje jeden bit na wartość tak samo jak vector<bool>. Na przykład wywołujemy dynamic_bitset<> test(1, false), a następnie dynamiczne_bitset początkowo przydziela 4 bajty ze wszystkimi zerami i utrzymuje rozmiar bitów (w tym przypadku rozmiar to 1).Zauważ, że jeśli rozmiar bitów staje się większy niż 32, to przydziela 4 bajty ponownie i przesyła je z powrotem do dynamic_bitsets<>::m_bits (więc m_bits jest wektorem 4 bloków bajtów).

Jeśli zadzwonię pod numer test.push_back(x), ustawia on drugi bit na x i zwiększa rozmiar bitów do 2. Jeśli x ma wartość false, oznacza to, że m_bits[0] nie zmienia się wcale! Aby poprawnie obliczyć hash, musimy wziąć m_num_bits w obliczeniach haszujących.

Następnie pytanie brzmi: jak?

1: Użyj boost::hash_combine To podejście jest proste i proste. Nie sprawdziłem tej kompilacji, czy nie.

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     size_t tmp = 0; 
     boost::hash_combine(tmp,bs.m_num_bits);   
     boost::hash_combine(tmp,bs.m_bits); 
     return tmp; 
    } 
} 

2: odwróć m_num_bits% bits_per_block th bit. odwróć nieco na podstawie rozmiaru bitowego. Uważam, że takie podejście jest szybsze niż 1.

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     // you may need more sophisticated bit shift approach. 
     auto bit = 1u << (bs.m_num_bits % bs.bits_per_block); 
     auto return_val = boost::hash_value(bs.m_bits); 

     // sorry this was wrong 
     //return (return_val & bit) ? return_val | bit : return_val & (~bit); 
     return (return_val & bit) ? return_val & (~bit) : return_val | bit; 
    } 
}