ماڊيول:Exponential search

هي ماڊيول هڪ عام قسم جو ايڪسپونينشل تلاش الگورٿم مهيا ڪري ٿو. اهڙي قسم جي ڳولا تڏهن مفيد ٿيندي آهي جڏهن توهان ڪنهن ترتيب ڏنل array ۾ ڪنهن key کي ڳولڻ چاهيو ٿا ۽ اهو ڪم اهڙي نموني ڪرڻ چاهيو ٿا جو جيترو ٿي سگهي گهٽ ترتيبي عنصرن کي چيڪ ڪرڻو پوي. اهڙيون حالتون هيٺين مثالن وانگر ٿي سگهن ٿيون:

• سڀئي آرڪائيو موجود آهن يا نه اهو الڳ الڳ چيڪ ڪرڻ کانسواءِ آرڪائيوز جي سيٽ ۾ سڀ کان وڏي آرڪائيو نمبر کي ڳولڻ.
• frame.args ۾ positional arguments جو تعداد ڳولڻ بغير ان جي ته هر هڪ لاءِ wikitext کي expand ڪرڻو پوي.

هي ماڊيول استعمال نه ڪرڻ گهرجي جيڪڏهن هيٺين حالتن مان ڪا به لاڳو ٿئي:

1. توهان جيڪو ڳولڻ چاهيو ٿا اهو Lua length operator استعمال ڪري حاصل ڪري سگهو ٿا.
2. توهان جي array ۾ ڪو به خال (gap) موجود هجي. (يعني آخري عنصر کان اڳ ڪنهن به هنڌ تي nil هجي، مثال طور: {'foo', 'bar', nil, 'baz'}.) جيڪڏهن توهان اهڙي sparse array تي هي ماڊيول استعمال ڪندا ته ممڪن آهي ته غلط نتيجو ملي.
3. توهان جي array ۾ لڳ ڀڳ 10 کان گهٽ عنصر هجن. اهڙين حالتن ۾ به هي ماڊيول استعمال ڪري سگهجي ٿو، پر توهان کي تقريباً سڀئي array عنصر چيڪ ڪرڻا پوندا (شايد ڪي عنصر ٻه ڀيرا)، ۽ توهان جو ڪوڊ سادو for لوپ استعمال ڪرڻ کان وڌيڪ پيچيده ٿي ويندو.

استعمال

پهريون، ماڊيول لوڊ ڪريو.

local expSearch = require('ماڊيول:Exponential search')

ان کان پوءِ توهان هيٺين طريقي سان expSearch فنڪشن استعمال ڪري سگهو ٿا:

expSearch(testFunc, init)

پيراميٽر:

• testFunc — توهان جي array لاءِ هڪ ٽيسٽ فنڪشن. هي فنڪشن پهرين پيراميٽر طور هڪ مثبت عدد i وٺندو. جيڪڏهن i سان لاڳاپيل عنصر array ۾ موجود نه هجي ته فنڪشن کي false يا nil واپس ڪرڻ گهرجي؛ ۽ جيڪڏهن اهو عنصر موجود هجي ته فنڪشن کي هڪ truthy قدر (يعني false يا nil کانسواءِ ڪا به قيمت) واپس ڪرڻ گهرجي. (ضروري)

• init — i جي شروعاتي قيمت جيڪا چيڪ ڪئي ويندي. هي ترقي يافته استعمال ڪندڙن لاءِ آهي. (اختياري)

expSearch اهو سڀ کان وڏو قدر i واپس ڪندو جنهن لاءِ testFunc سچو (truthy) نتيجو ڏئي. جيڪڏهن ڪو به قدر سچو نه هجي ته فنڪشن nil واپس ڪندو.

مثال

جمبو جي ڳالهه ٻولهه جا آرڪائيو

User talk:Jimbo Wales جا آرڪائيو User talk:Jimbo Wales/Archive 1، User talk:Jimbo Wales/Archive 2، ... تي موجود آهن. سڀ کان وڏو آرڪائيو نمبر ڳولڻ لاءِ توهان هي ڪوڊ استعمال ڪري سگهو ٿا:

local expSearch = require('ماڊيول:Exponential search')
local highestArchive = expSearch(function (i)
	local archive = 'User talk:Jimbo Wales/Archive ' .. i
	return mw.title.new(archive).exists
end)

وليج پمپ جا آرڪائيو

وڪيپيڊيا:ڳوٺ وارو پمپ (رٿون) جا پراڻا آرڪائيو وڪيپيڊيا: ڳوٺ وارو پمپ (رٿون)/آرڪائيو اي، وڪيپيڊيا: ڳوٺ وارو پمپ (رٿون)/آرڪائيو بي وغيره آهن. جڏهن اهي آرڪائيو زي تائين پهچي وڃن ٿا ته ايندڙ آرڪائيو آرڪائيو اي اي هوندو آهي. جيتوڻيڪ اهي آرڪائيو هاڻي اپڊيٽ نٿا ٿين، پر مثال طور اسان هن ماڊيول جي مدد سان سڀ کان وڏو آرڪائيو ڳولي سگهون ٿا؛ ان لاءِ رڳو هڪ اهڙو فنڪشن گهرجي جيڪو انٽيگر کي لاڳاپيل آرڪائيو نالي ۾ تبديل ڪري.

local expSearch = require('ماڊيول:Exponential search')

local function integerToAlpha(i)
	-- هي فنڪشن 1 کي A، 2 کي B، ... 26 کي Z، 27 کي AA وغيره ۾ تبديل ڪري ٿو
	local ret = ''
	while i > 0 do
		local rem = i % 26
		if rem == 0 then
			rem = 26
		end
		local char = string.char(rem + 64) -- الفابيٽ جو "rem"هون اکر
		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.
require[[strict]]

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