LÖVE

Posted: **Mon Aug 17, 2015 7:15 pm**

Here are two functions to calculate the biggest and smallest numbers in a table:
(first function)

function getMaxMin90000(...)
	local atoms
	if type(select(1, ...)) == 'table' then
		atoms = select(1, ...)
	else
		atoms = {...}
	end
	local winners
	local biggest = {atoms[1],1}
	local smallest = {atoms[1],1}
	if #atoms/2 == math.floor(#atoms/2) then --is even
		for i = 1,#atoms-1,2 do
			winners = atoms[i] > atoms[i+1] and {i,i+1} or {i+1,i}
			if atoms[winners[1]] > biggest[1] then biggest = {atoms[winners[1]],winners[1]} end
			if atoms[winners[2]] < smallest[1] then smallest = {atoms[winners[2]],winners[2]} end
		end
	else
		for i = 1,#atoms-2,2 do
			winners = atoms[i] > atoms[i+1] and {i,i+1} or {i+1,i}
			if atoms[winners[1]] > biggest[1] then biggest = {atoms[winners[1]],winners[1]} end
			if atoms[winners[2]] < smallest[1] then smallest = {atoms[winners[2]],winners[2]} end
		end
		if atoms[#atoms] > biggest[1] then biggest = {atoms[#atoms],#atoms} end
		if atoms[#atoms] < smallest[1] then smallest = {atoms[#atoms],#atoms} end
	end

	return biggest,smallest
end

(second function)

Code: Select all

function getMaxMin(...)
	local list
	if type(select(1, ...)) == 'table' then
		list = select(1, ...)
	else
		list = {...}
	end
	local biggest = {list[1],1}
	local smallest = {list[1],1}
	for i,v in ipairs(list) do
		if v > biggest[1] then biggest = {v,i} elseif v < smallest[1] then smallest = {v,i} end
	end
	return biggest[1],smallest[1]
end

The reason why there are two functions is that the seconds function is sometimes faster than the first, weird right ?
But the first function (90000) is usualy faster.
Benchmark (excel):

Code: Select all

calculating 90000 function
calculated a table with	200000	indexes in	0.074	seconds
results	1234087	1545
calculating second function
calculated a table with	200000	indexes in	0.088	seconds
results	842234	1545
calculating 90000 function
calculated a table with	190000	indexes in	0.079	seconds
results	1234087	2298
calculating second function
calculated a table with	190000	indexes in	0.094	seconds
results	1133902	803102
calculating 90000 function
calculated a table with	180000	indexes in	0.074	seconds
results	1234087	2034
calculating second function
calculated a table with	180000	indexes in	0.083	seconds
results	1006448	111673
calculating 90000 function
calculated a table with	170000	indexes in	0.071	seconds
results	1234087	2072
calculating second function
calculated a table with	170000	indexes in	0.072	seconds
results	327034	935829
calculating 90000 function
calculated a table with	160000	indexes in	0.07	seconds
results	1234087	1997
calculating second function
calculated a table with	160000	indexes in	0.059	seconds
results	293212	469365
calculating 90000 function
calculated a table with	150000	indexes in	0.098	seconds
results	1234087	2599
calculating second function
calculated a table with	150000	indexes in	0.047	seconds
results	103199	348653
calculating 90000 function
calculated a table with	140000	indexes in	0.077	seconds
results	1234087	2562
calculating second function
calculated a table with	140000	indexes in	0.046	seconds
results	250539	404508
calculating 90000 function
calculated a table with	130000	indexes in	0.071	seconds
results	1234087	7232
calculating second function
calculated a table with	130000	indexes in	0.064	seconds
results	371025	503224
calculating 90000 function
calculated a table with	120000	indexes in	0.053	seconds
results	1234087	5499
calculating second function
calculated a table with	120000	indexes in	0.063	seconds
results	380252	1027577
calculating 90000 function
calculated a table with	110000	indexes in	0.043	seconds
results	1234049	7345
calculating second function
calculated a table with	110000	indexes in	0.053	seconds
results	355470	466879
calculating 90000 function
calculated a table with	100000	indexes in	0.038	seconds
results	1234087	8174
calculating second function
calculated a table with	100000	indexes in	0.046	seconds
results	769506	52541
calculating 90000 function
calculated a table with	90000	indexes in	0.038	seconds
results	1234087	6177
calculating second function
calculated a table with	90000	indexes in	0.041	seconds
results	1119665	742087
calculating 90000 function
calculated a table with	80000	indexes in	0.032	seconds
results	1234087	1997
calculating second function
calculated a table with	80000	indexes in	0.026	seconds
results	684951	892139
calculating 90000 function
calculated a table with	70000	indexes in	0.043	seconds
results	1234087	1620
calculating second function
calculated a table with	70000	indexes in	0.028	seconds
results	809768	696627
calculating 90000 function
calculated a table with	60000	indexes in	0.05	seconds
results	1234087	5537
calculating second function
calculated a table with	60000	indexes in	0.048	seconds
results	380064	389216
calculating 90000 function
calculated a table with	50000	indexes in	0.019	seconds
results	1234087	8023
calculating second function
calculated a table with	50000	indexes in	0.022	seconds
results	55027	1163543
calculating 90000 function
calculated a table with	40000	indexes in	0.016	seconds
results	1234049	3277
calculating second function
calculated a table with	40000	indexes in	0.013	seconds
results	407370	385224
calculating 90000 function
calculated a table with	30000	indexes in	0.018	seconds
results	1234049	19962
calculating second function
calculated a table with	30000	indexes in	0.013	seconds
results	1016090	950329
calculating 90000 function
calculated a table with	20000	indexes in	0.0070000000000001	seconds
results	1234049	14237
calculating second function
calculated a table with	20000	indexes in	0.0070000000000001	seconds
results	750185	84329
calculating 90000 function
calculated a table with	10000	indexes in	0.0060000000000002	seconds
results	1233899	16648
calculating second function
calculated a table with	10000	indexes in	0.0029999999999997	seconds
results	236340	61204

Posted: **Mon Aug 17, 2015 8:51 pm**

Ranguna, the second function is much better in terms of the code.
But you have a bug here:

Code: Select all

      if v < biggest[1] then biggest = {v,i} end

It should be "smallest" instead of "biggest".
Creating intermediate tables in this case would be slow too.

You may get performance differences depending on the input and
depending on if the GC is turned on (I would turn it OFF during the test).
Also, several simplifications are possible:

Code: Select all

    function getMaxMin(list, ...)
       if type(list) ~= "table" then
         list = { list, ... }
       end
       local first = list[1]
       local bI, bV = 1, first
       local sI, sV = 1, first
       for i = 2, #list do
          local v = list[i]
          if v > bV then bV, bI = v, i
          elseif v < sV then sV, sI = v, i end
       end
       return bV, sV, bI, sI
    end

PS. When you compare 2 functions head to head, make sure to "assert" that the output is the same for both.

Posted: **Mon Aug 17, 2015 9:20 pm**

How does it compare speed-wise to this, using your benchmarking method?

Code: Select all

function minMax( x, ... )
    if type( x )=="table" then
        return math.min( unpack( x ) ), math.max( unpack( x ) )
    else
        return math.min( x, ... ), math.max( x, ... )
    end
end

Posted: **Mon Aug 17, 2015 10:00 pm**

Good one, undef.
Your solution is probably the fastest.
assuming you don't need the 'index' for each item.
I'm not 100% sure, but there may be a limit
to the number of arguments you can 'unpack' too.

PS.Turns out that the limit is fairly large (~1 million, perhaps depending on the stack space?)
so yep, the most practical solution so far.

Posted: **Mon Aug 17, 2015 11:50 pm**

ivan wrote:PS.Turns out that the limit is fairly large (~1 million, perhaps depending on the stack space?)

Really ?
I can't unpack a table that has more than 7999 indexes :/

EDIT: Also, updated the first function, it had some bugs.

Posted: **Tue Aug 18, 2015 1:51 am**

All of our functions only work for lists though.
Here's another one if you don't care about mutating your table:

Code: Select all

function minMax( x, ... )
    if type( x )=="table" then
        table.sort( x )
        return x[1], x[#x]
    else
        return math.min( x, ... ), math.max( x, ... )
    end
end

This should circumvent the unpack limit I guess?

Posted: **Tue Aug 18, 2015 2:49 am**

Well, it does but I'm not going to write a list with 200000 numbers just to test this out so my benchmark only uses a table as an input. I ran the numbers and my second function is the fastest without the need to unpack the table, your first function is the best but it requires the table to be unpacked which limits how many numbers can be inputed.
Here's the sheet.

Posted: **Tue Aug 18, 2015 2:58 am**

Building on my reduce function from a few pages back:

Code: Select all

-- reduce(fn, predicate, initial)

listmax = partial(reduce, Math.max, -math.huge)
listmin = partial(reduce, Math.min, math.huge)

LÖVE

Small Useful Functions

Re: Small Useful Functions

Re: Small Useful Functions

Re: Small Useful Functions

Re: Small Useful Functions

Re: Small Useful Functions

Re: Small Useful Functions

Re: Small Useful Functions

Re: Small Useful Functions