Sorting a list for max value

[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

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

[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.

[knorke]

SpliFF:
what if there is a tie?

[SpliFF]

in a tie it returns one of the tied teams (the last one written to the list).

[knorke]

yes, thats what i meant.
It should not declare a "random" team as winner.

[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

[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>).

[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.

[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.