Неупорядоченная (хэш) карта из набора битов в бит при ускорении - PullRequest
Новая
       40

Неупорядоченная (хэш) карта из набора битов в бит при ускорении

6 голосов
/ 09 октября 2010

Я хочу использовать кеш, реализованный в Boost unordered_map, от dynamic_bitset до dynamic_bitset Проблема, конечно, в том, что по умолчанию нет битовой функции из набора битов. Это не похоже на концептуальную проблему, но я не знаю, как решить технические вопросы. Как мне это сделать?

Ответы [ 5 ]

6 голосов
/ 09 октября 2010

Я нашел неожиданное решение.Оказывается, в бусте есть опция #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS.Когда это определено, закрытые члены, включая m_bits, становятся публичными (я думаю, что это связано со старыми компиляторами или чем-то еще).

Так что теперь я могу использовать ответ @ KennyTM, немного измененный: 

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);
    }
}
3 голосов
/ 09 октября 2010

Это запрос функции .

Можно реализовать неэффективный уникальный хэш, преобразовав битовый набор во временный вектор: 

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);
    }
}
3 голосов
/ 09 октября 2010

Есть to_block_range функция, которая копирует слова, из которых состоит набор битов, в некоторый буфер. Чтобы избежать реального копирования, вы можете определить свой собственный «выходной итератор», который просто обрабатывает отдельные слова и вычисляет из них хеш. Число рейнольдса как вычислить хеш: см. например хэш-функция FNV.

К сожалению, дизайн dynamic_bitset - это ИМХО, braindead, потому что он не дает вам прямой доступ к базовому буферу (даже как const).

2 голосов
/ 28 ноября 2011

Мы не можем напрямую вычислить хеш, потому что лежащие в основе dynamic_bitset данные являются частными (m_bits)

Но мы можем легко обмануть (подорвать!) Систему спецификации доступа c ++ без

  • взлом кода или
  • претензия на ваш компилятор не соответствует (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

Ключом является функция шаблона to_block_range, котораяот friend до dynamic_bitset.Поэтому специализации этой функции также имеют доступ к своим личным данным (например, m_bits).

Полученный код не может быть проще 

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;
}
}
0 голосов
/ 13 июля 2016

предлагаемое решение генерирует тот же хэш в следующей ситуации. 

#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!

предлагаемое решение иногда не подходит для отображения хеша.

Я прочитал исходный код dynamic_bitset, почему это произошлои понял, что dynamic_bitset хранит один бит на значение так же, как vector<bool>.Например, вы вызываете dynamic_bitset<> test(1, false), затем dynamic_bitset первоначально выделяет 4 байта со всеми нулями, и он содержит размер битов (в этом случае size равен 1).Обратите внимание, что если размер битов становится больше 32, то он снова выделяет 4 байта и возвращает его обратно в dynamic_bitsets<>::m_bits (поэтому m_bits - это вектор из 4 байтовых блоков).

Если я вызываю test.push_back(x) устанавливает второй бит в x и увеличивает размер битов до 2. Если x ложно, то m_bits[0] не изменяется вообще!Чтобы правильно вычислить хеш, нам нужно взять m_num_bits при вычислении хеша.

Тогда вопрос в том, как?

1: Использовать boost::hash_combine Этот подход прост и понятен.Я не проверял этот компилятор или нет. 

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: перевернуть m_num_bits% bits_per_block-й бит.перевернуть немного в зависимости от размера.Я считаю, что этот подход быстрее, чем 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;
    }
}
...