Создание многомерных массивов

[Appo 86]

local h = {}

function add(x,y,z,f) 
	h[x] = h[x] or {} 
	h[x][y] = h[x][y] or {} 
	h[x][y][z] = f
end

add(1,2,3,"xxx")
print( h[1][2][3] ) --> xxx

Есть ли способ делать то же самое, но по короче?

И как можно написать эту функцию для добавления значений в разные массивы? (с использованием ооп и без)

[Totoro 3 563]

Ты можешь использовать вместо многомерного массива - одномерный, перемножая индексы.

Это будет даже экономичнее в плане памяти.

 

Например:

local matrix = {}
local WIDTH, HEIGHT, DEPTH = 10, 10, 10

local function set(x, y, z, value)
  matrix[DEPTH * WIDTH * y + WIDTH * z + x] = value
end
local function get(x, y, z)
  return matrix[DEPTH * WIDTH * y + WIDTH * z + x]
end

set(1,2,3, "HOTTO DOGU")
print(get(1,2,3))

Нумерация индексов при такой системе идёт с нуля.

Можно добавить проверки на выход за пределы массива.

Можно засунуть дополнительную инфу (высота, ширина, глубина, методы get/set) в метатаблицу матрицы.
И т.п.

[eu_tomat 2 154]

Предположим, нужен массив [x,y,z] размером 80x64x20

Зная частные индексы и размеры массива нужно получить общий индекс.

 

Выбираем любой из индексов. Пусть это будет x.

Изменение x на единицу будет приводить к изменению общего индекса на единицу.

x ограничен 80 значениями. Значит, последующие индексы надо будет умножить на 80

 

Теперь выбираем следующий индекс. Пусть это будет y.

Изменение y на единицу будет приводить к изменению общего индекса на 80, как мы поняли выше.

y ограничен 64 значениями. Значит, последующие индексы надо будет умножить на 64. И не забываем об умножении на 80. То есть, на 80*64.

 

Теперь остался индекс z.

Исходя из предыдущих рассуждений, изменение z на единицу будет приводить к изменению общего индекса на 80*64.

z ограничен 20 значениями. Значит, последующие индексы надо будет умножить на 20. И не забываем об умножении на 80*64. То есть, на 80*64*20.

Но других индексов после z не наблюдается, поэтому не забиваем себе голову.

 

Итоговая формула: idx = x + y*80 + z*80*64

 

При выборе другого порядка индексов формула может отличаться. Следует придерживаться выбранной схемы.

 

Для получения частных индексов из общего индекса используется обратная схема:

i=idx
x=i%80 i=(i-x)/80
y=i%64 i=(i-y)/64
z=i

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

 

Пример

> X,Y,Z = 80,64,20
> x,y,z = 37,21,11
> idx = x + y*X + z*X*Y
> =idx
58037
> i=idx
> x=i%80 i=(i-x)/80
> y=i%64 i=(i-y)/64
> z=i
> =x,y,z
37      21      11

И надо помнить, что индексы в этой схеме нумеруются от нуля в отичие от принятого в Lua. Изменено 26 октября, 2017 пользователем eu_tomat

[ivan52945 75]

... matrix[DEPTH * WIDTH * y + WIDTH * z + x] ...

 

тока DEPTH * WIDTH сразу перемножь и запихни в какую нить переменную, чтоб не перемножать по 100500 раз

 

 

Изменено 15 октября, 2017 пользователем Totoro
цитатки сокращаем

[Appo Автор вопроса 86]

Если мне нужно будет перебрать массив, как мне вытащить координаты из номера ячейки массива?

я придумал иной способ
 

local function r(xx,yy,zz) return zz+yy*256+xx*65536 end -- Получаем 16-ричный код из координат для использования одномерного массива с целью экономии памяти
 
local function toXYZ(id) -- Получаем координаты из 16-го кода
	local f, g = ("%X"):format(id), "0x"
	f = string.rep("0",6-#f)..f
	return tonumber(g..f:sub(1,2)), tonumber(g..f:sub(3,4)), tonumber(g..f:sub(5,6))
end
 
local h = {}
 
h[r(1,2,3)] = "XXX" -- координаты x = 1, y = 2, z = 3
 
print( h[66051] ) -- Выведет: "XXX"
 
print( toXYZ(66051) ) -- Выведет 1,2,3

Но он не совсем подходит, так как большой размер, а именно = 256*256*256 . в следствии чего, ячейки массива занимают много места в файле.

Как сократить размер до 80x64x80 ?

[Appo Автор вопроса 86]

@@eu_tomat , как ты пришел к такому решению?
 

i=idx
x=i%80 i=(i-x)/80
y=i%64 i=(i-y)/64
z=i

[Doob 2 749]

Не стоит сильно экономить память в опенкомпах, т. к. ее очень много, а процессор крайне медленный.

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

Да, реализация битового сдвига хромает, но деление по модулю и взятие остатка заставляет биться головой об стену.

[eu_tomat 2 154]

как ты пришел к такому решению?

Не уверен, что я понял вопрос. Это решение обратно преобразованию idx = x + y*80 + z*80*64, оно изначально задумывлось таким образом, чтобы получить однозначное соответствие частных индексов и общего.

 

Попробуем для начала излечь x. Нам известно, что значение x находится в диапазоне [0..79], а idx равен сумме x и еще какого-то числа, кратного 80.

Логично, что для получения x достаточно взять остаток от деления idx%80.

Далее i получает значение целочисленного деления i//80

Теперь i = y + z*64

 

Теперь извлекаем y, зная, что значение y находится в диапазоне [0..63], а i равен сумме y и еще какого-то числа, кратного 64.

Значение y будет равно остатку от деления i%64,

а i получает значение целочисленного деления i//64

Теперь i = z

 

Осталось присвоить z = i, и задача решена.

[eu_tomat 2 154]

Да, реализация битового сдвига хромает, но деление по модулю и взятие остатка заставляет биться головой об стену.

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

[Zer0Galaxy 2 187]

Сравнение скорости обращения к элементам обычного трехмерного массива и линейного массива, построенного по предлагаемой схеме

 

 

uptime=require("computer").uptime
--Создадим два трехмерных массива, один обычный вида M[x][y][z]
--другой линейный, в котором общий индекс будет вычисляться по формуле вида id=x+y*80+z*80*64
--Функция для вычисления общего индекса
--Частные индексы x,y,z могут изменяться в диапазонах 1-XX, 1-YY, 1-ZZ соответственно
--Общий индекс изменяется в диапазоне 1 - XX*YY*ZZ
function id(x,y,z) return x+XX*(y-1)+XX*YY*(z-1) end

--Изначально массивы будут заполнены нулями, чтобы создание элементов массивов не повлияло на результат
--Затем  заменим все элементы каждого массива на другие числа
--Размерность массивов
XX, YY, ZZ=80, 64, 20
--количество повторов
N=100

--Обычный трехмерный массив
Arr1={}
for i=1,XX do
  Arr1[i]={}
  for j=1,YY do
    Arr1[i][j]={}
	  for k=1,ZZ do
	    Arr1[i][j][k]=0
	  end
  end
end

--Линейный массив
Arr2={}
for i=1,XX do
  for j=1,YY do
    for k=1,ZZ do
	  Arr2[id(i,j,k)]=0
	end
  end
end

--Произведем измерение времени, необходимого для изменения всех элементов массива
--Для повышения точности замера изменение проведем N раз
start=uptime()
for m=1,N do
 for i=1,XX do
  for j=1,YY do
	  for k=1,ZZ do
	    Arr1[i][j][k]=m
	  end
  end
 end
end
print("Обычный массив "..uptime()-start.." секунд")

start=uptime()
for m=1,N do
 for i=1,XX do
  for j=1,YY do
    for k=1,ZZ do
	  Arr2[id(i,j,k)]=m
	end
  end
 end
end
print("Линейный массив "..uptime()-start.." секунд")
 

 

 

Вот результат, если кому интересно

Как видим, использование обычного массива в три раза эффективнее с точки зрения процессорного времени.

 

Может быть всё дело в том, что для вычисления индекса линейного массива вызывается функция?

Попробуем обойтись без функции.

	  Arr2[i+XX*(j-1)+XX*YY*(k-1)]=m

хотя я так бы делать не стал, поскольку читабельность падает на порядок

Немного лучше, но выводы делайте сами.

 

PS: Если при вычислении индекса избавиться от лишнего умножения и вычитания единицы (Arr2[i+XX*j+XY*k]=m, где XY=XX*YY, при этом частные индексы изменяются от нуля), получим результат еще лучше - 0.89 секунд.

PS PS: Пост написан под впечатлением вот этого заявления:

 

 

Не стоит сильно экономить память в опенкомпах, т. к. ее очень много, а процессор крайне медленный.

Изменено 27 октября, 2017 пользователем Zer0Galaxy

[Doob 2 749]

Неплохо, но где обратная операция? Она ведь во многих случаях вызывается чаще и жрет больше времени.

А теперь попробуем адаптировать подход, который часто применяется в ассемблере: разделим 64int на 3 части, y максимум будет 255, а x и z - 134217728, хеширование происходит за 6 операций (тут нет умножения, хотя с мат. сопроцессором это не играет роли).

local function hash(x, y, z)
  x, z = x+134217728, z+134217728
  return y|(x<<8)|(z<<36)
end 

Если бы не требовалось при поиске пути каждый раз получать исходное число, скорость была бы не намного выше, чем при использовании многомерных массивов.

Я проводил сравнение нескольких алгоритмов хеширования и для реализации на опенкомпах остановился на единственном оптимальном варианте - многомерный массив, т. к. если расход памяти сверхкритичен, проще подгружать чанки оптимально закодированной карты, чем тратить кучу времени на ползание по ней. Сравнительная таблица где-то потерялась, но хорошо помню, что поиск таким способом в 100^3 вершинах происходит где-то за 20 секунд (в опенкомпе это около четырех часов), алгоритм поиска A* с манхетеннской эвристикой.

 

Вот, кстати, тестовый код: https://pastebin.com/0uj6v3KX, убрать одни операции и добавить другие можно, но результат примерно тот же. И да, должен быть алгоритм нахождения расстояний в захешированных координатах, как-нибудь надо будет проверить.

[ivan52945 75]

а битовые сдвиги типа хреновые?(хотя умножение всё равно лучче не юзать)

Изменено 27 октября, 2017 пользователем ivan52945

[Doob 2 749]

Не все так просто. Lua написан на си и написан чисто.

https://github.com/lua/lua/blob/master/lmathlib.c

https://github.com/lua/lua/blob/master/lbitlib.c

Тут не к чему придраться. Си тоже неплохо отполирован, хотя и остаётся языком костылей. Тут надо разобраться с виртуальным процессором, т. к. реальный процессор работает сверх-очевидно и оптимально написанные программы работают как и должны.

Изменено 28 октября, 2017 пользователем Doob

[NEO 542]

хотя и остаётся языком костылей. 

Каких еще костылей?

Всё прекрасно. Хотя есть макросы глуповатые.

Изменено 28 октября, 2017 пользователем NEO