Случайный элемент в наборе STL / карта в журнале n - PullRequest
7 голосов
/ 07 июля 2011

Поскольку C ++ STL set / map реализованы в виде красно-черных деревьев, должна быть возможность выполнять не только insert, delete и find за O (log n) время, но также getMin, getMax, getRandom.Как я понимаю, первые два имеют свои эквиваленты в begin() и end() (это правильно?).Как насчет последнего?Как я могу это сделать?

Единственная идея, которую я до сих пор имел, состояла в том, чтобы использовать advance со случайным аргументом, который, однако, занимает линейное время ...

РЕДАКТИРОВАТЬ:см. равномерное распределение

Ответы [ 6 ]

8 голосов
/ 07 июля 2011

begin() эквивалентно операции getMin, но end() возвращает итератор на единицу после максимума, поэтому будет rbegin().

Что касается getRandom: при условии, что выЯ имею в виду получение любого элемента случайным образом с равномерной вероятностью, что может быть возможно за O (LG N ) времени в дереве AVL, но я не вижу, как это сделать эффективно в красно-черном дереве.Как вы узнаете, сколько поддеревьев есть слева и справа от данного узла, не считая их за n / 2 = O ( n ) времени?И поскольку std::set и std::map не дают прямого доступа к их основному дереву, как вы собираетесь его пройти?

Я вижу три возможных решения:

  • useвместо этого AVL-дерево;
  • поддерживает vector с элементами в map или set параллельно ему;
  • использует Boost :: MultiIndex контейнер с сортированным и произвольным доступом.

Edit : Boost.Intrusive также может помочь.

0 голосов
/ 10 ноября 2015

с существующим STL, вероятно, нет пути. Но есть способ получить случайный ключ в O (1) с добавлением std :: map и std :: vector, используя обратную индексацию.

  1. Ведение карты m & vector v.
  2. при вставке нового ключа k, пусть i = v.length (), затем вставьте в m и вставьте k в v так, чтобы v [i] = k;
  3. при удалении ключа k пусть i = m [k], поиск последнего элемента k2 в v, установка m [k2] = i & v [i] = k2, pop_back v и удаление k из m;
  4. чтобы получить случайный ключ, пусть r = rand ()% v.length (), затем случайный ключ k = v [r];

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

0 голосов
/ 29 августа 2012

Я думаю, что на самом деле вы можете сделать это с STL, но это немного сложнее.

Вам нужно поддерживать карту.Каждый с ключом от 1..N (N - количество элементов).

Таким образом, каждый раз, когда вам нужно взять случайный элемент, генерируйте случайное число из 1..N, затем найдите элемент на картес выбранным ключом.Это элемент, который вы выбираете.

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

Поскольку каждый шаг является log(n) операцией, общее время составляет log(n).

0 голосов
/ 07 июля 2011

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

Если вставки и удаления встречаются редко, вы можете использовать вектор и сортировать его по мере необходимости. Заполнение вектора и его сортировка занимает примерно столько же времени, сколько заполнение набора или карты; это может быть даже быстрее, вам нужно проверить это, чтобы быть уверенным. Выбор случайного элемента в этой точке будет тривиальным.

0 голосов
/ 07 июля 2011

Как вы подозреваете, begin() и end() - 1 или rbegin() получат минимальное и максимальное значения. Хотя я не вижу способа получить случайный элемент в таком дереве. Однако у вас есть пара вариантов:

  • Вы можете сделать это за линейное время, используя аванс.
  • Вы можете сохранить отдельный вектор итераторов карты, который вы будете обновлять во всех вставках / удалениях.
  • Вы можете вернуться к выбору контейнера. Например, будет ли лучше отсортированный вектор, куча или другое представление?
0 голосов
/ 07 июля 2011

Да, начало и rbegin (не конец!) Являются минимальным и максимальным значением ключа соответственно.

Если ваш ключ прост, например, целое число, вы можете просто создать случайное целое число в диапазоне [min, max) (используя) и получить для этого lower_bound карты.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...