Перейти к содержимому
  • 0
Appo

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

Вопрос

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Рекомендуемые сообщения

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

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

 

Например:

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) в метатаблицу матрицы.
И т.п.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Предположим, нужен массив [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. Изменено пользователем eu_tomat

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
... matrix[DEPTH * WIDTH * y + WIDTH * z + x] ...

 

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

 

 

Изменено пользователем Totoro
цитатки сокращаем

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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 ?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Не уверен, что я понял вопрос. Это решение обратно преобразованию 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, и задача решена.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

 

 

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.." секунд")
 

 

 

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

rkEIhkx.png

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

 

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

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

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

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

TNORP9O.png

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

 

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

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

 

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

А теперь попробуем адаптировать подход, который часто применяется в ассемблере: разделим 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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

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

Изменено пользователем Doob

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

Изменено пользователем NEO

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

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

Гость
Ответить на вопрос...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...