[google-appengine] Re: Pagination with Ranking
Hi Josh,
Seems like you can use the technique in the linked document, but
replace order("-when") with order("-score"), so I guess the real issue
is how to display the rank (I assume you mean first place, second
place, etc.). If displaying pages of players, I think you can just
use a counter (in Python code, not the data store) that increments
with each displayed name.
I guess the real challenge is, when talking to a specific player, how
do you tell them that they are ranked 5th. I'm pretty new to GAE,
but I'd probably use a query that selected records that were less than
the current user's score, and then get the count (ignoring ties).
http://code.google.com/appengine/docs/python/datastore/queryclass.html#Query_count
On Oct 2, 5:40 pm, Josh wrote:
> Hi all,
>
> I've seen a number of interesting discussions on how to do efficient
> pagination on appengine, but one thing that I haven't seen addressed,
> which I would like, is how to efficiently compute ranking information
> for the items that are paginated.
>
> Let me motivate this discussion by considering a leader board. We
> have a model like so:
>
> class Player(db.Model):
> name = db.StringProperty()
> score = db.IntegerProperty()
> last_updated = db.DateTimeProperty(auto_now=True)
>
> We may have hundreds of thousands of Players and we want to be able to
> rank them by their score.
>
> How could we used the previously discussed pagination techniques
> (http://code.google.com/appengine/articles/paging.html) to efficiently
> page through the leader board and not only show the Players in order
> by score, but also assign a rank value to each player.
>
> Many thanks for your thoughts and input.
>
> Cheers,
> Josh
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Google App Engine" group.
To post to this group, send email to google-appengine@googlegroups.com
To unsubscribe from this group, send email to
google-appengine+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-appengine?hl=en
-~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
And of course I just finished reading the fine print that says it'll
only return a maximum of 1000. Oh well, maybe I stirred some creative
juices in someone else.
On Oct 2, 8:04 pm, dburns wrote:
> Hi Josh,
>
> Seems like you can use the technique in the linked document, but
> replace order("-when") with order("-score"), so I guess the real issue
> is how to display the rank (I assume you mean first place, second
> place, etc.). If displaying pages of players, I think you can just
> use a counter (in Python code, not the data store) that increments
> with each displayed name.
>
> I guess the real challenge is, when talking to a specific player, how
> do you tell them that they are ranked 5th. I'm pretty new to GAE,
> but I'd probably use a query that selected records that were less than
> the current user's score, and then get the count (ignoring ties).
>
> http://code.google.com/appengine/docs/python/datastore/queryclass.htm...
>
> On Oct 2, 5:40 pm, Josh wrote:
>
> > Hi all,
>
> > I've seen a number of interesting discussions on how to do efficient
> > pagination on appengine, but one thing that I haven't seen addressed,
> > which I would like, is how to efficiently compute ranking information
> > for the items that are paginated.
>
> > Let me motivate this discussion by considering a leader board. We
> > have a model like so:
>
> > class Player(db.Model):
> > name = db.StringProperty()
> > score = db.IntegerProperty()
> > last_updated = db.DateTimeProperty(auto_now=True)
>
> > We may have hundreds of thousands of Players and we want to be able to
> > rank them by their score.
>
> > How could we used the previously discussed pagination techniques
> > (http://code.google.com/appengine/articles/paging.html) to efficiently
> > page through the leader board and not only show the Players in order
> > by score, but also assign a rank value to each player.
>
> > Many thanks for your thoughts and input.
>
> > Cheers,
> > Josh
>
>
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Google App Engine" group.
To post to this group, send email to google-appengine@googlegroups.com
To unsubscribe from this group, send email to
google-appengine+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-appengine?hl=en
-~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
HI dburns,
Thanks for your reply.
On Oct 2, 5:04 pm, dburns wrote:
> Seems like you can use the technique in the linked document, but
> replace order("-when") with order("-score"), so I guess the real issue
> is how to display the rank (I assume you mean first place, second
> place, etc.). If displaying pages of players, I think you can just
> use a counter (in Python code, not the data store) that increments
> with each displayed name.
>
> I guess the real challenge is, when talking to a specific player, how
> do you tell them that they are ranked 5th. I'm pretty new to GAE,
> but I'd probably use a query that selected records that were less than
> the current user's score, and then get the count (ignoring ties).
>
> http://code.google.com/appengine/docs/python/datastore/queryclass.htm...
The problem here is that count() won't return more than 1000.
It seems I'll have to store the rank with the user, but then the
challenge is inserting new users, or updating the ranks as scores
change.
Cheers,
Josh
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Google App Engine" group.
To post to this group, send email to google-appengine@googlegroups.com
To unsubscribe from this group, send email to
google-appengine+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-appengine?hl=en
-~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
On Sat, Oct 3, 2009 at 10:09 AM, Josh wrote: > The problem here is that count() won't return more than 1000. > > It seems I'll have to store the rank with the user, but then the > challenge is inserting new users, or updating the ranks as scores > change. Using the taskqueue API would be ideal here: every time you change someone's score you fire off a task that will recompute everyone's rank. There are obvious optimisations that you can make since you'll be effectively doing an incremental sort of a mostly-sorted list. Dave. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com To unsubscribe from this group, send email to google-appengine+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
Hi Josh, You might want to look into the 'ranklist' library. It'll allow you to keep a large (much larger than 1000) set of records in ranked order, and efficiently answer queries like 'what is the value of the 235th entry?' and 'where would a score of 500 place me?'. http://code.google.com/p/google-app-engine-ranklist/ -Nick Johnson On Fri, Oct 2, 2009 at 10:40 PM, Josh wrote: > > Hi all, > > I've seen a number of interesting discussions on how to do efficient > pagination on appengine, but one thing that I haven't seen addressed, > which I would like, is how to efficiently compute ranking information > for the items that are paginated. > > Let me motivate this discussion by considering a leader board. We > have a model like so: > > class Player(db.Model): > name = db.StringProperty() > score = db.IntegerProperty() > last_updated = db.DateTimeProperty(auto_now=True) > > We may have hundreds of thousands of Players and we want to be able to > rank them by their score. > > How could we used the previously discussed pagination techniques > (http://code.google.com/appengine/articles/paging.html) to efficiently > page through the leader board and not only show the Players in order > by score, but also assign a rank value to each player. > > Many thanks for your thoughts and input. > > Cheers, > Josh > > > > -- Nick Johnson, Developer Programs Engineer, App Engine Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration Number: 368047 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com To unsubscribe from this group, send email to google-appengine+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
I'd approach this by using some kind of a tree structure, with each node in the tree represented by an entity in the data store. Your player items would be in leaf nodes pointing at those interior node entities. Put a count in each node saying how many items are below that node. If you have the record for a player, and you know his parent node, you can compute his rank with O(lg N) datastore lookups, which you can probably get done before the deadline runs out. Whenever you need to change someone's position in the tree, you'd run through O(lg N) entities and update counters (in a transaction, of course). What kind of tree to use would require some study of the problem domain. Red/Black, B-tree, etc., etc. -Joshua --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com To unsubscribe from this group, send email to google-appengine+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
Thanks Nick. That library looks terrific. However, I notice that it primarily uses: from google.appengine.api import datastore for accessing the appengine datastore, where as most of the documentation at: http://code.google.com/appengine/docs/python/datastore/ uses: from google.appengine.ext import db I'm having trouble finding good documentation on google.appengine.api.datastore, can someone point me in the right direction? Thanks! Josh On Oct 5, 6:46 am, "Nick Johnson (Google)" wrote: > Hi Josh, > You might want to look into the 'ranklist' library. It'll allow you to keep > a large (much larger than 1000) set of records in ranked order, and > efficiently answer queries like 'what is the value of the 235th entry?' and > 'where would a score of 500 place me?'. > > http://code.google.com/p/google-app-engine-ranklist/ > > -Nick Johnson > > > > > > On Fri, Oct 2, 2009 at 10:40 PM, Josh wrote: > > > Hi all, > > > I've seen a number of interesting discussions on how to do efficient > > pagination on appengine, but one thing that I haven't seen addressed, > > which I would like, is how to efficiently compute ranking information > > for the items that are paginated. > > > Let me motivate this discussion by considering a leader board. We > > have a model like so: > > > class Player(db.Model): > > name = db.StringProperty() > > score = db.IntegerProperty() > > last_updated = db.DateTimeProperty(auto_now=True) > > > We may have hundreds of thousands of Players and we want to be able to > > rank them by their score. > > > How could we used the previously discussed pagination techniques > > (http://code.google.com/appengine/articles/paging.html) to efficiently > > page through the leader board and not only show the Players in order > > by score, but also assign a rank value to each player. > > > Many thanks for your thoughts and input. > > > Cheers, > > Josh > > -- > Nick Johnson, Developer Programs Engineer, App Engine > Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration Number: > 368047 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com To unsubscribe from this group, send email to google-appengine+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
count > 1000 split according to time or any, example improvable with
dynamical increment (make dependant dayinc)
def get(self):#sums > 1000
import time
from datetime import datetime, timedelta
inc = datetime.now ()-timedelta(days = 1000)
dayinc = 10 #ok while return < 1000 every 10 days
sum = 0
while(inc < datetime.now()):
ads = Ad.all().filter("modified <", inc + timedelta(days =
dayinc)).filter("modified >", inc).count()
inc = inc + timedelta (days = dayinc)
sum=sum+ads
self.response.out.write(sum)
and sorting in pure python with one's own order always works or use
the pattern called "comparable",
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Google App Engine" group.
To post to this group, send email to google-appengine@googlegroups.com
To unsubscribe from this group, send email to
google-appengine+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-appengine?hl=en
-~--~~~~--~~--~--~---
[google-appengine] Re: Pagination with Ranking
Hi Josh, The only official docs for the datastore module is in the docstrings in the source itself. Note, though, that just because ranklist uses the datastore module doesn't mean you have to! -Nick On Tue, Oct 6, 2009 at 6:25 PM, Josh wrote: > > Thanks Nick. > > That library looks terrific. > > However, I notice that it primarily uses: > > from google.appengine.api import datastore > > for accessing the appengine datastore, where as most of the > documentation at: > http://code.google.com/appengine/docs/python/datastore/ > > uses: > from google.appengine.ext import db > > I'm having trouble finding good documentation on > google.appengine.api.datastore, can someone point me in the right > direction? > > Thanks! > Josh > > > On Oct 5, 6:46 am, "Nick Johnson (Google)" > wrote: > > Hi Josh, > > You might want to look into the 'ranklist' library. It'll allow you to > keep > > a large (much larger than 1000) set of records in ranked order, and > > efficiently answer queries like 'what is the value of the 235th entry?' > and > > 'where would a score of 500 place me?'. > > > > http://code.google.com/p/google-app-engine-ranklist/ > > > > -Nick Johnson > > > > > > > > > > > > On Fri, Oct 2, 2009 at 10:40 PM, Josh wrote: > > > > > Hi all, > > > > > I've seen a number of interesting discussions on how to do efficient > > > pagination on appengine, but one thing that I haven't seen addressed, > > > which I would like, is how to efficiently compute ranking information > > > for the items that are paginated. > > > > > Let me motivate this discussion by considering a leader board. We > > > have a model like so: > > > > > class Player(db.Model): > > > name = db.StringProperty() > > > score = db.IntegerProperty() > > > last_updated = db.DateTimeProperty(auto_now=True) > > > > > We may have hundreds of thousands of Players and we want to be able to > > > rank them by their score. > > > > > How could we used the previously discussed pagination techniques > > > (http://code.google.com/appengine/articles/paging.html) to efficiently > > > page through the leader board and not only show the Players in order > > > by score, but also assign a rank value to each player. > > > > > Many thanks for your thoughts and input. > > > > > Cheers, > > > Josh > > > > -- > > Nick Johnson, Developer Programs Engineer, App Engine > > Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration > Number: > > 368047 > > > -- Nick Johnson, Developer Programs Engineer, App Engine Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration Number: 368047 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com To unsubscribe from this group, send email to google-appengine+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~--~~~~--~~--~--~---
