Альтернативная структура данных для многомерного массива - PullRequest
Новая
       24

Альтернативная структура данных для многомерного массива

1 голос
/ 12 мая 2011

У меня быстрый вопрос, я работаю над проектом, для которого требуется объект, имеющий идентификатор и координаты x, y. Все это сохраняется в объекте, и идея заключается в том, что он помещается в 2D-массив. Однако существует возможность создания и хранения большого количества объектов, а также размера массива. Есть ли что-то более эффективное по размеру и скорости хранения данных? Я читал об использовании карты, это может быть моим лучшим вариантом.

Ответы [ 2 ]

5 голосов
/ 12 мая 2011

Ответ зависит от того, каков основной шаблон доступа вашего приложения.

Если основной шаблон доступа ищет объект по определенной координате x, y, то вам, вероятно, лучше всего подойдет одно из следующего:

  • 2D-массив (как у вас сейчас);то есть Thing[][],
  • a Map<Point, Thing>, или
  • a Map<Integer, Map<Integer, Thing>>.

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

Если массив 2Dмалонаселенный, то подходы на карте сэкономят место за счет времени.Если массив плотно заполнен, то подходы Map могут использовать больше пробелов, чем 2D-массив.

Если основной шаблон доступа предназначен для поиска объектов вблизи заданной координаты x, y(или в регионе), то вам, вероятно, понадобится что-то вроде структуры данных с четырьмя деревьями.

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

2 голосов
/ 12 мая 2011 
Map<Double, java.awt.Point>

Будет работать java.awt.Point, или вы можете создать свой собственный тип данных для хранения координат x, y.

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

Другая альтернатива - это то, что объединяет три вещи (ID, x, y) и сохраняет их в массиве, а затем использует Arrays.binarySearch , чтобы добраться до них.Для этого потребуется отсортировать массив.

Редактировать:

Если вы хотите отобразить x, y на двойное, вы должны сделать: 

Map<java.awt.Point, Double>
...