Комплектация без замены в яве

Я часто * нуждаюсь в структуре данных, которая имеет следующие свойства:

  • может быть инициализирован массивом из n объектов в O(n).
  • в O(1) можно получить случайный элемент, после которого выбранный элемент удаляется из структуры. (без замены)
  • в O(p) можно отменить p операций "выбор без замены"
  • можно удалить конкретный объект (например, по id) из структуры в O(log (n))
  • в O(n) можно получить массив объектов, находящихся в настоящее время в структуре.

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

Кто-нибудь может дать мне руководство по реализации такой структуры? В настоящее время я реализовал структуру, имеющую все вышеперечисленные свойства, за исключением того, что для выбора элемента берется O(d) с числом предыдущих выборок (поскольку я явно проверяю, "еще не выбрано" ли это). Я могу понять структуры, позволяющие выбирать в O(1), но они имеют более высокую сложность по крайней мере в одной из других операций.

Кстати, обратите внимание, что O(1) выше подразумевает, что сложность не зависит от # ранее выбранных элементов и не зависит от общего количества #elements.

* в алгоритмах Монте-Карло (итерационные выборки из p случайных элементов из "набора" из n элементов).

Источник

4 ответа

Решение

Хорошо, тот же ответ, что и Heisenbug, с простым исправлением, чтобы получить O (1) случайный поиск. Создайте массив, в котором хранятся те же n объектов. Теперь в HashMap сохраните пары. Например, скажем, ваши объекты (строки для простоты):

{"abc" , "def", "ghi"}

Создать

List<String> array = ArrayList<String>("abc","def","ghi")

Создайте карту HashMap со следующими значениями:

for (int i = 0; i < array.size(); i++) 
{
    map.put(array[i],i);
}

O (1) случайный поиск легко достигается путем выбора любого индекса в массиве. Единственное осложнение, которое возникает при удалении объекта. Для этого сделайте:

  1. Найти объект в map, Получите его индекс массива. Позволяет назвать этот индекс i (map.get(i)) - O(1)

  2. Поменять местами массив [i] с массивом [размер массива - 1] (последний элемент в массиве). Уменьшить размер массива на 1 (поскольку теперь число на единицу меньше) - O(1)

  3. Обновите индекс нового объекта в позиции i массива в map (map.put(array[i], i)) - O(1)

Я прошу прощения за сочетание нотации java и cpp, надеюсь, это поможет

Источник

HashMap имеет сложность O(1) как для вставки, так и для удаления. Вы указываете много операций, но все они - не что иное, как вставка, удаление и перемещение:

может быть инициализирован массивом из n объектов в O (n).

n * O(1) вставка. HashMap в порядке

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

Это единственная операция, требующая O (n).

в O (p) можно отменить p операций "выбор без замены"

это операция вставки: O(1).

можно удалить конкретный объект (например, по id) из структуры в O (log (n))

O(1).

в O (n) можно получить массив объектов, находящихся в настоящее время в структуре.

вы можете пересечь HashMap в O (N)

РЕДАКТИРОВАТЬ: пример выбора случайного элемента в O (n):

HashMap map ....
int randomIntFromZeroToYouHashMapSize = ...
Collection collection = map.values();
Object[] values = collection.toArray();
values[randomIntFromZeroToYouHashMapSize];
Источник

Как насчет массива (или ArrayList) что поделено на "выбрано" и "не выбрано"? Вы отслеживаете, где находится граница, и, чтобы выбрать, вы генерируете случайный индекс ниже границы, затем (так как вам не важен порядок), меняете элемент по этому индексу на последний не выбранный элемент и уменьшаете границу., Чтобы снять выделение, вы просто увеличиваете границу.

Обновление: Забыл про удаление O(log(n)). Не так сложно, хотя, просто немного дороже памяти, если вы держите HashMap идентификаторов к индексам.

Если вы ковыряетесь на линии, вы найдете различные IndexedHashSet реализации, которые все работают более или менее по этому принципу - массив или ArrayList плюс HashMap,

(Хотелось бы увидеть более элегантное решение, если таковое существует.)

Обновление 2: Хм... или фактическое удаление снова становится O(n), если вам нужно либо переписать массивы, либо переместить их?

Источник

Вот мой анализ использования Collections.shuffle() на ArrayList:

  • ✔ может быть инициализирован массивом из n объектов в O(n).

    Да, хотя стоимость амортизируется, если n не известно заранее.

  • Obtain можно получить случайный элемент в O (1), после этой операции выбранный элемент удаляется из структуры без замены.

    Да, выберите последний элемент в перемешанном массиве; заменить массив на subList() из оставшихся элементов.

  • P в O (p) можно отменить p операций "выбор без замены".

    Да, добавить элемент в конец этого списка через add(),

  • Remove можно удалить определенный объект (например, по идентификатору) из структуры в O (log (n)).

    Нет, это выглядит как O(n).

  • Can можно получить массив объектов, находящихся в данный момент в структуре, в O(n).

    Да, используя toArray() выглядит разумно.

Источник
Другие вопросы по тегам