Модуль:Exponential search

Документація модуля[перегляд] [редагувати] [історія] [очистити кеш]

Цей модуль забезпечує алгоритм звичайного експоненціального пошуку. Цей вид пошуку може бути корисним, коли ви хочете знайти ключ у відсортованому масиві й при цьому бажаєте це зробити, перевіривши якомога менше елементів масиву. Це може включати такі ситуації як:

• Пошук найвищого числа архіву у наборі архівів без перевірки чи вони існують.
• Пошук кількості позиційних аргументів у frame.args без необхідності розкривати вікітекст для кожного із них.

Ви не повинні використовувати цей модуль, якщо застосовується хоча б одна з умов:

1. Ви можете використати оператор довжини Lua, щоб знайти те, що вам потрібно.
2. Ваш масив має у собі пропуски. (Іншими словами, будь-який з елементів перед фінальним елементом є nil, наприклад, {'foo', 'bar', nil, 'baz'}.) Якщо ви спробуєте і використаєте цей модуль на розрідженому масиві, то ви можете отримати хибне значення.
3. Ваш масив має менше ніж 10 елементів. Цей модуль можна використовувати для таких масивів, але ви всеодно будете звертатися до більшості елементів масиву (до деяких можливо двічі), а ваш код буде складнішими, ніж коли ви використаєте цикл.

Використання

Спершу, завантажте модуль.

local expSearch = require('Module:Exponential search')

Потім ви можете використати функцію expSearch з наступним синтаксисом:

expSearch(testFunc, init)

Параметри:

• testFunc — функція перевірки для вашого масиву. Ця функція повинна приймати додатне ціле число function i у свій перший параметр. Якщо елемент, який відповідає i, відсутній в масиві, то функція повинна повернути false або nil; а якщо наявний в масиві, то тоді функція повинна повернути правдиве значення (будь-що, окрім false або nil). (обов'язково)
• init — початкове значення i для перевірки. Для просунутих користувачів. (необов'язково)

expSearch поверне найвище значення i для якого testFunc є правдивою. Якщо не має жодного правдивого значення, то функція поверне nil.

Приклади

Архіви обговорення Джиммі

en:User talk:Jimbo Wales має архіви en:User talk:Jimbo Wales/Archive 1, en:User talk:Jimbo Wales/Archive 2, ... Щоб знайти найвище число архівів, ви використаєте ось такий код:

local expSearch = require('Module:Exponential search')
local highestArchive = expSearch(function (i)
	local archive = 'User talk:Jimbo Wales/Archive ' .. i
	return mw.title.new(archive).exists
end)

Архіви англійської Кнайпи

en:Wikipedia:Village pump (proposals) має старі архіви у вигляді en:Wikipedia:Village pump (proposals)/Archive A, en:Wikipedia:Village pump (proposals)/Archive B тощо. Після того як вони доходять до Archive Z, то наступним архівом є Archive AA. Хоча ці архіви більше не оновлюються, але як демонстрацію ми можемо знайти найвищий архів, використавши цей модуль. Для цього нам потрібна функція, що перетворює ціле число у відповідну назву архіву.

local expSearch = require('Module:Exponential search')

local function integerToAlpha(i)
	-- This function converts 1 to A, 2 to B, ... 26 to Z, 27 to AA, ...
	local ret = ''
	while i > 0 do
		local rem = i % 26
		if rem == 0 then
			rem = 26
		end
		local char = string.char(rem + 64) -- the "rem"th letter of the alphabet
		ret = char .. ret
		i = (i - rem) / 26
	end
	return ret
end

local function integerToArchive(i)
	return 'Wikipedia:Village pump (proposals)/Archive ' .. integerToAlpha(i)
end

local highestInteger = expSearch(function (i)
	local archive = integerToArchive(i)
	return mw.title.new(archive).exists
end)
local highestArchive = integerToArchive(highestInteger)

-- This module provides a generic exponential search algorithm.

local checkType = require('libraryUtil').checkType
local floor = math.floor

local function midPoint(lower, upper)
	return floor(lower + (upper - lower) / 2)
end

local function search(testFunc, i, lower, upper)
	if testFunc(i) then
		if i + 1 == upper then
			return i
		end
		lower = i
		if upper then
			i = midPoint(lower, upper)
		else
			i = i * 2
		end
		return search(testFunc, i, lower, upper)
	else
		upper = i
		i = midPoint(lower, upper)
		return search(testFunc, i, lower, upper)
	end
end

return function (testFunc, init)
	checkType('Exponential search', 1, testFunc, 'function')
	checkType('Exponential search', 2, init, 'number', true)
	if init and (init < 1 or init ~= floor(init) or init == math.huge) then
		error(string.format(
			"invalid init value '%s' detected in argument #2 to " ..
			"'Exponential search' (init value must be a positive integer)",
			tostring(init)
		), 2)
	end
	init = init or 2
	if not testFunc(1) then
		return nil
	end
	return search(testFunc, init, 1, nil)
end