unordered_map с запрещенными коллизиями - PullRequest
Новая
       2

unordered_map с запрещенными коллизиями

3 голосов
/ 11 апреля 2011

Я хочу реализовать оптимизированный по производительности вариант unordered_map, который работает в несколько этапов:

  1. Инициализация: вставить около 100 элементов в std::map
  2. Подготовка: Выполнитьнекоторая магия, преобразующая std::map в вариант std::unordered_map
  3. Работа: Выполнить большое (неограниченное) количество поисков;вставки / удаления запрещены

Чтобы сделать фазу «работы» максимально быстрой, я бы хотел выбрать функцию хеширования, в которой нет коллизий для данного набора ключей (собранных при инициализации).фаза).

Я хотел бы измерить, насколько улучшение производительности я могу получить с помощью этого трюка.Так что это будет эксперимент, возможно, входящий в производственный код.

Есть ли в стандартной библиотеке средства для этой реализации (например, определение количества коллизий, которые имеет данный unordered_map, или изменение функции хеширования)?Или я должен вместо этого сделать свою собственную реализацию?

Ответы [ 3 ]

6 голосов
/ 11 апреля 2011

Вот API «управления коллизиями»: 

size_type bucket_count() const;
size_type max_bucket_count() const;

size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;

local_iterator       begin(size_type n);
local_iterator       end(size_type n);
const_local_iterator begin(size_type n) const;
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;

В двух словах, bucket_size(n) дает вам количество коллизий для n-го сегмента.Вы можете искать сегменты с ключом, и вы можете перебирать сегменты с помощью local_iterator.

Для изменения хеш-функции я бы назначил / сконструировал новый контейнер, от старой хеш-функции до нового.

2 голосов
/ 11 апреля 2011

Если у вас много чтений и меньше записей, вы можете использовать вектор как карту. Это очень распространено, потому что lower_bound более эффективен, чем map и использует меньше места в памяти: 

bool your_less_function( const your_type &a, const your_type &b )
{
  // based on keys
  return ( a < b );
}
...
std::vector<your_type> ordered-vector;

Когда вы добавляете значения: 

...
// First 100 values
ordered-vector.push_back(value)
...
// Finally. The vector must be sorted before read.
std::sort( ordered-vector.begin(), ordered-vector.end(), your_less_function );

Когда запрашивать данные: 

std::vector<your_type>::iterator iter = std::lower_bound( ordered-vector.begin(), ordered-vector.end(), value, your_less_function );
if ( ( iter == ordered-vector.end() ) || your_less_function( *iter, value ) )
  // you did not find the value
else
  // iter contains the value

К сожалению, это заказано, но очень быстро.

0 голосов
/ 11 апреля 2011

Количество столкновений зависит от количества ведер.Полезно ли вам использовать функцию rehash, чтобы установить количество сегментов равным 100, как указано в документации boost ?

...