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

Question

Фактический вопрос заключается в следующем: Какую структуру данных вы будете использовать, чтобы найти бесплатные парковочные места в гараже с миллионами мест?

Что я думал:

• Я мог бы использовать LinkedHashMap и продолжать перемещать свободные места в начало очереди, но я не думаю, что это правильное решение.

Есть мысли?

Answer 1

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

boolean slots[] = new boolean[1000000];

Если вам нужно хранить больше информации, например, информацию об автомобилев слоте, расстояние от слота до ближайшего входа и т. д., затем используйте:

 Slot[] slots = new Slot[1000000];

и класс слота будет похож на

public class Slot{
    Car car;//object for car in slot
    boolean occupied;//whether slot is vacant: may be redundant
    Cost cost;//a set of fields: distance from entrance; parking fee for "good" slots, etc.
}

И так вы продолжаете ...

Answer 2

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

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

Answer 3

Мы можем использовать Очередь.

Очередь содержит все миллионы записей в начале.Если парковочное место необходимо , dequeue .Если место для парковки становится бесплатным , enque .

Answer 4

Улучшая решение Касавбере, я бы предложил использовать BitSet / BitArray , если есть возможность.BitSet использует массивы long, каждое значение long представляет 64 слота.Это эффективно уменьшает общий размер массива в 8 раз по сравнению с логическими значениями [Массивы логических значений обычно занимают 1 байт на элемент] .BitSet также предоставляет методы для получения следующего набора или свободного слота из определенного индекса, поэтому вам не нужно писать собственный метод для этого.

Answer 5

Я бы использовал набор битов, где каждый бит представляет собой место для парковки. Значение 1 бесплатно и 0 используется. Линейный поиск свободных мест должен сделать эту работу. Очень легко внедрить и достаточно быстро с asm.

Answer 6

PriorityQueue, где приоритет определяется как расстояние между местом для парковки и въездом.