Я люблю Lua. I love Lua.

Заполнение таблиц данными

Posted in Uncategorized by ilovelua on Январь 20, 2016

Нередко встает задача заполнить таблицу данными.
Допустим, нам нужно создать список параметров.
Каждый параметр — это таблица вида:

{
name = 'Name',
value = '',
type = 'string',
}

Соответственно, список параметров будет выглядеть как-то так:

{
	{
		name = 'Name',
		value = '',
		type = 'string',
	},
	{
		name = 'Order',
		value = 1,
		type = 'number',
	},
	{
		name = 'File',
		value = 'default.lua',
		type = 'string',
	},
}

Если параметров много, то для удобства заполнения я создаю функцию:

local function createParameter(name, value, type)
	return {
		name	= name,
		value	= value,
		type	= type,
	}
end

Список параметров начинает выглядеть так:

{
    createParameter('Name',     '',             'string'),
    createParameter('Order',    1,              'number'),
    createParameter('File',     'default.lua',  'string'),
}

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

local function Property(name)
    return {
        name    = name,
        
        Value = function(self, value)
            self.value = value
            
            return self
        end,
        
        Type = function(self, type)
            self.type = type
            
            return self
        end,
    }
end

Теперь заполнение таблицы параметров выглядит так:

{
    Property('Name')    :Value('')              :Type('string'),
    Property('Order')   :Value(1)               :Type('number'),
    Property('File')    :Value('default.lua')   :Type('string'),
}

Теперь каждый параметр подписан, а если есть опциональные поля, то их можно пропустить, а не писать такое:

createParameter('Name', '', nil, nil, nil, 'string'),

 

PS
Не помню, сам я это придумал, или где-то украл 🙂

Реклама
Tagged with: , ,

Поиск позиции для вставки элемента в отсортированный массив

Posted in Uncategorized by ilovelua on Июль 22, 2013

Eng: how to find proper position to insert value into ordered array.
Upd: Вот здесь все есть http://lua-users.org/wiki/OrderedAssociativeTable см функцию table.binsert(). Она, кстати, и быстрее моей.
Тут на работе понадобилось решить такую задачу. Сначала сделал все по простому:

function findPositionInSortedArraySlow(value, array)
	for i, arrayValue in ipairs(array) do
		if value <= arrayValue then
			return i
		end
	end

	return #array + 1
end

Оно, конечно, работает, но неаккуратненько как-то… Сразу в голову полезли мысли о быстрой сортировке вставками. Поскольку массив отсортированный, то позицию можно быстро найти, каждый раз разделяя массив пополам и проверяя нужную половину. В результате получилось это:

function findPositionInSortedArrayFast(value, array)
	local beginIndex = 1
	local endIndex = #array
	local floorFunc = math.floor

	if 0 ~= endIndex then
		local middleIndex

		while true do		
			if value <= array[beginIndex] then
				return beginIndex
			end

			if value >= array[endIndex] then
				return endIndex + 1
			end

			middleIndex = beginIndex + floorFunc((endIndex - beginIndex) / 2)

			if value < array[middleIndex] then
				endIndex = middleIndex
			else
				beginIndex = middleIndex + 1
			end
		end
	end

	return beginIndex
end

Тесты для проверки правильности. Обратите внимание, что в некоторых случаях результаты работы алгоритмов не совпадают. Это происходит в случаях, когда valuе присутствует в массиве array. Быстрый алгоритм выдает позицию за или перед присутствующим элементом в зависимости от того, четное или нечетное количество элементов в массиве. Медленный алгоритм всегда выдает позицию перед присутствующим элементом. В моем случае это абсолютно не критично.

local array = {}
local value = 1
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 100
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))

array = {100}
value = 1
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 100
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 101
assert(2 == findPositionInSortedArrayFast(value, array))
assert(2 == findPositionInSortedArraySlow(value, array))

array = {100, 200}
value = 1
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 100
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 101
assert(2 == findPositionInSortedArrayFast(value, array))
assert(2 == findPositionInSortedArraySlow(value, array))
value = 200
-- аглоритмы выдают разные(хотя и правильные!) значения
assert(3 == findPositionInSortedArrayFast(value, array))
assert(2 == findPositionInSortedArraySlow(value, array))
value = 201
assert(3 == findPositionInSortedArrayFast(value, array))
assert(3 == findPositionInSortedArraySlow(value, array))

array = {100, 200, 300}
value = 1
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 100
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 101
assert(2 == findPositionInSortedArrayFast(value, array))
assert(2 == findPositionInSortedArraySlow(value, array))
value = 200
-- аглоритмы выдают разные(хотя и правильные!) значения
assert(3 == findPositionInSortedArrayFast(value, array))
assert(2 == findPositionInSortedArraySlow(value, array))
value = 201
assert(3 == findPositionInSortedArrayFast(value, array))
assert(3 == findPositionInSortedArraySlow(value, array))
value = 300
-- аглоритмы выдают разные(хотя и правильные!) значения
assert(4 == findPositionInSortedArrayFast(value, array))
assert(3 == findPositionInSortedArraySlow(value, array))
value = 301
assert(4 == findPositionInSortedArrayFast(value, array))
assert(4 == findPositionInSortedArraySlow(value, array))

array = {100, 200, 300, 400}
value = 1
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 100
assert(1 == findPositionInSortedArrayFast(value, array))
assert(1 == findPositionInSortedArraySlow(value, array))
value = 101
assert(2 == findPositionInSortedArrayFast(value, array))
assert(2 == findPositionInSortedArraySlow(value, array))
value = 200
-- аглоритмы выдают разные(хотя и правильные!) значения
assert(3 == findPositionInSortedArrayFast(value, array))
assert(2 == findPositionInSortedArraySlow(value, array))
value = 201
assert(3 == findPositionInSortedArrayFast(value, array))
assert(3 == findPositionInSortedArraySlow(value, array))
value = 300
assert(3 == findPositionInSortedArrayFast(value, array))
assert(3 == findPositionInSortedArraySlow(value, array))
value = 301
assert(4 == findPositionInSortedArrayFast(value, array))
assert(4 == findPositionInSortedArraySlow(value, array))
value = 400
-- аглоритмы выдают разные(хотя и правильные!) значения
assert(5 == findPositionInSortedArrayFast(value, array))
assert(4 == findPositionInSortedArraySlow(value, array))
value = 401
assert(5 == findPositionInSortedArrayFast(value, array))
assert(5 == findPositionInSortedArraySlow(value, array))

Проверка скорострельности. На массиве размером 100 элементов разницу в скорости методом os.clock() уловить не удалось 🙂
Попробуем на массиве размером в 1000 элементов. Сначала ищем позицию для элемента где-то в начале массива. В этом случае медленный алгоритм будет почти такой же быстрый, как быстрый 🙂

array = {}

for i = 1, 1000 do
	table.insert(array, i)
end

value = 1

local t = os.clock()

for i = 1, 1000 do
	findPositionInSortedArrayFast(value, array)
end

print('~~~fast', os.clock() - t)

t = os.clock()

for i = 1, 1000 do
	findPositionInSortedArraySlow(value, array)
end

print('~~~slow', os.clock() - t)

Результаты таковы:
~~~fast 0
~~~slow 0.0010000000000003

Теперь поищем позицию для элемента в конце массива:

value = 1001

local t = os.clock()

for i = 1, 1000 do
	findPositionInSortedArrayFast(value, array)
end

print('~~~fast', os.clock() - t)

t = os.clock()

for i = 1, 1000 do
	findPositionInSortedArraySlow(value, array)
end

print('~~~slow', os.clock() - t)

Результат:
~~~fast 0
~~~slow 0.122

Ну вот, намного быстрее 🙂

Сравнение таблиц Lua

Posted in Uncategorized by ilovelua on Апрель 1, 2013

Есть две таблицы вида:

[1] = "{6D21ECEA-F85B-4E8D-9D51-31DC9B8AA4EF}",
[3] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
...

и нужно их мне сравнить. Сравнение я сделал двумя циклами:

function areTablesEqual1(table1, table2)
	for k, v in pairs(table1) do
		if table2[k] ~= v then
			return false
		end
	end

	for k, v in pairs(table2) do
		if table1[k] ~= v then
			return false
		end
	end

	return true
end

Проверим:

local table1 = {	
	[1] = "{6D21ECEA-F85B-4E8D-9D51-31DC9B8AA4EF}",
	[3] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[5] = "{69DC8AE7-8F77-427B-B8AA-B19D3F478B66}",
	[7] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[9] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[11] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[13] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[15] = "{DB434044-F5D0-4F1F-9BA9-B73027E18DD3}",
	[17] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[19] = "{69DC8AE7-8F77-427B-B8AA-B19D3F478B66}",
}

local table2 = {	
	[1] = "{6D21ECEA-F85B-4E8D-9D51-31DC9B8AA4EF}",
	[3] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[5] = "{69DC8AE7-8F77-427B-B8AA-B19D3F478B66}",
	[7] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[9] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[11] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[13] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[15] = "{DB434044-F5D0-4F1F-9BA9-B73027E18DD3}",
	[17] = "{BCE4E030-38E9-423E-98ED-24BE3DA87C32}",
	[19] = "{69DC8AE7-8F77-427B-B8AA-B19D3F478B66}",
}
assert(areTablesEqual1(table1, table1))
assert(areTablesEqual1(table1, table2))

И вдруг отчего-то захотелось мне сравнить их внутри одного цикла, а не двух. Для этого на помощь призвал я функцию next():

function areTablesEqual2(table1, table2)
	local result = true

	local key1, value1 = next(table1)
	local key2, value2 = next(table2)

	while key1 and key2 do
		if key1 ~= key2 or value1 ~= value2 then
			result = false
			break
		end

		key1, value1 = next(table1, key1)
		key2, value2 = next(table2, key2)
	end

	if result then
		result = (not key1) and (not key2)
	end

	return result
end

Проверим:

assert(areTablesEqual2(table1, table1))
assert(areTablesEqual2(table1, table2)) -- <-- fail!

Посмотрим, что там происходит внутри:

function areTablesEqual2(table1, table2)
	print('areTablesEqual2 output:')
	local result = true

	local key1, value1 = next(table1)
	local key2, value2 = next(table2)

	print('~~~table1', key1, value1)
	print('~~~table2', key2, value2)

	while key1 and key2 do
		if key1 ~= key2 or value1 ~= value2 then
			result = false
			break
		end

		key1, value1 = next(table1, key1)
		key2, value2 = next(table2, key2)

		print('~~~table1', key1, value1)
		print('~~~table2', key2, value2)
	end

	if result then
		result = (not key1) and (not key2)
	end

	return result
end

Вывод:
areTablesEqual2 output:
~~~table1 13 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 13 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 7 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 7 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 1 {6D21ECEA-F85B-4E8D-9D51-31DC9B8AA4EF}
~~~table2 1 {6D21ECEA-F85B-4E8D-9D51-31DC9B8AA4EF}
~~~table1 15 {DB434044-F5D0-4F1F-9BA9-B73027E18DD3}
~~~table2 15 {DB434044-F5D0-4F1F-9BA9-B73027E18DD3}
~~~table1 9 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 9 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 5 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table2 5 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table1 19 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table2 19 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table1 3 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 3 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 17 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 17 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 11 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 11 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 nil nil
~~~table2 nil nil
areTablesEqual2 output:
~~~table1 13 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 13 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 7 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 7 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 1 {6D21ECEA-F85B-4E8D-9D51-31DC9B8AA4EF}
~~~table2 1 {6D21ECEA-F85B-4E8D-9D51-31DC9B8AA4EF}
~~~table1 15 {DB434044-F5D0-4F1F-9BA9-B73027E18DD3}
~~~table2 15 {DB434044-F5D0-4F1F-9BA9-B73027E18DD3}
~~~table1 9 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table2 9 {BCE4E030-38E9-423E-98ED-24BE3DA87C32}
~~~table1 5 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table2 5 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table1 19 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table2 19 {69DC8AE7-8F77-427B-B8AA-B19D3F478B66}
~~~table1 3 {BCE4E030-38E9-423E-98ED-24BE3DA87C32} <
~~~table2 17 {BCE4E030-38E9-423E-98ED-24BE3DA87C32} <

Ну вот, различный порядок обхода таблиц. Жаль, что не получилось. А идея была неплохая, да…

Удаление данных из таблицы внутри цикла

Posted in Uncategorized by ilovelua on Октябрь 25, 2011

Есть массив:

local t = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Из него нужно удалить все элементы большие 2 и меньшие 9.

Неправильное решение: (more…)

Tagged with: , , , , ,