Page 1 of 1
Sorting a list for max value
Posted: 09 Feb 2011, 05:24
by bobthedinosaur
I can of modified an example I saw elsewhere.
What I want to find the teamID entry with the highest score. Would this work for lets say list score where score[teamID] - score values (in numbers)?
Code: Select all
local function findwinner(score)
local winner = 1 --index of max value
local m = score[winner] --max value
for i, val in ipairs(score) do --can use pairs() as well, ipairs() indicates an array-like table
if val > m then
winner = i
m = val
end
end
return m, winner --neat feature of lua, can return multiple values
end
Re: Sorting a list for max value
Posted: 09 Feb 2011, 05:49
by knorke
your code should work i think, whats wrong with it?
it can only find one winner though, does not work for a tie.
If you use better names for your variables, it gets much easier to read your code. ie "m" -> highestscore_sofar etc
---
spring tanks -> gadgets\tp_gamelogic.lua
Code: Select all
function winningteams(score)
local highestscore=0
for teamid,_ in pairs (score) do
if (score[teamid] > highestscore) then highestscore=score[teamid] end
end
local winners = {}
for teamid,_ in pairs (score) do
if (score[teamid] == highestscore) then table.insert(winners,teamid) end
end
return winners
end
In the first loop I look for the highest score.
In the second loop I check which team's score is equal to the highest score.
It is in two loops because multiple teams might have the same score (tie)
Re: Sorting a list for max value
Posted: 09 Feb 2011, 05:56
by SpliFF
Code: Select all
local teams = {'team1','team2','team3'}
local scores = {
team1 = 100,
team2 = 200,
team3 = 300
}
-- Returns a shallow copy of t so changes to basic values won't affect the original (see also deepcopy).
function table.copy(t)
local copy = {}
for k,v in pairs(t) do
copy[k] = v
end
return copy
end
-- returns a copy of teams sorted
local function SortTeamsByScore()
-- a local function inside a function for speed
local function HighestScore(teamA,teamB)
return scores[teamA] > scores[teamB]
end
local sortedTeams = table.copy(teams)
table.sort(sortedTeams, HighestScore)
return sortedTeams
end
This code may look complicated but the key to it is the built-in Lua function table.sort. This function takes an array and a comparison function and runs the comparison on pairs of values to determine which comes first. It is the fastest method, especially on large lists.
The table copy stuff is only relevant if you don't want to change the order in the original table - otherwise just sort teams 'in-place' for even more speed.
Method 2:
If you are only interested in the highest score there is an even faster way
Code: Select all
local teamScores = {
[100] = 'team1',
[300] = 'team2',
[200] = 'team3'
}
local scores = {100,300,200}
local highestScore = math.max(unpack(scores))
local bestTeam = teamScores[highestScore]
This works because math.max can take an unlimited number of arguments and unpack converts the table into arguments. It fails in the event of 2 teams having the same score.
Re: Sorting a list for max value
Posted: 09 Feb 2011, 06:07
by knorke
SpliFF:
what if there is a tie?
Re: Sorting a list for max value
Posted: 09 Feb 2011, 06:11
by SpliFF
in a tie it returns one of the tied teams (the last one written to the list).
Re: Sorting a list for max value
Posted: 09 Feb 2011, 06:49
by knorke
yes, thats what i meant.
It should not declare a "random" team as winner.
Re: Sorting a list for max value
Posted: 09 Feb 2011, 21:32
by CarRepairer
Be careful with these solutions. In my experience this won't work correctly (but someone correct me if I'm wrong). The reason being, you should only sort an ordered table (the kind you use with ipairs() ). If your table is indexed by teamID (you use pairs() on it), and then the table you're getting back will not output sorted when you run it through pairs().
What I do is first put the key and value of the table into a new table like so:
Code: Select all
table2 = {}
for k,v in pairs(table1)
table2[#table2+1] = {k,v}
end
then sort table2 with this method:
Code: Select all
local function Sortfunc(v1,v2)
return v1[2] > v2[2]
end
table.sort(table2, Sortfunc)
then use ipairs() on the new table:
Code: Select all
for _,val in ipairs(table2) do
local k, v = val[1], val[2]
-- do stuff with k and v which correspond to table1.
end
Re: Sorting a list for max value
Posted: 09 Feb 2011, 23:23
by jK
what car said is true.
Tables in Lua are split in 2 parts: an array (index:1..n) and a list (= hashtable).
Now iterating the array is 'stable'. But the list one is NOT, that's because it uses the hashvalues of indices to find the values in it and those can differ between run instances. E.g. the hash of a table is the pointer to the memory location in RAM, and this obviously runtime dynamic. That's why you should NEVER EVER use pairs() on tables with tables as indices in synced code!!!
So if you need an ordered table then use only indices 1..n w/o any holes in it (cause of: 1..3 + 5..7 = array<1,2,3> + hashtable<5,6,7>).
Re: Sorting a list for max value
Posted: 10 Feb 2011, 17:50
by knorke
That all seems very complicated, tables in tables just to find player with highest score at game end?
Is there something similiar wrong with my version? So far it doesnt look like it.
Re: Sorting a list for max value
Posted: 24 Aug 2011, 17:46
by Jools
Can't you just use dictionary tables all the way and not iterate but lookup each time? The problem with ipairs is that it starts on 1, and that prevents you from making a table indexed by player id for example, because then it missed player id 0. Of course you could add 1 to each player id to get index, but then you can't copy and paste objects from one code to another.