Могу ли я выскочить из HashSet эффективно?

Question

Мой алгоритм должен итеративно сокращать набор, удаляя элемент, и делать что-то с удаленным элементом и с набором сокращения в каждой итерации.И:

• Мне нужен подлинный набор с быстрым поиском, а не просто вектор, содержащий уникальные элементы.
• Выбор элемента произвольный: исход алгоритма не зависитна заказ посетил.Производительность, вероятно, сильно зависит от этого выбора, но, скажем, я хочу самый простой код и оставляю его на усмотрение самого набора, чтобы выбрать элемент, который он может эффективно удалить.
• Кстати, мой алгоритм - основная форма алгоритма Брон-Кербоша .Более умные версии этого алгоритма работают быстрее (в основном), потому что они не оставляют выбор элемента произвольным, и я хотел бы узнать, сколько стоит это усилие.

Наборы Python имеют pop член, который в значительной степени делает это.В Scala и Go выбор и удаление «первого» элемента хеш-набора, кажется, работает нормально (где «first» соответствует итератору).В Rust это что-то вроде:

// split off an arbitrary element from a (non-empty) set
pub fn pop<T>(set: &mut HashSet<T>) -> T
where
    T: Eq + Clone + std::hash::Hash,
{
    let elt = set.iter().next().cloned().unwrap();
    set.remove(&elt);
    elt
}

Это, похоже, узкое место в производительности по сравнению с другими языками.Я провел бенчмаркинг некоторых реализаций поп-функции на игровой площадке , но ни одна из них не работает хорошо.Очевидно, что удаление элемента не дорого, но его выбор: iter().next() стоит целое состояние (*).Понятно, что избежать этого с retain не помогает: он всегда повторяет весь набор.Есть ли альтернативы?

PS при ближайшем рассмотрении, iter().next() довольно дешево, пока микробенчмаркингу можно доверять. Отдельные микробенчмарки говорят, что выбор произвольного элемента из набора стоит (в наносекундах в моей системе):

| Type of set      | Number of elements in set instance
|                  | 100 | 10,000 | 1,000,000
| Rust HashSet     |   2 |      2 |         2
| Rust BTreeSet    |  11 |     12 |        13
| Go map[]struct{} |  27 |     31 |        94
| Python set       | 125 |    125 |       125

Answer 1

набор, который я использую, имеет целые числа

Не используйте HashSet;A BTreeSet имеет лучшую и более стабильную производительность.

Для N = 100000 ...

BTreeSet

sequenced : 3065.098µs
pop_1     : 2941.876µs
pop_2     : 2927.429µs

HashSet

sequenced : 3091.454µs
pop_1     : 172547.080µs
pop_2     : 807182.085µs

Answer 2

Ваш код может быть немного упрощен:

let elt = set.iter().next().cloned().unwrap();
set.take(&elt).unwrap()

Если вы хотите удалить все элементы из HashSet, вам следует использовать итератор drain - этоочень эффективный.

HashSet из стандартной библиотеки Rust не такой быстрый.Попробуйте заменить его одним из ящика hashbrown .

Answer 3

Я полагаю, что тот же совет применим, что и в Могу ли я эффективно выбрать случайную выборку из HashSet? : скопировать набор как вектор, просто чтобы выполнить итерацию по нему, как показано в «1003 *« последовательном »решении вбенчмарк :

let seq: Vec<u32> = set.iter().cloned().collect();
for elt in seq {
    set.remove(&elt);

Это означает, что этот ответ неприменим, если вам нужно уменьшить набор (выбрать произвольный элемент) только один или несколько раз, или если содержимое набора не может быть дешевымклонировали.