How would you do it? - Erlang Programming

The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion How would you do it?
Received-SPF: pass (google.com: domain of erlang-questions-boun...@erlang.org designates 192.121.151.104 as permitted sender) client-ip=192.121.151.104;
MIME-version: 1.0
From: Rudolph van Graan <rvg.mail...@me.com>
Date: Fri, 06 Jul 2012 13:46:09 +0100
References: <EF9FBE4B-70EB-4106-8D1B-05E5D7216...@me.com>
To: erlang-questions Questions <erlang-questi...@erlang.org>
Message-id: <924C63BF-9335-4E10-B34F-3D6D1B16B...@me.com>
Subject: [erlang-questions]  How would you do it?
Precedence: list
Content-Type: multipart/mixed; boundary="===============6468803162825097617=="
Errors-To: erlang-questions-boun...@erlang.org
Sender: erlang-questions-boun...@erlang.org


--===============6468803162825097617==
Content-type: multipart/alternative;
 boundary="Boundary_(ID_sIPv+q4N48hbntxN9N5Htg)"


--Boundary_(ID_sIPv+q4N48hbntxN9N5Htg)
Content-type: text/plain; CHARSET=US-ASCII
Content-transfer-encoding: 7BIT

> I have to rank about 50 000 - 100 000 different players.
> On each score message I have to re-sort whole ranking table.
> It must be very cheap to get:
> top 100 players
> player's rating +/- 10 players about current player
> I expect about 20-50 score messages per seconds
> Size of score message is about 4KB (profile takes most of the space).
Trying to be pragmatic, I would do this:

1. Every player has a unique key (say ID) and this is the key to a Mnesia table that stores the player records.
2. I would have a second table with the rankings, keyed on score.
3. Each slot contains the ID and score of the player at that position: 
- {score,30,{player,200},undefined,20}
- {score,20,{player,5},30,19}
- {score,19,{player,18},20,undefined}
...
So the top player is the one with rank 30, i.e. player 200, the 2nd one is player 5 and the third is player 18. You can get to the first one by reading the first entry or last entry in the table. Each score record contains a "pointer" to the one before and the one after.

The record will look like this:

{score, Score, PlayerID, Next, Previous}

4. The player table is keyed on the player id and contains the player's current score. So in the example above Player 200 will be rank 1 (score 30) and Player 5 will be rank 2 (score 20) etc.

So you can easily get the top N, simply read the records starting at the end (using dirty last) and following the next pointer. That will give you two database reads per entry. If you want to cache this, make a simple gen_server that keeps this list in memory and refreshes every 10 seconds.

4. Process your score messages concurrently, i.e. each operation does the folling
 a) Read the player record according to ID and get the score from the player ID. 
 b) Read the score record using the current score and retrieve the values of "previous" and "next"
 c) Delete the score record and modify "previous" to point to "next" and "next" to point to previous
 d) Insert a new #score{score=NewScore,previous=undefined, next=undefined}
 e) Call mnesia:next(Tab,{score,NewScore}) to get the logical Next and mnesia:prev/2 to get the logical previous
 f) Update the three records with the appropriate next/prev values

(all of this protected by a transaction of course)

This approach is heavy compared to the other approaches suggested, but it gives you distribution for free and no single process bottlenecks. It should be very fast if you use only memory tables and fast enough if you add persistent tables.

Obviously I haven't worked out all the details above - I am sure you can figure that out.

Hope it helps.
Rudolph van Graan

Please have a look at my blogs:

- Random Views of London -- A photographer's interpretation of London
  http://randomlondonview.blogspot.co.uk/


On 2 Jul 2012, at 11:29, Max Bourinov wrote:

> Hi Erlangers,
> 
> I need to build a ranking system for online game.
> 
> I think I will have a ranking gen_server that will accept cast messages like this: {score, Player :: profile(), Score :: integer()}.
> 
> So, the question is what would be most appropriate data structure if:
> I have to rank about 50 000 - 100 000 different players.
> On each score message I have to re-sort whole ranking table.
> It must be very cheap to get:
> top 100 players
> player's rating +/- 10 players about current player
> I expect about 20-50 score messages per seconds
> Size of score message is about 4KB (profile takes most of the space).
> 
> Any ideas or suggestions are welcome!
> 
> Best regards,
> Max
> 
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questi...@erlang.org
> http://erlang.org/mailman/listinfo/erlang-questions



--Boundary_(ID_sIPv+q4N48hbntxN9N5Htg)
Content-type: text/html; CHARSET=US-ASCII
Content-transfer-encoding: quoted-printable

<html><head></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
"><div><div style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =
-webkit-line-break: after-white-space; "><blockquote =
type=3D"cite"><div><ol><li>I have to rank about 50 000 - 100 000 =
different players.</li><li>On each score message I have to re-sort whole =
ranking table.</li><li>It must be very cheap to get:</li><ol><li>top 100 =
players</li><li>player's rating +/- 10 players about current =
player</li></ol><li>I expect about 20-50 score messages per =
seconds</li><li>Size of score message is about 4KB (profile takes most =
of the space).</li></ol></div></blockquote><div>Trying to be =
pragmatic,&nbsp;I would do this:</div><div><br></div><div>1. Every =
player has a unique key (say ID) and this is the key to a Mnesia table =
that stores the player records.</div><div>2. I would have a second table =
with the rankings, keyed on score.</div><div>3. Each slot contains the =
ID and score of the player at that position:&nbsp;</div><div>- =
{score,30,{player,200},undefined,20}</div><div><div>- =
{score,20,{player,5},30,19}</div></div><div>- =
{score,19,{player,18},20,undefined}</div><div>...</div><div>So the top =
player is the one with rank 30, i.e. player 200, the 2nd one is player 5 =
and the third is player 18. You can get to the first one by reading the =
first entry or last entry in the table. Each&nbsp;score&nbsp;record =
contains a "pointer" to the one before and the one =
after.</div><div><br></div><div>The record will look like =
this:</div><div><br></div><div>{score, Score, PlayerID, Next, =
Previous}</div><div><br></div><div>4. The player table is keyed on the =
player id and contains the player's current score. So in the example =
above Player 200 will be rank 1 (score 30) and Player 5 will be rank 2 =
(score 20) etc.</div><div><br></div><div>So you can easily get the top =
N, simply read the records starting at the end (using dirty last) and =
following the next pointer. That will give you two database reads per =
entry. If you want to cache this, make a simple gen_server that keeps =
this list in memory and refreshes every 10 =
seconds.</div><div><br></div><div>4. Process your score messages =
concurrently, i.e. each operation does the folling</div><div>&nbsp;a) =
Read the player record according to ID and get the score from the player =
ID.&nbsp;</div><div>&nbsp;b) Read the score record using the current =
score and retrieve the values of "previous" and =
"next"</div><div>&nbsp;c) Delete the score record and modify "previous" =
to point to "next" and "next" to point to previous</div><div>&nbsp;d) =
Insert a new #score{score=3DNewScore,previous=3Dundefined, =
next=3Dundefined}</div><div>&nbsp;e) Call =
mnesia:next(Tab,{score,NewScore}) to get the logical Next and =
mnesia:prev/2 to get the logical previous</div><div>&nbsp;f) Update the =
three records with the appropriate next/prev =
values</div><div><br></div><div>(all of this protected by a transaction =
of course)</div><div><br></div><div>This approach is heavy compared to =
the other approaches suggested, but it gives you distribution for free =
and no single process bottlenecks. It should be very fast if you use =
only memory tables and fast enough if you add persistent =
tables.</div><div><br></div><div>Obviously I haven't worked out all the =
details above - I am sure you can figure that =
out.</div><div><br></div><div>Hope it helps.<br><div =
apple-content-edited=3D"true">
<span class=3D"Apple-style-span" style=3D"border-collapse: separate; =
font-family: 'Courier New'; font-style: normal; font-variant: normal; =
font-weight: normal; letter-spacing: normal; line-height: normal; =
orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: =
none; white-space: normal; widows: 2; word-spacing: 0px; =
-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =
0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =
auto; -webkit-text-stroke-width: 0px; font-size: medium; "><span =
class=3D"Apple-style-span" style=3D"border-collapse: separate; =
font-family: 'Courier New'; font-style: normal; font-variant: normal; =
font-weight: normal; letter-spacing: normal; line-height: normal; =
orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: =
none; white-space: normal; widows: 2; word-spacing: 0px; =
-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =
0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =
auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div =
style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =
-webkit-line-break: after-white-space; "><span class=3D"Apple-style-span" =
style=3D"orphans: 2; text-align: -webkit-auto; text-indent: 0px; widows: =
2; -webkit-text-decorations-in-effect: none; "><div =
style=3D"border-collapse: separate; font-style: normal; font-variant: =
normal; font-weight: normal; letter-spacing: normal; line-height: =
normal; text-transform: none; white-space: normal; word-spacing: 0px; =
-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =
0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; =
word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space; "><span class=3D"Apple-style-span" =
style=3D"border-collapse: separate; font-style: normal; font-variant: =
normal; font-weight: normal; orphans: 2; text-align: -webkit-auto; =
text-indent: 0px; text-transform: none; white-space: normal; widows: 2; =
word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; =
-webkit-border-vertical-spacing: 0px; =
-webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =
auto; -webkit-text-stroke-width: 0px; "><div style=3D"color: rgb(0, 0, =
0); font-family: 'Courier New'; font-size: medium; word-wrap: =
break-word; -webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space; "><span class=3D"Apple-style-span" =
style=3D"font-family: 'Courier New'; font-size: medium; letter-spacing: =
normal; line-height: normal; border-collapse: separate; font-style: =
normal; font-variant: normal; font-weight: normal; orphans: 2; =
text-align: -webkit-auto; text-indent: 0px; text-transform: none; =
white-space: normal; widows: 2; word-spacing: 0px; =
-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =
0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =
auto; -webkit-text-stroke-width: 0px; "><div style=3D"word-wrap: =
break-word; -webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space; "><div><p style=3D"font-family: Arial; font-size: =
11px; line-height: 1.4em; margin-top: 10px; margin-right: 0px; =
margin-bottom: 0px; margin-left: 0px; letter-spacing: 1px; color: rgb(0, =
105, 141); font-weight: bold; "><span class=3D"Apple-style-span" =
style=3D"font-weight: normal; ">Rudolph van =
Graan</span></p></div></div></span><span class=3D"Apple-style-span" =
style=3D"font-family: 'Courier New'; letter-spacing: normal; =
line-height: normal; font-size: 11px; "><a><font =
class=3D"Apple-style-span" color=3D"#00698D" face=3D"Arial"><span =
class=3D"Apple-style-span" style=3D"letter-spacing: 1px; line-height: =
15px; "><font class=3D"Apple-style-span" size=3D"2"><span =
class=3D"Apple-style-span" style=3D"font-size: 10px; =
"></span></font></span></font></a><font class=3D"Apple-style-span" =
color=3D"#00698D" face=3D"Arial"><font class=3D"Apple-style-span" =
size=3D"2"><div><a><span class=3D"Apple-style-span" style=3D"font-size: =
11px; "></span></a><a><font class=3D"Apple-style-span" color=3D"#00698D" =
face=3D"Arial"><span class=3D"Apple-style-span" style=3D"letter-spacing: =
1px; line-height: 15px; "><font class=3D"Apple-style-span" =
size=3D"2"><span class=3D"Apple-style-span" style=3D"font-size: 10px; =
"><br></span></font></span></font></a></div></font></font></span></div></s=
pan></div></span><span class=3D"Apple-style-span" style=3D"font-family: =
Arial; font-size: small; ">Please have a look at my blogs:</span><span =
class=3D"Apple-style-span" style=3D"orphans: 2; text-align: =
-webkit-auto; text-indent: 0px; widows: 2; =
-webkit-text-decorations-in-effect: none; "><div style=3D"border-collapse:=
 separate; font-variant: normal; font-weight: normal; letter-spacing: =
normal; line-height: normal; text-transform: none; white-space: normal; =
word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; =
-webkit-border-vertical-spacing: 0px; -webkit-text-size-adjust: auto; =
-webkit-text-stroke-width: 0px; word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
font-style: normal; "><span class=3D"Apple-style-span" =
style=3D"border-collapse: separate; font-variant: normal; font-weight: =
normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; =
text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; =
-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =
0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =
auto; -webkit-text-stroke-width: 0px; font-style: normal; "><div =
style=3D"font-family: 'Courier New'; font-size: medium; word-wrap: =
break-word; -webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space; "><span class=3D"Apple-style-span" =
style=3D"font-family: 'Courier New'; letter-spacing: normal; =
line-height: normal; font-size: 11px; "><font class=3D"Apple-style-span" =
face=3D"Arial"><font class=3D"Apple-style-span" =
size=3D"2"><br></font></font></span></div></span><span =
class=3D"Apple-style-span" style=3D"font-family: Arial; font-size: =
small; ">-&nbsp;<a href=3D"http://randomlondonview.blogspot.co.uk/">Random=
 Views of London</a>&nbsp;-- A photographer's interpretation of =
London</span></div><div style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><font =
class=3D"Apple-style-span" face=3D"Arial" size=3D"2">&nbsp;<span =
class=3D"Apple-converted-space">&nbsp;</span></font><font =
class=3D"Apple-style-span" face=3D"Arial" size=3D"1"><a =
href=3D"http://randomlondonview.blogspot.co.uk/">http://randomlondonview.b=
logspot.co.uk/</a></font></div></span><div style=3D"border-collapse: =
separate; font-style: normal; font-variant: normal; font-weight: normal; =
letter-spacing: normal; line-height: normal; text-transform: none; =
white-space: normal; word-spacing: 0px; =
-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =
0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; =
word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: =
after-white-space; "><font class=3D"Apple-style-span" color=3D"#00698d" =
face=3D"Arial" =
size=3D"2"><br></font></div></div></span><br></span></div><div><div>On 2 =
Jul 2012, at 11:29, Max Bourinov wrote:</div><br =
class=3D"Apple-interchange-newline"><blockquote type=3D"cite">Hi =
Erlangers,<div><br></div><div>I need to build a ranking system for =
online game.</div><div><br></div><div>I think I will have a ranking =
gen_server that will accept cast messages like this: {score, Player :: =
profile(), Score :: integer()}.</div>

<div><br></div><div>So, the question is what would be most appropriate =
data structure if:</div><div><ol><li>I have to rank about 50 000 - 100 =
000 different players.</li><li>On each score message I have to re-sort =
whole ranking table.</li>

<li>It must be very cheap to get:</li><ol><li>top 100 =
players</li><li>player's rating +/- 10 players about current =
player</li></ol><li>I expect about 20-50 score messages per =
seconds</li><li>Size of score message is about 4KB (profile takes most =
of the space).</li>

</ol><div><br></div></div><div>Any ideas or suggestions are =
welcome!</div><div><br></div><div><div>Best =
regards,</div><div>Max</div><br><br>
</div>
_______________________________________________<br>erlang-questions =
mailing list<br><a =
href=3D"mailto:erlang-questi...@erlang.org">erlang-questi...@erlang.org</a=
><br><a =
href=3D"http://erlang.org/mailman/listinfo/erlang-questions">http://erlang=
.org/mailman/listinfo/erlang-questions</a><br></blockquote></div><br></div=
></div></div><br></body></html>=

--Boundary_(ID_sIPv+q4N48hbntxN9N5Htg)--

--===============6468803162825097617==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
erlang-questions mailing list
erlang-questi...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

--===============6468803162825097617==--
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
Account Options
