комплектация без замены в яве - PullRequest
Новая
       32

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

4 голосов
/ 01 июля 2011

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

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

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

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

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

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

Ответы [ 4 ]

2 голосов
/ 01 июля 2011

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];
1 голос
/ 01 июля 2011

Хорошо, тот же ответ, что и 0verbose с простым исправлением, чтобы получить 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, надеюсь, это поможет

1 голос
/ 01 июля 2011

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

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

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

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

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

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

    Да,добавьте элемент в конец этого списка с помощью add().

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

    Нет, похоже, что O (n).

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

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

1 голос
/ 01 июля 2011

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

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

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

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

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

...