unordered_map‹TYPE, bool› срещу set‹TYPE›

Какви са действителните компромиси от използването на колекция тип хеш таблица като std::unordered_map срещу std::set?

За нещо случайно, върху което работя (в C++), имам зададен проблем с пресичане на идентифициране на дублирани елементи от двойка големи списъци.

Първото ми предположение беше да премина през първия списък и да вмъкна всеки в std::unordered_map<T, bool> или (std::hash_map), където стойността на параметъра при вмъкване винаги е true. След това направете справки в hash_map за всеки елемент във втория списък. Работното предположение е, че всяко вмъкване е O(1) и всяко търсене също е O(1).

Тогава започнах да мисля, че може би std::set е по-подходящ. Някои повърхностни търсения онлайн разкриват, че реализацията на std::set е червено/черно истина и че вмъкванията и/или търсенето може да са във време на изпълнение O(lg n) вместо O(1). (Вярно ли е?)

Предполагам, че компромисите между всеки може да са използването на паметта и използването на функция за хеширане (срещу директно сравнение). Действителният тип на данните, които използвам, е просто unsigned int. Мога да си представя, че динамиката на този проблем може да се промени въз основа на по-сложен тип с различна функция за хеширане.


c++ set hashtable
person selbie    schedule 12.06.2014    source източник
comment
Какви видове контейнери са вашите списъци? И колко елемента съдържат приблизително?   -  person 101010    schedule 13.06.2014
comment
Какво ще кажете за std::unordered_set?   -  person T.C.    schedule 13.06.2014
comment
Карта и комплект респ. неподредените версии могат да бъдат изразени една от друга, без загуба на функционалност / ефективност / гъвкавост. Също така изпълнението не е договорно, въпреки че има гаранции за изпълнение.   -  person Deduplicator    schedule 13.06.2014
comment
Със сигурност е по-ефективно да се представи набор като набор, вместо допълнително да се записва bool, което трябва да бъде true, за да може елементът да се брои. Колко допълнителните записи, допълнителните тестове и допълнителното пространство за bool биха попречили на производителността, зависи от точните числа и точното изпълнение.   -  person Deduplicator    schedule 13.06.2014
comment
Защо просто не сортирате списъците и не използвате std::set_intersection или нещо подобно? Ако трябва да бъда честен, както хеш-таблиците и двоичните дървета за търсене се използват прекалено много. Нямате нужда от тях в много случаи, които си мислите, че имате. Също така: какъв тип данни е T?   -  person user541686    schedule 13.06.2014

Отговори (2)


arrow_upward
2
arrow_downward

Ако приемем, че имате 2 списъка (напр. L1 и L2) с N и M брой елементи съответно. И също така, че L1 и L2 имат уникални елементи. (т.е. L#(i) != L#(j) за всяко i != j).

Вашият първи алгоритъм:

стъпка 1: Копирайте елементи от L1 в unordered_map U, е с времева сложност:

  • Среден случай O(N).

  • Най-лошият случай O(N^2).

стъпка 2: Превъртете през елементите на L2 и за всеки елемент проверете дали съществува в U.

  • Среден случай O(M) * O(1) = O(M).

  • Най-лошият случай O(M) * O(N) = O(M*N).

Като цяло:

  • Среден случай O(N) + O(M), линейна сложност.

  • Най-лош случай O(N^2) + O(M*N), квадратична сложност.

Вашият 2-ри алгоритъм:

стъпка 1: Копирайте елементи от L1 в set S, е с времева сложност:

  • Среден случай O(N) * O(log(N)).

  • Най-лошият случай O(N) * O(log(N)).

стъпка 2: Преминете през елементите на L2 и за всеки елемент проверете дали съществува в S.

  • Среден случай O(M) * O(log(N)).

  • Най-лошият случай O(M) * O(log(N)).

Като цяло:

  • Среден случай O(M) * O(log(N)) + O(N) * O(log(N)), линейна логаритмична сложност.

  • Най-лош случай O(M) * O(log(N)) + O(N) * O(log(N)), линейна логаритмична сложност.

Резултати:

Асимптотично първият алгоритъм печели в средния случай. Губи в най-лошия случай по 2-ри алгоритъм.

коментари:

  1. Предложеният алгоритъм с използване на unordered_set асимптотично е същият по времева сложност с първия алгоритъм. На практика е по-добре и по-бързо, защото нямате излишъка от булеви стойности.
  2. На практика има повече от теоретична сложност поради факта на кеш паметта. Изглежда, че структурите от данни с непрекъснато съхранение на елементи в паметта постигат по-добра производителност от други с фрагментирано съхранение на елементи в паметта. Хърб Сътър обяснява добре този ефект в тази видеолекция.
  3. Всичко изброено на практика е фокус покус. Винаги трябва да профилирате своя код, за да определите кой алгоритъм е по-бърз на практика. Ерик Брумер обяснява това добре в тази видеолекция.
person 101010    schedule 12.06.2014
comment
Благодаря 40две. Това е дълъг начин да се каже ред n срещу ред n, лог n. Вече знаех това. ;) - person selbie; 13.06.2014

arrow_upward
0
arrow_downward

set‹> и map‹> обикновено се изпълняват с дървовидна структура от данни, като по този начин изискват O(lg n) време за изпълнение за вмъкване и търсене.

unordered_set‹> и unordered_map‹> обикновено се изпълняват със структура на хеш таблица, като по този начин се получава O(1) производителност за вмъкване и търсене.

Предстои да се определи - не съм сигурен защо set‹> и map‹> могат да бъдат реализирани като комбинация от хеш таблица и двойно свързан списък. Където всеки елемент в хеш-таблицата капсулира както стойността, така и указателите към предишните/следващите възли, които са били вмъкнати. Това ще бъде въпрос за друг ден.

person selbie    schedule 18.06.2014