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

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

То, что я подумал:

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

Любые мысли?

источник

2012-03-29 noMAD

Вы заботитесь о том, чтобы найти ближайшее место или все «свободные места для парковки»? Является ли гараж многоуровневым? Как бы вы определили стоимость перехода на следующий уровень по сравнению с дальнейшим продвижением на этом уровне? Это все вопросы, которые вы могли бы задать, думая о решении. – Seph

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

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

источник

2012-03-29 04:36:35 iehrlich

'LinkedHashMap' использует очередь приоритетов. Но вы не можете хранить миллионы узлов в очереди. По крайней мере, это то, что я думаю. – noMAD

И почему вы так думаете? – iehrlich

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

источник

2012-03-29 07:15:32 knivil

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

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. 
}

и поэтому вы продолжайте идти ...

источник

2012-03-29 14:06:19 kasavbere

Улучшение решения kasavbere, я бы предложил использовать класс BitSet/BitArray, если у вас есть опция. BitSet использует массивы longs с каждым длинным значением, представляющим 64 слота. Это эффективно уменьшает общий размер массива в 8 раз по сравнению с булевыми [Arrays of booleans typically occupy 1 byte per element]. BitSet также предоставляет методы для получения следующего набора или свободного слота из определенного индекса, поэтому вам не нужно писать свой собственный метод для этого.

источник

2012-03-30 19:18:58 Faisal

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

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

источник

2012-03-31 20:17:06 Sandeep

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

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

источник

2014-04-01 03:01:57 user2100441

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

ответ

Смежные вопросы