Заполнение таблиц данными
Нередко встает задача заполнить таблицу данными.
Допустим, нам нужно создать список параметров.
Каждый параметр — это таблица вида:
{ 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
Не помню, сам я это придумал, или где-то украл 🙂
Поиск позиции для вставки элемента в отсортированный массив
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
Есть две таблицы вида:
[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} <
Ну вот, различный порядок обхода таблиц. Жаль, что не получилось. А идея была неплохая, да…
Удаление данных из таблицы внутри цикла
Есть массив:
local t = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Из него нужно удалить все элементы большие 2 и меньшие 9.
Неправильное решение: (more…)
5 комментариев