开发者

How to implement Foursquare's "Mayor" feature - find the user with the highest score in the last N days?

In Foursquare, the user who has the highest score开发者_如何转开发 for a place in the last N days is awarded the Mayorship of that place.

What is the most efficient way to implement that?

A user could have checked into hundreds of places. To display all the mayorships that belong to a user, it'd be necessary to go through all those hundreds of places one by one and check if he has the highest score in the last 60 days for each place-- that sounds very inefficient.

Is there any SQL or algorithmic magic that could perform the task quickly?

UPDATE: I'm using MySQL and Django


I would keep the 'current major' in the place table, and update that from time to time. Example (I have no idea if the data model is correct):

drop table place;
create table place(name varchar(20) primary key, major varchar(20));
insert into place values('NY', null), ('LA', null);
create index idx_p_m on place(major);

drop table visits;
create table visits(user varchar(20), place varchar(20), points int, day int);
create index idx_v_p on visits(place, day desc);
insert into visits values
  ('Ben', 'NY', 1, 100), 
  ('Ben', 'LA', 3, 102), 
  ('Joe', 'NY', 2, 103), 
  ('Joe', 'LA', 1, 104);

-- just to prove this is efficient  
explain  select user from visits v where v.place = 'NY' 
  and day > 90
  group by user 
  order by sum(points) desc 
  limit 1;

update place p set major = 
  (select user from visits v where p.name = v.place 
  and day > 90
  group by user 
  order by sum(points) desc 
  limit 1);

select * from place where major = 'Joe';
select * from place where name = 'LA';
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜