Я люблю 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

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

Реклама