Массив объектов или массив «массивов»?

Question

[kunjut19]

Если представить, что я пишу игру с клеточной картой (что-то типа Цивилизации или Героев), какой способ хранения информации о клетках был бы предпочтительней с точки зрения быстродействия?
Клеток много (допустим, 100.000), и в каждой клетке хранится куча информации - какому игроку принадлежит клетка, тип ландшафта, ресурсы, занята ли юнитом, сведения о соседних клетках (если рядом морская клетка - то можно строить порт). Игрок захватывает замок, и теперь нужно пробежаться по большому количеству клеток вокруг замка и поменять в них принадлежность тому или иному игроку.
Это только модель, чтобы было легче понять, что именно я имею ввиду. С точки зрения такой модели, с чем быстрее происходит работа - с двумерным массивом объектов или с трехмерным массивом строк и чисел? Если пренебречь тем, что удобнее будет понять запись map[463][537].type='grass', чем map[463][537][31]='grass', то что будет лучшим выбором?
Не знаю, будет ли разница в зависимости от языка, поэтому не ориентирую вопрос на конкретный язык.

Comments

[Тимур Покровский]

так а какой язык? например в c++ нельзя хранить в массиве и строки и числа

[Александр Ананьев]

Тимур Покровский, можно сделать массив типов variant.

[twoone]

Прежде всего нужно разделять абстракции иначе буджет невозможно контролировать сложность. Прежде всего игровое поле. Оно должно быть представлено произвольным графом каждый из которых хранит ссылку на своих соседей (связан 4 или 8 клеток) . Кроме того граф имеет поле data которое ассоциированно с данными о ячейке. Уровнем выше идет игровой мир, то есть его карта. Карта поделена на области и контексты предметной области (города\моря\т.д.) и представляются сервисными классами которые работают непосредственно с графами. То есть вы напрямую с графами не работаете вы через сервесные классы ищите, менеяете значения и т.д. Это уже они внутри себя создают кеши по индексу или ключу или чаще всего и тому и другому.

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

Answer 1

[Сергей Чамкин]

Произвел сейчас простейший замер. Разница не велика +-15%.
Выигрывает двумерный массив объектов.
(производил замер на java)

Comments

[kunjut19]

а каков был размер массивов?

[Сергей Чамкин]

kunjut19, 3000 * 3000 с двумя полями

Answer 2

[Тимур Покровский]

код c#:

using System;
using System.Diagnostics;

namespace ConsoleApp19 {
	class Program {
		struct Cell {
			public string type;
			public string player;
			public bool isUnit;
		}

		public static void Main() {
			const int size = 1_000;

			object[,,] objs = new object[size, size, 3];
			Cell[,] cells = new Cell[size, size];

			Stopwatch timer = new Stopwatch();
			timer.Start();
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					objs[i, j, 0] = "type";
					objs[i, j, 1] = "player";
					objs[i, j, 2] = false;

					string type = (string)objs[i, j, 0];
					string player = (string)objs[i, j, 1];
					bool isUnit = (bool)objs[i, j, 2];
				}
			}
			timer.Stop();
			Console.WriteLine(timer.ElapsedMilliseconds);

			timer.Reset();
			timer.Start();
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					cells[i, j].type = "type";
					cells[i, j].player = "player";
					cells[i, j].isUnit = false;

					string type = cells[i, j].type;
					string player = cells[i, j].player;
					bool isUnit = cells[i, j].isUnit;
				}
			}
			timer.Stop();
			Console.WriteLine(timer.ElapsedMilliseconds);
		}
	}
}

Вывод:
89 (3-ёх мерный массив)
18 (2-ух мерный)

Comments

[edward_freedom]

если включить оптимизацию кода, можно сократить время в двое

Answer 3

[Griboks]

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

Comments

[kunjut19]

спасибо, попытаюсь найти :) но ответы пользователей говорят об обратном

[Griboks]

kunjut19, кроме того, намного быстрее использовать множество одномерных массивов. Например, вместо map[463][537].type='grass' писать types[123456]='grass'.