Can someone help em think of a efficient way to do this elo ranking algorithm?

My friend wants me to code a elo ranking system that works like this:

code:



Your skill points = Kills/Deaths (800)+Wins/Losses(200)

Condensed Alternate Tiers	 	 
Percentile	Tier	Title
<2.50%	Elite	Elite
<6.00%	Tier 00	Tier 00
<10.00%	Tier 0	Purple I
<15.00%	Tier 1	Purple II
<21.00%	Tier 2	Purple III
<29.00%	Tier 3	Green I
<38.00%	Tier 4	Green II
<52.00%	Tier 5	Green III
<75.00%	Tier 6	Red I
<90.00%	Tier 7	Red II
<100.00%	Tier 8	Red III



Now the issue comes in play when I have to set their ranks because I have too get a list of all the players and then get the top 2% and set it down the list that way. The players rank is based on ALL of the players that have ever joined the server, meaning when I ahev to get the table of players it could get insane. The order of the list MUST BE ORGANIZED BEFORE THE PERCENTILES ARE DONE.

Do you know of some like mathematical equation I could do to quickly get the rank in BigO(1)?

Well, to be pedantic that’s not an Elo system. Elo systems are based on relative performance, not absolute, and as such don’t work well in non-1v1 games.

But anyways, if you keep a sorted list of players by skill points (qsort is O(n log n) average), you can get their rank fairly easily. Find the player who just barely meets the threshold (given a sorted list, that’s O(1)) and look up how many points he has. If a player has more than that, they’re in that tier. So it’s O(n) for the number of tiers, not the number of players, and with a low, static number of tiers that’s essentially O(1).

If you still need faster performance, re-calculate those thresholds every minute instead of every time someone scores. And if that’s still not enough, only re-rank players at the end of a match. Although honestly, if you’re having performance issues with this, you’re doing something wrong.

Well the sorting isn’t the issue because all of this is gonna be saved in a mysql database. The way I have it right now is it only sets values on disconnect or on match end. You only retrieve data on the join.Because its saved in a mysql database I would then need to get a huge table of players every time the game starts to set their ranks correctly.

The last time I did saving of mysql data constantly every kill, it caused the server to start having really bad performance which is why I am not doing it that way.

If the problem is the table being too big to store the result set in-memory, try using LIMIT 1 OFFSET <x> for whatever offset you need to find the 2.5% user to use as a threshold, etc.

This will still involve a partial table scan, since MySQL will still read through the whole table until getting to that row, but it should at least cut down on memory if that’s your problem.

You might have to change your whole algorithm, though. One extremely fast method might be to take the top player’s point total, and use simple subdivisions of that to determine tiers (eg. if M is the points of the top player, tier 1 would be P>M0.975, tier 2 would be P>M.94, etc). That will be much less statistically rigorous, but also faster to compute.

An actual Elo-like system might also be faster, but would discard your entire point system. Start all players with some default. After every round, take the average score of the winning team (W) and losing team (L). Add points to any players on the winning team who are below L, and remove an equal number of points from any players on the losing team who are above W. I don’t know specifics of your game more so details of figuring out how many points to give and take away are left to you, but as long as point totals are conserved (losers lose as many points as winners win), you can figure out tiers based purely on the distance of a particular player’s point total from the starting value, without needing to look at the scores of other players.

To solve your issue, you could count the table, then get each players rank and compare the two. The solution above is probably a faster way to the same end, though.