Более эффективный способ заполнить unordered_set? - PullRequest
Новая
       18

Более эффективный способ заполнить unordered_set?

4 голосов
/ 12 апреля 2019

У меня есть массив целых чисел, хранящихся непрерывно в памяти, и я хочу добавить их все в коллекцию unordered_set.

Сейчас я добавляю их по одному за раз. 

for (int i = 0; i < count; i++)
    collection.insert(pi[i]);

Есть ли способ сделать это более эффективно?

Я понимаю, что элементы не хранятся в коллекции непрерывно, поэтому это будет не так просто, как просто передать массив в коллекцию.,Но можно ли это как-то оптимизировать?

Ответы [ 2 ]

6 голосов
/ 12 апреля 2019

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

template< class InputIt >
unordered_set( InputIt first, InputIt last,
           size_type bucket_count = /*implementation-defined*/,
           const Hash& hash = Hash(),
           const key_equal& equal = key_equal(),
           const Allocator& alloc = Allocator() );

Так что вы можете просто сделать collection = std::unordered_set{ p, p + count }; и оставить его до реализации.

Как отметил другой пользователь в комментариях, существует также перегрузка для insert, которая принимает диапазон: 

template< class InputIt >
void insert( InputIt first, InputIt last );

Так что, как и при вызове конструктора, вы можете сделать, collection.insert(p, p + count);

Нет гарантии, что эти перегрузки будут более эффективными, поскольку сложность линейна как в среднем по обеим перегрузкам, так и для простого вставления элементов один за другим.

На самом деле, если мы посмотрим, как insert реализован в MSVC, это очень просто 

template<class _Iter>
void insert(_Iter _First, _Iter _Last)
{   // insert [_First, _Last) at front, then put in place
    _DEBUG_RANGE(_First, _Last);
    for (; _First != _Last; ++_First)
        emplace(*_First);
}

, поэтому никакой оптимизации для этого случая.

Я думаю, лучший способ сделать это - позвонить reserve, если вызнать количество элементов, которые вы собираетесь добавить, и, если есть много коллизий (которых не будет для целых чисел), возможно, измените bucket_count.

2 голосов
/ 12 апреля 2019

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

Рассмотрите возможность вызова резерва метод std :: unordered_set. 

collection.reserve(pi.size());
collection.insert(pi.begin(), pi.end());

РЕДАКТИРОВАТЬ: Как уже упоминалось в комментариях, можно также беспокоиться об эффективности хеширования вставленных элементов один за другим.Тогда было бы эффективно выполнять какие-то массовые вставки.Однако в случае OP элементы являются целыми числами, которые хэшируются с использованием функции тождественности в большинстве, если не во всех реализациях std :: hash, что не так дорого стоит;).Действительно, это лучшая хеш-функция, которую можно получить для случайных целых чисел.Другие хэш-функции могут быть более подходящими в случае «организованных» наборов.

EDIT2: в разделе комментариев теперь рассуждают о том, что может быть лучшей реализацией метода вставки.Я утверждаю, что перегрузка вставки, основанная на диапазоне, запрашивает входные итераторы, так что да, вы можете фактически передать любой не выходной итератор.Также обратите внимание на сложность наихудшего случая для вставки диапазона: вы увидите, что он указан так, что ему разрешено вставлять элементы один за другим.Наконец, взгляните на некоторые реализации метода вставки, и вы увидите, что для итераторов с произвольным доступом нет особой перегрузки.Это имеет смысл, поскольку нет причин налагать дополнительную проверку в методе вставки, в то время как резервный метод здесь для случая, когда мы хотим установить контейнер, по крайней мере, на заданную емкость.Исходя из этого, приведенный выше ответ, скорее всего, будет лучшим методом, основанным на реальных реализациях stdlib.

...