Поиск первого бесплатного индекса

Question

У меня есть большой массив/список из 1 миллиона идентификаторов, а затем мне нужно найти первый бесплатный идентификатор, который можно использовать. Можно предположить, что существуют пара модулей, которые относятся к этой структуре данных и принимают идентификатор (в течение которого он должен быть помечен как использованный), а затем возвращать его позже (должен быть отмечен как свободный). Я хочу знать, какие различные структуры данных можно использовать? и какой алгоритм я могу использовать для эффективного использования времени и пространства (отдельно). Пожалуйста, извините, если он уже присутствовал здесь, я выполнил поиск перед публикацией.

Answer 1

Наивным, но эффективным методом было бы хранить все ваши идентификаторы в стеке. Получение идентификатора - операция с постоянным временем: поп первый элемент списка. Когда задача завершена, просто нажмите идентификатор в стеке.

Если минимальный бесплатный идентификатор должен быть возвращен (а не какой-либо свободный идентификатор), вы можете использовать кучу минут с вставкой и поп-позицию в O (log N).

Answer 2

Ну, массив, вероятно, не лучшая структура. Хеш был бы лучше, по крайней мере, по скорости. Что касается структуры для каждого «узла», все, что я вижу, что вам нужно, это всего лишь идентификатор, и он используется, или нет.

Answer 3

Одна из исходных идей, которая могла бы работать, заключалась в том, чтобы сохранить очередь приоритетов для всех неиспользуемых идентификаторов, отсортированную так, чтобы низкие идентификаторы были вычеркнуты перед высокими идентификаторами. Используя стандартную двоичную кучу, это позволит вернуть идентификатор в неиспользуемый пул идентификаторов в O (log n) и найти следующий свободный идентификатор в O (log n). Это имеет тот недостаток, что для этого требуется явно хранить все идентификаторы, которые могут быть неэффективными в пространстве, если существует огромное количество идентификаторов.

Одной из возможных задач экономии пространства было бы попытаться объединить последовательные идентификационные значения в диапазоны идентификаторов. Например, если у вас есть бесплатные идентификаторы 1, 3, 4, 5, 6, 8, 9, 10 и 12, вы можете просто сохранить диапазоны 1, 3-6, 8-10 и 12. Это потребует от вас немного изменить базовую структуру данных. Вместо использования двоичной кучи можно использовать сбалансированное двоичное дерево поиска, в котором хранятся диапазоны. Поскольку эти диапазоны не будут перекрываться, вы можете сравнить диапазоны как меньше, равно или больше других диапазонов. Поскольку BST хранятся в отсортированном порядке, вы можете найти первый бесплатный идентификатор, взяв минимальный элемент дерева (в O (log n)) и глядя на нижний конец своего диапазона. Затем вы обновите диапазон, чтобы исключить этот первый элемент, который может потребовать удаления пустого диапазона из дерева. При возврате идентификатора в пул неиспользуемых идентификаторов вы можете выполнить поиск предшественника и преемника, чтобы определить диапазоны, которые поступают непосредственно перед и после ID. Если один из них может быть расширен, чтобы включить этот идентификатор, вы можете просто расширить диапазон. (Возможно, вам потребуется объединить два диапазона). Это также занимает только время O (log n).

Надеюсь, это поможет!

Answer 4

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

Answer 5

Преамбула: бинарная куча кажется лучшим ответом. Я приведу здесь альтернативу, которая может иметь преимущества в некоторых сценариях.

Один из возможных способов - использовать Fenwick Tree. Вы можете хранить в каждой позиции либо 0, либо 1, указывая, что позиция уже использовалась или нет. И вы можете найти первую пустую позицию с бинарным поиском (чтобы найти первый диапазон [1..n], который имеет сумму n-1).Сложность этой операции O (журнал^2 п), что хуже, чем в двоичной куче, но этот подход имеет еще преимущества:

• Вы можете реализовать Фенвик дерево менее чем 10 строк кода
• Теперь можно рассчитать плотность (количество используемых/всего идентификаторов) в диапазоне в O (журнал N)

Answer 6

Если вы не строго нужен низкий идентификатор, вы можете выделить идентификаторы для модулей в партиях по 1000. При освобождении идентификаторов их можно добавить в конец списка. И время от времени вы сортируете список, чтобы снова убедиться, что идентификаторы, которые вы назначили, находятся на нижнем конце.