计算多个时间段的前 10 名或前 X 名列表的有效方法

Question

我想做的：计算最受欢迎的搜索查询：过去一天、过去 30 天、过去 60 天、过去 90 天、每个日历月和所有时间。

我的原始数据是带时间戳的搜索查询列表，并且我已经在运行一个夜间 cron 作业以进行相关数据聚合，因此我想将此计算集成到其中。通读每个查询对于每日计数来说很好（据我所知是必要的），但对于其他时间段，这将是一个昂贵的计算，所以我正在寻找一种方法来使用我的预先计算的数据来节省时间。

我不想做的是：提取该时间段内每天的记录，对所有计数求和，对整个结果列表进行排序，然后取前 X 个值。这将是低效的，特别是对于"所有时间"列表。

我

考虑使用堆和二叉树来保持实时排序和/或更快地访问数据，并行读取每个列表中的单词，并在各种约束和结束条件下将它们的值推入堆中，但这总是破坏查找时间或排序时间，我基本上回到了查看所有内容。

我还考虑过保留每个时间段的运行总计，添加最新一天并减去最早的一天（在每个月的 1 号保存每月总计），但是我必须每天保存每个时间段的完整计数（而不仅仅是前 X 个），我仍在查看每日总计中的每条记录。

有没有办法更快地执行此操作，也许使用其他一些数据结构或我不知道的有趣的数学属性？此外，任何人都需要知道，这整个事情都存在于 Django 项目中。

Answer 1

简短的回答是否定的。

不能保证上一年的十大歌曲曾经出现在前十名的每日名单上（很有可能，但不能保证）。

获得绝对确定的前十名的唯一方法是将指定时间段内的所有选票相加，然后选择前十名。

Answer 2

可以使用 Counter（） 类，这是高性能容器数据类型的一部分。创建所有搜索的字典作为字典的键，并计算其频率。

cnt = Counter()
for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
    cnt[word] += 1
print cnt
Counter({'blue': 3, 'red': 2, 'green': 1})

Answer 3

I'm not sure if it fits with what you're doing, but if the data is stored via a Django model, you can avail yourself of aggregation to get the info in a single query.

Given:

class SearchQuery(models.Model):
    query = models.CharField()
    date = models.DateTimeField()

然后：

import datetime
from django.db.models import Count
today = datetime.date.today()
yesterday = today - datetime.timedelta(days=1)
days_ago_30 = today - datetime.timedelta(days=30)
...
top_yesterday = SearchQuery.objects.filter(date__range=(yesterday, today)).annotate(query_count=Count('query')).order_by('-query_count')
top_30_days = SearchQuery.objects.filter(date__range=(days_ago_30, today)).annotate(query_count=Count('query')).order_by('-query_count')
...

这是使用Django完成的最高效的方法，但它不一定是最有效的。但是，执行诸如为query添加索引之类的操作将有很大帮助。

编辑

我只是想到，你最终会在列表中得到欺骗。从技术上讲，你可以在事后对列表进行重复数据删除，但是如果你运行Django 1.4+和PostgreSQL作为你的数据库，你可以简单地将.distinct('query')附加到这些查询集的末尾。