Как реализовать функцию Foursquare «Mayor» - найти пользователя с наибольшим количеством очков за последние N дней? - PullRequest
Новая
       27

Как реализовать функцию Foursquare «Mayor» - найти пользователя с наибольшим количеством очков за последние N дней?

0 голосов
/ 10 сентября 2010

В Foursquare пользователь, набравший наибольшее количество баллов за место за последние N дней, получает статус мэра этого места.

Какой самый эффективный способ реализовать это?

Пользователь мог проверить сотни мест. Чтобы отобразить все должности мэров, которые принадлежат пользователю, необходимо пройти все эти сотни мест по одному и проверить, имеет ли он самый высокий балл за последние 60 дней для каждого места - это звучит очень неэффективно.

Есть ли какая-либо SQL или алгоритмическая магия, которая могла бы быстро выполнить задачу?

ОБНОВЛЕНИЕ: я использую MySQL и Django

1 Ответ

1 голос
/ 10 сентября 2010

Я бы оставил «текущий майор» в таблице мест и обновлял его время от времени.Пример (я понятия не имею, верна ли модель данных): 

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';
...