Поиск отсутствующего числа в неотсортированной таблице

xor_search.lua

-- Для получения таблицы, типа {5,3,6,1,4,2,7} (1,7)
local function getArrayWithUniqueRandomNumbers(min,max)
	local array = {}

	local tmp = {} -- для расброса
	for i = min,max do
		table.insert(tmp,i)
	end

	repeat
		local _,k = table.Random(tmp)
		table.insert(array, table.remove(tmp,k))
	until !next(tmp)

	return array
end

-- Заменяет последнее число в таблице
local function replaceLastNum(t,n)
	t[#t] = n
end

-- битовая маска всех чисел в таблице
local function xorArray(t)
	return bit.bxor(unpack(t))
end

-- Получает маски диапазона чисел
local function xorRange(from,to)
	local t = {}
	for i = from,to do
		t[#t + 1] = i
	end

	return xorArray(t)
end

-- Путем подбора пытаемся узнать отсутствующее число в таблице.
-- Может работать с диапазонами
local function findMissingNumberXor(t,min,max)
	local need_xor = xorRange(min,max)

	-- заполняем отсутствующую ячейку таблицы переменным числом
	table.insert(t,0)

	-- Меняем переменное число до тех пор, пока битовые маски не совпадут
	-- Если маски совпадают, значит мы нашли изъятое число
	-- Или у нас есть все числа или параметры некорректны
	for i = min,max do
		replaceLastNum(t,i)

		if xorArray(t) == need_xor then
			return i
		end
	end
end

-- Быстрее, но работает только для массивов от 1 до N
local function findMissingNumberLoop(t)
	local size = #t + 1

	local sumAll = size * (size + 1) / 2
	local sumCurrent = 0
	for i,num in ipairs(t) do
		sumCurrent = sumCurrent + num
	end

	return (sumAll - sumCurrent)
end



-------------------------------------------------------------------------------------------------


-- Диапазон чисел, которые должны быть в таблице
local MIN_NUMBER = 1
local MAX_NUMBER = 500

-- Заполняем таблицу уникальными числами в случайном порядке
local array = getArrayWithUniqueRandomNumbers(MIN_NUMBER,MAX_NUMBER)

-- Удаляем неизвестное число из таблицы
local removed = table.remove(array)


-- Пропавшее число найдено: 233
local missing = findMissingNumberXor(array, MIN_NUMBER, MAX_NUMBER)
-- local missing = findMissingNumberLoop(array)
if missing then
	if missing == removed then
		print("Пропавшее число найдено: " .. missing)
	else
		print("Похоже, вводные данные указаны неверно или формат нарушен")
	end
else
	print("Все числа в таблице присутствуют")
end



-- require("bench")

-- bench.Compare({
-- 	xor  = function() findMissingNumberXor(array, MIN_NUMBER, MAX_NUMBER) end,
-- 	loop = function() findMissingNumberLoop(array) end,
-- },1000)

-- 500 numbers, 1000 calls
-- XOR: 1.579700065
-- LOOP: 0.0005687980010407