Module:Exponential search/doc - Revision history

Warudo: Added the page to :Category:Module documentation pages

2024-08-29T21:17:59Z

Added the page to Category:Module documentation pages

← Previous revision		Revision as of 21:17, 29 August 2024
Line 79:		Line 79:
	<!-- Categories below this line, please; interwikis at Wikidata -->		<!-- Categories below this line, please; interwikis at Wikidata -->

	}}</includeonly>		}}</includeonly><noinclude>
			[[Category:Module documentation pages]]
			</noinclude>

Hike395: highly-used template

2024-08-15T11:54:55Z

highly-used template

← Previous revision		Revision as of 11:54, 15 August 2024
Line 1:		Line 1:
			{{high use}}
	This module provides a generic [[exponential search]] algorithm. This kind of search can be useful when you want to find a key in some kind of sorted array, and you want to do it by checking as few array elements as possible. This could include situations like:		This module provides a generic [[exponential search]] algorithm. This kind of search can be useful when you want to find a key in some kind of sorted array, and you want to do it by checking as few array elements as possible. This could include situations like:
	* Finding the highest archive number in a set of archives without checking whether they all exist.		* Finding the highest archive number in a set of archives without checking whether they all exist.

WOSlinker: change source to syntaxhighlight

2020-07-07T16:26:21Z

change source to syntaxhighlight

← Previous revision		Revision as of 16:26, 7 July 2020
Line 5:		Line 5:
	You shouldn't use this module if any of the following apply:		You shouldn't use this module if any of the following apply:
	# You can use the [[mw:Extension:Scribunto/Lua reference manual#Length operator\|Lua length operator]] to find what you need.		# You can use the [[mw:Extension:Scribunto/Lua reference manual#Length operator\|Lua length operator]] to find what you need.
	# Your array has any gaps in it. (In other words, any of the items before the final item is <code>nil</code>, e.g. <~~source~~ lang="lua" inline>{'foo', 'bar', nil, 'baz'}</~~source~~>.) If you try and use this module on a sparse array, you might get an erroneous value.		# Your array has any gaps in it. (In other words, any of the items before the final item is <code>nil</code>, e.g. <syntaxhighlight lang="lua" inline>{'foo', 'bar', nil, 'baz'}</syntaxhighlight>.) If you try and use this module on a sparse array, you might get an erroneous value.
	# Your array has less then about 10 items in it. It's possible to use this module for those arrays, but you will access most of the array elements anyway (perhaps some of them twice), and your code will be more complicated than if you just used a for loop.		# Your array has less then about 10 items in it. It's possible to use this module for those arrays, but you will access most of the array elements anyway (perhaps some of them twice), and your code will be more complicated than if you just used a for loop.

Line 12:		Line 12:
	First, load the module.		First, load the module.

	<~~source~~ lang="lua">		<syntaxhighlight lang="lua">
	local expSearch = require('Module:Exponential search')		local expSearch = require('Module:Exponential search')
			</syntaxhighlight>
	</source>

	You can then use the expSearch function with the following syntax:		You can then use the expSearch function with the following syntax:

	<~~source~~ lang="lua">		<syntaxhighlight lang="lua">
	expSearch(testFunc, init)		expSearch(testFunc, init)
			</syntaxhighlight>
	</source>

	Parameters:		Parameters:
Line 34:		Line 34:
	[[User talk:Jimbo Wales]] has archives at [[User talk:Jimbo Wales/Archive 1]], [[User talk:Jimbo Wales/Archive 2]], ... To find the highest archive number, you would use code like this:		[[User talk:Jimbo Wales]] has archives at [[User talk:Jimbo Wales/Archive 1]], [[User talk:Jimbo Wales/Archive 2]], ... To find the highest archive number, you would use code like this:

	<~~source~~ lang="lua">		<syntaxhighlight lang="lua">
	local expSearch = require('Module:Exponential search')		local expSearch = require('Module:Exponential search')
	local highestArchive = expSearch(function (i)		local highestArchive = expSearch(function (i)
Line 40:		Line 40:
	return mw.title.new(archive).exists		return mw.title.new(archive).exists
	end)		end)
			</syntaxhighlight>
	</source>

	=== Village pump archives ===		=== Village pump archives ===
Line 46:		Line 46:
	[[Wikipedia:Village pump (proposals)]] has old archives at [[Wikipedia:Village pump (proposals)/Archive A]], [[Wikipedia:Village pump (proposals)/Archive B]], etc. After they go through to Archive Z, the next archive is Archive AA. Although these archives aren't being updated anymore, as a demonstration we can find the highest one using this module; all we need is a function that converts from an integer to the corresponding archive name.		[[Wikipedia:Village pump (proposals)]] has old archives at [[Wikipedia:Village pump (proposals)/Archive A]], [[Wikipedia:Village pump (proposals)/Archive B]], etc. After they go through to Archive Z, the next archive is Archive AA. Although these archives aren't being updated anymore, as a demonstration we can find the highest one using this module; all we need is a function that converts from an integer to the corresponding archive name.

	<~~source~~ lang="lua">		<syntaxhighlight lang="lua">
	local expSearch = require('Module:Exponential search')		local expSearch = require('Module:Exponential search')

Line 73:		Line 73:
	end)		end)
	local highestArchive = integerToArchive(highestInteger)		local highestArchive = integerToArchive(highestInteger)
			</syntaxhighlight>
	</source>

	<includeonly>{{#ifeq:{{SUBPAGENAME}}\|sandbox \| \|		<includeonly>{{#ifeq:{{SUBPAGENAME}}\|sandbox \| \|

Erutuon: ce

2019-02-28T02:09:40Z

← Previous revision		Revision as of 02:09, 28 February 2019
Line 5:		Line 5:
	You shouldn't use this module if any of the following apply:		You shouldn't use this module if any of the following apply:
	# You can use the [[mw:Extension:Scribunto/Lua reference manual#Length operator\|Lua length operator]] to find what you need.		# You can use the [[mw:Extension:Scribunto/Lua reference manual#Length operator\|Lua length operator]] to find what you need.
	# Your array has any gaps in. (In other words, any of the items before the final item is <code>nil</code>, e.g. <source lang="lua" inline>{'foo', 'bar', nil, 'baz'}</source>.) If you try and use this module on a sparse array, you might get an erroneous value.		# Your array has any gaps in it. (In other words, any of the items before the final item is <code>nil</code>, e.g. <source lang="lua" inline>{'foo', 'bar', nil, 'baz'}</source>.) If you try and use this module on a sparse array, you might get an erroneous value.
	# Your array has less then about 10 items in it. It's possible to use this module for those arrays, but you will access most of the array elements anyway (perhaps some of them twice), and your code will be more complicated than if you just used a for loop.		# Your array has less then about 10 items in it. It's possible to use this module for those arrays, but you will access most of the array elements anyway (perhaps some of them twice), and your code will be more complicated than if you just used a for loop.

Mr. Stradivarius: give example of a sparse array

2017-02-02T05:46:43Z

give example of a sparse array

← Previous revision		Revision as of 05:46, 2 February 2017
Line 5:		Line 5:
	You shouldn't use this module if any of the following apply:		You shouldn't use this module if any of the following apply:
	# You can use the [[mw:Extension:Scribunto/Lua reference manual#Length operator\|Lua length operator]] to find what you need.		# You can use the [[mw:Extension:Scribunto/Lua reference manual#Length operator\|Lua length operator]] to find what you need.
	# Your array has any gaps in. If you try and use this module on a sparse array, you might get an erroneous value.		# Your array has any gaps in. (In other words, any of the items before the final item is <code>nil</code>, e.g. <source lang="lua" inline>{'foo', 'bar', nil, 'baz'}</source>.) If you try and use this module on a sparse array, you might get an erroneous value.
	# Your array has less then about 10 items in it. It's possible to use this module for those arrays, but you will access most of the array elements anyway (perhaps some of them twice), and your code will be more complicated than if you just used a for loop.		# Your array has less then about 10 items in it. It's possible to use this module for those arrays, but you will access most of the array elements anyway (perhaps some of them twice), and your code will be more complicated than if you just used a for loop.

Mr. Stradivarius: use the original archives rather than the ClueBot III indexes, and simplify the code a little

2015-02-27T16:27:31Z

use the original archives rather than the ClueBot III indexes, and simplify the code a little

← Previous revision		Revision as of 16:27, 27 February 2015
Line 42:		Line 42:
	</source>		</source>

	=== ~~ClueBot~~ ~~III~~ ~~archive indexes~~ ===		=== Village pump archives ===

	~~[[User:ClueBot III]] keeps archives of~~ [[Wikipedia:Village pump (proposals)]] at [[~~User:ClueBot III/Detailed Indices/~~Wikipedia:Village pump (proposals)/Archive A]], [[~~User:ClueBot III/Detailed Indices/~~Wikipedia:Village pump (proposals)/Archive B]], etc. After they go through to Archive Z, the next archive is Archive AA. We ~~can~~ ~~use~~ ~~this~~ ~~module~~ to find the highest of ~~these~~ ~~indexes~~ ~~as well~~; all we need is a function that converts from ~~<var>i</var>~~ to ~~ClueBot's~~ ~~alphabetical~~ ~~naming~~ ~~system~~.		[[Wikipedia:Village pump (proposals)]] has old archives at [[Wikipedia:Village pump (proposals)/Archive A]], [[Wikipedia:Village pump (proposals)/Archive B]], etc. After they go through to Archive Z, the next archive is Archive AA. Although these archives aren't being updated anymore, as a demonstration we can find the highest one using this module; all we need is a function that converts from an integer to the corresponding archive name.

	<source lang="lua">		<source lang="lua">
Line 64:		Line 64:
	end		end

			local function integerToArchive(i)
	local indexPrefix = 'User:ClueBot III/Detailed Indices/Wikipedia:Village pump (proposals)/Archive '
			return 'Wikipedia:Village pump (proposals)/Archive ' .. integerToAlpha(i)
			end

	local highestInteger = expSearch(function (i)		local highestInteger = expSearch(function (i)
	local ~~index~~ = ~~indexPrefix .. integerToAlpha~~(i)		local archive = integerToArchive(i)
	return mw.title.new(~~index~~).exists		return mw.title.new(archive).exists
	end)		end)
	local ~~highestIndex~~ = ~~indexPrefix .. integerToAlpha~~(highestInteger)		local highestArchive = integerToArchive(highestInteger)
	</source>		</source>

Mr. Stradivarius: add examples

2015-02-27T16:06:57Z

add examples

@@ Line 26: / Line 26: @@
 * <var>init</var> - the initial value of <var>i</var> to check. For advanced users. (optional)
-expSearch will return the highest value of <var>i</var> for which testFunc was truthy.
+expSearch will return the highest value of <var>i</var> for which testFunc was truthy. If no values were truthy, the function will return nil.
 <includeonly>{{#ifeq:{{SUBPAGENAME}}|sandbox | |

Mr. Stradivarius: create

2015-02-27T14:55:44Z

create

New page

This module provides a generic [[exponential search]] algorithm. This kind of search can be useful when you want to find a key in some kind of sorted array, and you want to do it by checking as few array elements as possible. This could include situations like:
* Finding the highest archive number in a set of archives without checking whether they all exist.
* Finding the number of positional arguments in frame.args without having to expand the wikitext for each of them.

You shouldn't use this module if any of the following apply:
# You can use the [[mw:Extension:Scribunto/Lua reference manual#Length operator|Lua length operator]] to find what you need.
# Your array has any gaps in. If you try and use this module on a sparse array, you might get an erroneous value.
# Your array has less then about 10 items in it. It's possible to use this module for those arrays, but you will access most of the array elements anyway (perhaps some of them twice), and your code will be more complicated than if you just used a for loop.

== Usage ==

First, load the module.

<source lang="lua">
local expSearch = require('Module:Exponential search')
</source>

You can then use the expSearch function with the following syntax:

<source lang="lua">
expSearch(testFunc, init)
</source>

Parameters:
* <var>testFunc</var> - a test function for your array. This function should take a positive integer <var>i</var> as its first parameter. If the element corresponding to <var>i</var> is not in the array, then the function should return false or nil; and if it ''is'' in the array, then the function should return a truthy value (anything other than false or nil). (required)
* <var>init</var> - the initial value of <var>i</var> to check. For advanced users. (optional)

expSearch will return the highest value of <var>i</var> for which testFunc was truthy.

<includeonly>{{#ifeq:{{SUBPAGENAME}}|sandbox | |


}}</includeonly>