Page 13 of 13

### Re: Small Useful Functions

Posted: Mon Aug 17, 2015 7:15 pm
Here are two functions to calculate the biggest and smallest numbers in a table:
(first function)

Code: Select all

``````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``````

### Re: Small Useful Functions

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.

### Re: Small Useful Functions

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
``````

### Re: Small Useful Functions

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.

### Re: Small Useful Functions

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.

### Re: Small Useful Functions

Posted: Tue Aug 18, 2015 1:51 am
All of our functions only work for lists though.

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?

### Re: Small Useful Functions

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.

### Re: Small Useful Functions

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)
``````