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

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

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 Апрель 10, 2013

Тут на работе возник вопрос: насколько обильные комментарии замедляют скорость загрузки скриптов? Ответ: весьма незначительно. Ниже тест:

local testFolder = ...

require('lfs')

local folderCommented = testFolder .. 'commented/'

lfs.mkdir(folderCommented)

local folderUncommented = testFolder .. 'uncommented/'

lfs.mkdir(folderUncommented)

local commentedText = [[
-------------------------------------------------------------------------------
-- Удаляет подпись к заданной точке маршрута с карты.
function remove_waypoint_text%d(wpt)
  set_mapObjects(wpt.boss.mapObjects.route.numbers[wpt.index].id, nil)
  return table.remove(wpt.boss.mapObjects.route.numbers, wpt.index)
end

-------------------------------------------------------------------------------
--
function set_mapObjects%d(a_key, a_value)
	mapObjects[a_key] = a_value
end
]]

local fileCount = 100
local textCount = 100

for i = 1, fileCount do
	local filename = string.format('%s%03d.lua', folderCommented, i)
	local file = io.open(filename, 'w')
	for j = 1, textCount do
		-- зададим жару Lua - пусть все функции будут разными
		file:write(string.format(commentedText, j, j))
	end	
	file:close()
end

local uncommentedText = [[
function remove_waypoint_text%d(wpt)
  set_mapObjects(wpt.boss.mapObjects.route.numbers[wpt.index].id, nil)
  return table.remove(wpt.boss.mapObjects.route.numbers, wpt.index)
end

function set_mapObjects%d(a_key, a_value)
	mapObjects[a_key] = a_value
end
]]

for i = 1, fileCount do
	local filename = string.format('%s%03d.lua', folderUncommented, i)
	local file = io.open(filename, 'w')
	for j = 1, textCount do
		-- зададим жару Lua - пусть все функции будут разными
		file:write(string.format(uncommentedText, j, j))
	end	
	file:close()
end

-- загружаем файлы с комментариями
local startTime = os.clock()

for i = 1, fileCount do
	local filename = string.format('%s%03d.lua', folderCommented, i)
	dofile(filename)
end

local commentedTime = os.clock() - startTime
print('commented files loading time:', commentedTime)

-- загружаем файлы без комментариев
local startTime = os.clock()

for i = 1, fileCount do
	local filename = string.format('%s%03d.lua', folderUncommented, i)
	dofile(filename)
end

local uncommentedTime = os.clock() - startTime

print('uncommented files loading time:', uncommentedTime)
print(string.format('loading speed difference is: %0.2f%%', 100 - (uncommentedTime / commentedTime) * 100))

local commentedFilesSize = 4728400

print('total commented files size is %d bytes:', commentedFilesSize)

local uncommentedFilesSize =  2558400

print('total uncommented files size is %d bytes:', uncommentedFilesSize)

print(string.format('files size difference is: %0.2f%%', 100 - (uncommentedFilesSize / commentedFilesSize) * 100))

Запускаем:

commented files loading time: 0.382
uncommented files loading time: 0.363
loading speed difference is: 4.97%
total commented files size is %d bytes: 4728400
total uncommented files size is %d bytes: 2558400
files size difference is: 45.89%

Итого: комментированный фалов почти 4 с половиной мегабайта, некомментированных почти в 2 раза меньше. Разница в скорости загрузки ~5 процентов.

Резюме: о комментариях в коде можно не волноваться.

Сравнение таблиц 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} <

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

gluas plug-in for GIMP

Posted in Uncategorized by ilovelua on Февраль 14, 2013

А вот, допустим, захотелось вам на Lua обработать фотографию. Ну, там, цвета поменять,  или еще что нибудь гениальное сделать. Не вопрос! Идем на http://pippin.gimp.org/plug-ins/gluas/files/ и качаем бинарники плагина gluas. Затем gluas.exe распаковываем в пользовательскую папку с плагинами GIMP. Ее расположение можно посмотреть запустив GIMP->Edit-Preferences->Folders:

1

Затем открываем картинку в GIMP. Идем в Filters->Generic->gluas…:

2

Появляется окно со скриптом:

3

Нажимаем OK. Магия!

4

Tagged with: , , ,

Вопросы производительности — 3

Posted in Uncategorized by ilovelua on Сентябрь 17, 2012

Рассмотрим скорость доступа модуля к локальной переменной и к полю, объявленному внутри модуля. Код модуля:

module('TestModule', package.seeall)

local localTable = {}
testTable = {}

-- добавляем в модуль полей, чтобы поиск осуществлялся не в совсем пустой таблице
for i = 1, 100 do
    _M['testTable' .. i] = i
end

function getTestTable()
    return testTable
end

function getLocalTable()
    return localTable
end

Код теста:

local TestModule = require('TestModule')

local count = 1000000

function test()
    local t = os.clock ()

    for i = 1, count do
        TestModule.getTestTable()[i] = i
    end

    local t1 = os.clock () - t

    t = os.clock ()

    for i = 1, count do
        TestModule.getLocalTable()[i] = i
    end

    local t2 = os.clock () - t

    return t1, t2
end

local percents = {}

for i = 1, 100 do
    local t1, t2 = test()
    local delta = string.format('%.6f', t1 - t2)
    local p = string.format('%.6f', ((t1 - t2) / t1) * 100)

    print(i, 'delta:', delta, '%', p)

    table.insert(percents, p)
end

local totalPercents = 0

for i, percent in ipairs(percents) do
    totalPercents = totalPercents + percent
end

print('average percents is:', totalPercents / #percents)

Результаты:

1 delta: 0.028000 % 9.395973
2 delta: 0.015000 % 5.514706
3 delta: 0.013000 % 4.779412
4 delta: 0.015000 % 5.494505
5 delta: 0.011000 % 4.044118
6 delta: 0.015000 % 5.494505
7 delta: 0.014000 % 5.128205
8 delta: 0.015000 % 5.474453
9 delta: 0.014000 % 5.147059
10 delta: 0.014000 % 5.147059
11 delta: 0.011000 % 4.044118
12 delta: 0.014000 % 5.147059
13 delta: 0.012000 % 4.411765
14 delta: 0.011000 % 4.074074
15 delta: 0.012000 % 4.411765
16 delta: 0.015000 % 5.494505
17 delta: 0.014000 % 5.128205
18 delta: 0.013000 % 4.779412
19 delta: 0.013000 % 4.761905
20 delta: 0.013000 % 4.797048
21 delta: 0.013000 % 4.779412
22 delta: 0.015000 % 5.494505
23 delta: 0.015000 % 5.494505
24 delta: 0.013000 % 4.779412
25 delta: 0.011000 % 4.059041
26 delta: 0.013000 % 4.779412
27 delta: 0.013000 % 4.761905
28 delta: 0.013000 % 4.779412
29 delta: 0.013000 % 4.797048
30 delta: 0.014000 % 5.147059
31 delta: 0.015000 % 5.494505
32 delta: 0.014000 % 5.147059
33 delta: 0.014000 % 5.128205
34 delta: 0.014000 % 5.147059
35 delta: 0.014000 % 5.147059
36 delta: 0.014000 % 5.147059
37 delta: 0.015000 % 5.494505
38 delta: 0.015000 % 5.494505
39 delta: 0.014000 % 5.147059
40 delta: 0.014000 % 5.147059
41 delta: 0.014000 % 5.128205
42 delta: 0.016000 % 5.860806
43 delta: 0.014000 % 5.147059
44 delta: 0.014000 % 5.147059
45 delta: 0.014000 % 5.147059
46 delta: 0.012000 % 4.411765
47 delta: 0.013000 % 4.779412
48 delta: 0.015000 % 5.514706
49 delta: 0.013000 % 4.779412
50 delta: 0.013000 % 4.779412
51 delta: 0.014000 % 5.128205
52 delta: 0.012000 % 4.411765
53 delta: 0.015000 % 5.494505
54 delta: 0.016000 % 5.860806
55 delta: 0.015000 % 5.494505
56 delta: 0.014000 % 5.147059
57 delta: 0.015000 % 5.514706
58 delta: 0.014000 % 5.147059
59 delta: 0.014000 % 5.147059
60 delta: 0.013000 % 4.779412
61 delta: 0.014000 % 5.147059
62 delta: 0.013000 % 4.779412
63 delta: 0.013000 % 4.761905
64 delta: 0.014000 % 5.147059
65 delta: 0.013000 % 4.779412
66 delta: 0.012000 % 4.411765
67 delta: 0.013000 % 4.797048
68 delta: 0.013000 % 4.779412
69 delta: 0.015000 % 5.494505
70 delta: 0.011000 % 4.044118
71 delta: 0.014000 % 5.147059
72 delta: 0.015000 % 5.494505
73 delta: 0.013000 % 4.779412
74 delta: 0.015000 % 5.494505
75 delta: 0.013000 % 4.779412
76 delta: 0.016000 % 5.860806
77 delta: 0.015000 % 5.514706
78 delta: 0.014000 % 5.147059
79 delta: 0.013000 % 4.779412
80 delta: 0.015000 % 5.494505
81 delta: 0.016000 % 5.818182
82 delta: 0.013000 % 4.761905
83 delta: 0.013000 % 4.779412
84 delta: 0.016000 % 5.860806
85 delta: 0.012000 % 4.411765
86 delta: 0.013000 % 4.779412
87 delta: 0.014000 % 5.128205
88 delta: 0.015000 % 5.514706
89 delta: 0.012000 % 4.411765
90 delta: 0.014000 % 5.147059
91 delta: 0.015000 % 5.494505
92 delta: 0.014000 % 5.147059
93 delta: 0.016000 % 5.860806
94 delta: 0.017000 % 6.204380
95 delta: 0.014000 % 5.147059
96 delta: 0.014000 % 5.147059
97 delta: 0.013000 % 4.779412
98 delta: 0.012000 % 4.411765
99 delta: 0.012000 % 4.411765
100 delta: 0.015000 % 5.494505
average percents is: 5.1020022

Здесь результаты не столь впечатляющие, как в предыдущем тесте, но тем не менее разница в ~5% есть.
Вывод: локальные переменные — наши друзья.

Вопросы производительности — 2

Posted in Uncategorized by ilovelua on Сентябрь 17, 2012

К вопросу о том, стоит ли заводить отдельные поля в модуле или пользоваться локальными переменными внутри модуля.

Код модуля:

module('TestModule', package.seeall)

local localTable = {}
testTable = {}

local count = 1000000

-- добавляем в модуль полей, чтобы поиск осуществлялся не в совсем пустой таблице
for i = 1, 100 do
    _M['testTable' .. i] = i
end

function fillTestTable()
    for i = 1, count do 
        testTable[i] = i
    end
end

function fillLocalTable()
    for i= 1, count do 
        localTable[i] = i
    end
end

Код теста:

local TestModule = require('TestModule')

function test()
    local t = os.clock ()
    TestModule.fillTestTable()
    local t1 = os.clock () - t

    t = os.clock ()
    TestModule.fillLocalTable()
    local t2 = os.clock () - t

    return t1, t2
end

local percents = {}

for i = 1, 100 do
    local t1, t2 = test()
    local delta = string.format('%.6f', t1 - t2)
    local p = string.format('%.6f', ((t1 - t2) / t1) * 100)

    print(i, 'delta:', delta, '%', p)

    table.insert(percents, p)
end

local totalPercents = 0

for i, percent in ipairs(percents) do
    totalPercents = totalPercents + percent
end

print('average percents is:', totalPercents / #percents)

Результаты:

1 delta: 0.020000 % 15.748031
2 delta: 0.023000 % 22.549020
3 delta: 0.022000 % 21.782178
4 delta: 0.022000 % 21.782178
5 delta: 0.022000 % 21.782178
6 delta: 0.022000 % 21.782178
7 delta: 0.022000 % 21.782178
8 delta: 0.021000 % 20.792079
9 delta: 0.021000 % 20.792079
10 delta: 0.021000 % 20.792079
11 delta: 0.021000 % 20.792079
12 delta: 0.023000 % 22.549020
13 delta: 0.021000 % 20.792079
14 delta: 0.023000 % 22.549020
15 delta: 0.022000 % 21.782178
16 delta: 0.023000 % 22.549020
17 delta: 0.023000 % 22.549020
18 delta: 0.023000 % 22.549020
19 delta: 0.021000 % 20.792079
20 delta: 0.023000 % 22.330097
21 delta: 0.021000 % 20.792079
22 delta: 0.022000 % 21.782178
23 delta: 0.022000 % 21.782178
24 delta: 0.021000 % 20.792079
25 delta: 0.023000 % 22.549020
26 delta: 0.021000 % 20.792079
27 delta: 0.022000 % 21.568627
28 delta: 0.022000 % 21.568627
29 delta: 0.024000 % 23.076923
30 delta: 0.022000 % 21.782178
31 delta: 0.021000 % 20.792079
32 delta: 0.022000 % 21.782178
33 delta: 0.023000 % 22.549020
34 delta: 0.022000 % 21.782178
35 delta: 0.022000 % 21.782178
36 delta: 0.022000 % 21.782178
37 delta: 0.022000 % 21.782178
38 delta: 0.022000 % 21.782178
39 delta: 0.021000 % 20.792079
40 delta: 0.022000 % 21.782178
41 delta: 0.021000 % 20.792079
42 delta: 0.022000 % 21.782178
43 delta: 0.022000 % 21.782178
44 delta: 0.022000 % 21.782178
45 delta: 0.020000 % 19.801980
46 delta: 0.022000 % 21.782178
47 delta: 0.023000 % 22.549020
48 delta: 0.022000 % 21.782178
49 delta: 0.022000 % 21.782178
50 delta: 0.022000 % 21.782178
51 delta: 0.023000 % 22.549020
52 delta: 0.022000 % 21.782178
53 delta: 0.022000 % 21.782178
54 delta: 0.022000 % 21.782178
55 delta: 0.021000 % 20.792079
56 delta: 0.022000 % 21.782178
57 delta: 0.022000 % 21.782178
58 delta: 0.022000 % 21.782178
59 delta: 0.022000 % 21.782178
60 delta: 0.021000 % 20.792079
61 delta: 0.020000 % 20.000000
62 delta: 0.022000 % 21.782178
63 delta: 0.022000 % 21.782178
64 delta: 0.021000 % 20.792079
65 delta: 0.022000 % 21.782178
66 delta: 0.021000 % 20.792079
67 delta: 0.022000 % 21.782178
68 delta: 0.022000 % 21.782178
69 delta: 0.021000 % 20.792079
70 delta: 0.022000 % 21.782178
71 delta: 0.022000 % 21.782178
72 delta: 0.022000 % 21.782178
73 delta: 0.022000 % 21.782178
74 delta: 0.022000 % 21.782178
75 delta: 0.022000 % 21.782178
76 delta: 0.021000 % 20.792079
77 delta: 0.022000 % 21.782178
78 delta: 0.022000 % 21.782178
79 delta: 0.022000 % 21.782178
80 delta: 0.023000 % 22.549020
81 delta: 0.022000 % 21.782178
82 delta: 0.022000 % 21.782178
83 delta: 0.023000 % 22.549020
84 delta: 0.022000 % 21.782178
85 delta: 0.023000 % 22.549020
86 delta: 0.022000 % 21.782178
87 delta: 0.022000 % 21.782178
88 delta: 0.022000 % 21.782178
89 delta: 0.022000 % 21.782178
90 delta: 0.022000 % 21.782178
91 delta: 0.023000 % 22.549020
92 delta: 0.022000 % 21.782178
93 delta: 0.022000 % 21.782178
94 delta: 0.022000 % 21.782178
95 delta: 0.022000 % 21.782178
96 delta: 0.022000 % 21.782178
97 delta: 0.021000 % 20.792079
98 delta: 0.022000 % 21.782178
99 delta: 0.022000 % 21.782178
100 delta: 0.022000 % 21.568627
average percents is: 21.61547195

Вывод: обращение к локальным переменным на ~20% быстрее, чем к полям модуля.
Локальные переменные — наши друзья.

Вопросы производительности

Posted in Uncategorized by ilovelua on Сентябрь 11, 2012

Стало мне тут интересно, насколько в модулях Lua передача таблицы в качестве параметра в функцию быстрее, чем поиск таблицы по имени внутри модуля. Для этого был сооружен тестовый модуль TestModule.lua:

module('TestModule', package.seeall)

testTable = {}

local count = 1000000

-- добавляем в модуль полей, чтобы поиск осуществлялся не в пустой таблице
for i = 1, 100 do
    _M['testTable' .. i] = i
end

function fillTestTableStraight()
    local f = function(i)
        testTable[i] = i
    end

    for i = 1, count do
        f(i)
    end
end

function fillTestTableFromStack()
    local f = function(t, i)
        t[i] = i
    end

    for i = 1, count do
        f(testTable, i)
    end
end

А вот код теста:

local TestModule = require('TestModule')

function test()
    local t = os.clock ()
    TestModule.fillTestTableStraight()
    local t1 = os.clock () - t

    t = os.clock ()
    TestModule.fillTestTableFromStack()
    local t2 = os.clock () - t

    return t1, t2
end

local percents = {}

for i = 1, 100 do
    local t1, t2 = test()
    local delta = string.format('%.6f', t1 - t2)
    local p = string.format('%.6f', ((t1 - t2) / t1) * 100)

    print(i, 'delta:', delta, '%', p)

    table.insert(percents, p)
end

local totalPercents = 0

for i, percent in ipairs(percents) do
    totalPercents = totalPercents + percent
end

print('average percents is:', totalPercents / #percents)

Вот результаты:

1 delta: 0.038000 % 14.728682
2 delta: 0.009000 % 3.913043
3 delta: 0.010000 % 4.329004
4 delta: 0.008000 % 3.508772
5 delta: 0.008000 % 3.508772
6 delta: 0.008000 % 3.508772
7 delta: 0.007000 % 3.070175
8 delta: 0.007000 % 3.083700
9 delta: 0.007000 % 3.070175
10 delta: 0.007000 % 3.083700
11 delta: 0.008000 % 3.508772
12 delta: 0.008000 % 3.508772
13 delta: 0.008000 % 3.508772
14 delta: 0.008000 % 3.508772
15 delta: 0.007000 % 3.083700
16 delta: 0.003000 % 1.315789
17 delta: 0.016000 % 6.779661
18 delta: 0.007000 % 3.070175
19 delta: 0.008000 % 3.508772
20 delta: 0.007000 % 3.083700
21 delta: 0.010000 % 4.366812
22 delta: 0.008000 % 3.508772
23 delta: 0.008000 % 3.508772
24 delta: 0.007000 % 3.070175
25 delta: 0.009000 % 3.930131
26 delta: 0.011000 % 4.761905
27 delta: 0.008000 % 3.508772
28 delta: 0.007000 % 3.083700
29 delta: 0.006000 % 2.643172
30 delta: 0.008000 % 3.508772
31 delta: 0.008000 % 3.508772
32 delta: 0.007000 % 3.070175
33 delta: 0.007000 % 3.083700
34 delta: 0.008000 % 3.508772
35 delta: 0.007000 % 3.083700
36 delta: 0.008000 % 3.508772
37 delta: 0.007000 % 3.083700
38 delta: 0.008000 % 3.508772
39 delta: 0.008000 % 3.508772
40 delta: 0.007000 % 3.083700
41 delta: 0.008000 % 3.508772
42 delta: 0.007000 % 3.056769
43 delta: 0.008000 % 3.508772
44 delta: 0.007000 % 3.083700
45 delta: 0.009000 % 3.930131
46 delta: 0.007000 % 3.083700
47 delta: 0.007000 % 3.083700
48 delta: 0.009000 % 3.947368
49 delta: 0.008000 % 3.508772
50 delta: 0.009000 % 3.947368
51 delta: 0.008000 % 3.508772
52 delta: 0.008000 % 3.508772
53 delta: 0.008000 % 3.508772
54 delta: 0.007000 % 3.083700
55 delta: 0.007000 % 3.083700
56 delta: 0.008000 % 3.508772
57 delta: 0.008000 % 3.508772
58 delta: 0.008000 % 3.508772
59 delta: 0.008000 % 3.508772
60 delta: 0.009000 % 3.947368
61 delta: 0.008000 % 3.508772
62 delta: 0.007000 % 3.083700
63 delta: 0.009000 % 3.930131
64 delta: 0.006000 % 2.643172
65 delta: 0.007000 % 3.070175
66 delta: 0.008000 % 3.508772
67 delta: 0.008000 % 3.508772
68 delta: 0.008000 % 3.508772
69 delta: 0.006000 % 2.643172
70 delta: 0.010000 % 4.366812
71 delta: 0.008000 % 3.508772
72 delta: 0.007000 % 3.083700
73 delta: 0.009000 % 3.947368
74 delta: 0.008000 % 3.508772
75 delta: 0.008000 % 3.508772
76 delta: 0.007000 % 3.083700
77 delta: 0.009000 % 3.930131
78 delta: 0.008000 % 3.524229
79 delta: 0.009000 % 3.947368
80 delta: 0.009000 % 3.947368
81 delta: 0.008000 % 3.508772
82 delta: 0.009000 % 3.947368
83 delta: 0.008000 % 3.508772
84 delta: 0.007000 % 3.083700
85 delta: 0.007000 % 3.083700
86 delta: 0.007000 % 3.083700
87 delta: 0.008000 % 3.508772
88 delta: 0.008000 % 3.508772
89 delta: 0.007000 % 3.083700
90 delta: 0.007000 % 3.083700
91 delta: 0.008000 % 3.508772
92 delta: 0.006000 % 2.620087
93 delta: 0.044000 % 16.666667
94 delta: 0.008000 % 3.508772
95 delta: 0.010000 % 4.347826
96 delta: 0.008000 % 3.508772
97 delta: 0.007000 % 3.083700
98 delta: 0.008000 % 3.508772
99 delta: 0.008000 % 3.508772
100 delta: 0.008000 % 3.508772
average percents is: 3.6979102

Я несколько раз запускал этот тест, и результаты крутятся около 3.5%.

Ну, разница, понятно, не велика. Однако она есть. Чтобы почувствовать, насколько плох поиск по ключу в цикле, нужно воспользоваться локальными переменными. Поменяем в модуле TestModule функцию fillTestTableFromStack():

function fillTestTableFromStack()
    local f = function(t, i)
        t[i] = i
    end

    local tbl = testTable

    for i = 1, count do
        f(tbl, i)
    end
end

Результаты впечатляют гораздо сильнее:
1 delta: 0.037000 % 14.682540
2 delta: 0.038000 % 16.379310
3 delta: 0.033000 % 14.473684
4 delta: 0.037000 % 16.086957
5 delta: 0.033000 % 14.601770
6 delta: 0.037000 % 16.157205
7 delta: 0.036000 % 15.789474
8 delta: 0.033000 % 14.537445
9 delta: 0.033000 % 14.601770
10 delta: 0.035000 % 15.486726
11 delta: 0.035000 % 15.418502
12 delta: 0.032000 % 14.096916
13 delta: 0.034000 % 14.977974
14 delta: 0.034000 % 15.044248
15 delta: 0.033000 % 14.666667
16 delta: 0.035000 % 15.418502
17 delta: 0.035000 % 15.418502
18 delta: 0.030000 % 13.043478
19 delta: 0.036000 % 15.789474
20 delta: 0.035000 % 15.418502
21 delta: 0.034000 % 15.044248
22 delta: 0.034000 % 15.111111
23 delta: 0.036000 % 15.789474
24 delta: 0.035000 % 15.418502
25 delta: 0.035000 % 15.418502
26 delta: 0.035000 % 15.418502
27 delta: 0.035000 % 15.418502
28 delta: 0.034000 % 15.044248
29 delta: 0.034000 % 15.044248
30 delta: 0.036000 % 15.859031
31 delta: 0.034000 % 15.044248
32 delta: 0.035000 % 15.418502
33 delta: 0.035000 % 15.418502
34 delta: 0.033000 % 14.666667
35 delta: 0.034000 % 15.044248
36 delta: 0.034000 % 15.044248
37 delta: 0.034000 % 15.044248
38 delta: 0.035000 % 15.418502
39 delta: 0.035000 % 15.418502
40 delta: 0.033000 % 14.666667
41 delta: 0.034000 % 15.044248
42 delta: 0.035000 % 15.418502
43 delta: 0.036000 % 15.789474
44 delta: 0.035000 % 15.418502
45 delta: 0.032000 % 14.159292
46 delta: 0.033000 % 14.666667
47 delta: 0.035000 % 15.418502
48 delta: 0.035000 % 15.418502
49 delta: 0.036000 % 15.789474
50 delta: 0.036000 % 15.859031
51 delta: 0.035000 % 15.418502
52 delta: 0.034000 % 15.044248
53 delta: 0.037000 % 16.228070
54 delta: 0.036000 % 15.789474
55 delta: 0.037000 % 16.228070
56 delta: 0.035000 % 15.418502
57 delta: 0.035000 % 15.486726
58 delta: 0.034000 % 15.044248
59 delta: 0.034000 % 15.044248
60 delta: 0.036000 % 15.789474
61 delta: 0.034000 % 15.044248
62 delta: 0.037000 % 16.228070
63 delta: 0.034000 % 15.044248
64 delta: 0.035000 % 15.486726
65 delta: 0.036000 % 15.859031
66 delta: 0.034000 % 15.044248
67 delta: 0.035000 % 15.350877
68 delta: 0.037000 % 16.228070
69 delta: 0.034000 % 15.044248
70 delta: 0.034000 % 15.111111
71 delta: 0.037000 % 16.228070
72 delta: 0.036000 % 15.859031
73 delta: 0.037000 % 16.228070
74 delta: 0.036000 % 15.859031
75 delta: 0.035000 % 15.418502
76 delta: 0.036000 % 15.859031
77 delta: 0.036000 % 15.789474
78 delta: 0.034000 % 15.044248
79 delta: 0.034000 % 15.044248
80 delta: 0.035000 % 15.418502
81 delta: 0.035000 % 15.486726
82 delta: 0.035000 % 15.418502
83 delta: 0.035000 % 15.486726
84 delta: 0.034000 % 15.044248
85 delta: 0.037000 % 16.228070
86 delta: 0.034000 % 15.044248
87 delta: 0.035000 % 15.418502
88 delta: 0.034000 % 15.044248
89 delta: 0.034000 % 15.044248
90 delta: 0.035000 % 15.418502
91 delta: 0.040000 % 17.167382
92 delta: 0.038000 % 16.593886
93 delta: 0.034000 % 15.044248
94 delta: 0.035000 % 15.418502
95 delta: 0.034000 % 15.044248
96 delta: 0.034000 % 15.044248
97 delta: 0.033000 % 14.666667
98 delta: 0.036000 % 15.789474
99 delta: 0.038000 % 16.593886
100 delta: 0.034000 % 15.044248
average percents is: 15.36543997

Вывод: локальные переменные — наши друзья.

Перемешивание элементов массива

Posted in Uncategorized by ilovelua on Март 14, 2012

Нужно перемешать элементы массива в случайном порядке:

function swap(array, index1, index2)
  array[index1], array[index2] = array[index2], array[index1]
end

function shake(array)
  local counter = #array

  while counter > 1 do
    local index = math.random(counter)

    swap(array, index, counter)		
    counter = counter - 1
  end
end
Tagged with: ,

Сопрограммы(coroutines)

Posted in Uncategorized by ilovelua on Февраль 2, 2012

Автор Валерий Блажнов.

Сопрограмма — это обертка вокруг функции, выполнение которой
может приостанавливаться ею с возвратом промежуточных результатов
и затем продолжаться вызывающей программой с передачей новых
значений параметров. В Lua функции работы с сопрограммами
представлены в стандартной библиотеке coroutine. (more…)

Конвертор цвета из hex в RGBA

Posted in Uncategorized by ilovelua on Январь 23, 2012

Встала задача, превратить цвет, заданный в форме 0x37abc8ff в четыре числовых значения RGBA. Для этого можно воспользоваться какой-нибудь Lua библиотекой для работы с битами(например, http://bitop.luajit.org/), а можно это сделать по рабоче-крестьянки, поскольку Lua умеет парсить hex-числа (идея украдена отсюда: http://www.javascripter.net/faq/hextorgb.htm):

function parseHexColor(text)
  local r = tonumber('0x' .. string.sub(text, -8, -7))
  local g = tonumber('0x' .. string.sub(text, -6, -5))
  local b = tonumber('0x' .. string.sub(text, -4, -3))
  local a = tonumber('0x' .. string.sub(text, -2))

  return r, g, b, a
end
Tagged with: , ,