database - 如何找到数据点最多的一小时时段？

Question

我有一个包含数十万个论坛帖子的数据库表，我想找出一个小时的时间段包含的帖子数量最多。

我可以一次向前爬行一分钟，保留一系列时间戳并跟踪其中最多的时间，但我觉得有更好的方法来做到这一点。我将在一年的帖子上运行此操作，因此检查一年中的每一分钟似乎非常糟糕。

理想情况下，有一种方法可以在单个数据库查询中执行此操作。

Answer 1

给定一个包含您感兴趣的一年中每一分钟的Minutes表格和一个Posts包含一Time列的表格：

select top 1 minutes.time, count (posts.time)
from Minutes
   left join posts on posts.time >= minutes.time AND posts.time < dateadd(hour, 1, Minutes.Time)
group by minutes.time
order by count (posts.time) desc

要解决生成分钟表的问题，可以使用ufn_GenerateIntegers 之类的函数。 那么函数就变成了

select top 5 minutes.time, count (posts.time)
from (select dateadd(minute, IntValue, '2008-01-01') as Time from ufn_GenerateIntegers(525600)) Minutes
   left join posts on posts.time >= minutes.time AND posts.time < dateadd(hour, 1, Minutes.Time)
group by minutes.time
order by count(posts.time) desc

我刚刚用大约 5000 个随机帖子进行了测试，在我的机器上花了 16 秒。因此，对于偶尔的一次性查询来说，这不是微不足道的，但也不是荒谬的。幸运的是，这是一个数据点，您可以每天计算一次，甚至每月计算一次，如果您想频繁显示该值，可以将其缓存。

看看lassevk的改进。

Answer 2

如果您想查看诸如 10:00 - 11:00 之类的时间间隔，则分档将起作用。但是，如果您在 10:30 - 11:30 之间突然产生了兴趣，那么它将被分成两个垃圾箱，因此可能会被恰好在一个时钟小时内完全适合的较少点击量隐藏。

避免这个问题的唯一方法是生成一个按时间排序的列表并逐步执行。像这样的东西：

max = 0; maxTime = 0
for each $item in the list:
   push $item onto queue
   while head of queue is more than an hour before $item
      drop queue head.
   if queue.count > max then max = queue.count; maxTime = $item.time

这样你只需要在内存中保存一个 1 小时的窗口而不是整个列表。

Answer 3

将每个帖子的时间戳视为一个小时的开始，并计算该小时内的所有其他帖子，包括开始它的帖子。根据每个小时的帖子数，按降序对生成的小时数进行排序。

完成此操作后，您会发现其中帖子最多的单个“小时”，但这段时间可能不完全是一小时，它可能更短（但永远不会更长）。

要获得“更漂亮”的时期，您可以计算它的实际长度，除以 2，然后将时期的开始向后调整该数量，并将结束向前调整，这将在一小时内“居中”帖子。此调整保证不包括任何新帖子，因此计数仍然有效。如果帖子足够接近以至于在您将其扩展到一小时后突然被包含在该时段中，那么较早的时间点将包含“最多帖子”而不是您选择的那个。

如果这是一个 SQL 问题，您可以重用 Josh 在此处发布的 SQL ，只需将 Minutes 表替换为您的帖子表的另一个链接。

---

您可以使用的另一种方法是使用滑动窗口。

首先根据时间戳对所有帖子进行排序。使用列表跟踪帖子，可以使用链接列表。

现在，对于每个帖子，将其添加到列表的末尾。然后，对于列表开头的每个帖子，如果该帖子比您刚刚添加的帖子早一个多小时，请将其从列表中删除。

在对列表中的单个新帖子执行该 2 步操作后，检查列表中的帖子数量是否超过以前的最大值，如果是，则复制列表或至少存储该帖子你刚刚添加。

完成后，您将获得一小时内帖子最多的“列表副本”，或者您获得了包含最多帖子的 1 小时窗口结束的帖子。

伪代码：

initialize posts-window-list to empty list
for each post in sorted-posts-list:
    add post to end of posts-window-list
    for each other-post from start of posts-window-list:
        if other-post is more than one hour older than post, remove it
        otherwise, end this inner loop
    if number of posts in list is more than previous maximum:
        make copy of list, this is the new maximum

Answer 4

这适用于一个小型测试 MS-SQL 数据库。

SELECT TOP 1 id, date_entered,
  (SELECT COUNT(*)
   FROM   dbo.notes AS n2
   WHERE n2.date_entered >= n.date_entered 
   AND n2.date_entered < Dateadd(hh, 1, n.date_entered)) AS num
FROM  dbo.notes n
ORDER BY num DESC

这不是很有效，根据每个帖子的一个小时进行检查。

For MYSQL 

SELECT ID,f.Date, (SELECT COUNT(*)
FROM Forum AS f2
WHERE f2.Date >= f.Date AND f2.Date < Date_ADD(f.Date, INTERVAL 1 HOUR)) As num
FROM Forum AS f
ORDER BY num
LIMIT 0,1

Answer 5

这导致 O(n) 数据库查询和 O(n) 最大时间搜索，总复杂度为 O(2n)（当然，仍然是 O(n)）：

在 SQL 中使用 count distinct 命令，它会以分钟的增量为您“装箱”项目。

因此，您将在此表上运行计数查询：

time
1
2      
4
3
3
2
4
1
3
2

它会返回：

0 1
1 1
2 3
3 3
4 2

通过计算每个项目。

我怀疑你可以对你的桌子做同样的事情，并按分钟将它们装箱，然后在上面运行一个算法。

SELECT customer_name, COUNT(DISTINCT city) as "Distinct Cities"
FROM customers
GROUP BY customer_name;

从本教程计数：http ://www.techonthenet.com/sql/count.php （接近尾声）。

这是 MySQL 手册中的一个类似页面：http: //dev.mysql.com/doc/refman/5.1/en/counting-rows.html

因此，如果您有一个包含时间日期的表（到分钟，允许按分钟进行分箱）：

datetime (yyyymmddhhmm)
200901121435
200901121538
200901121435
200901121538
200901121435
200901121538
200901121538
200901121435
200901121435
200901121538
200901121435
200901121435

然后是 SQL

SELECT datetime, COUNT(DISTINCT datetime) as "Date Time"
FROM post
GROUP BY datetime;

应该返回

200901121435 7
200901121538 5

您仍然需要对此进行后期处理，但是分组和计数的艰苦工作已经完成，并且每年只会产生超过 50 万行（60 分钟、24 小时、365 天）

后处理将是：

Start at time T = first post time.
Set greatestTime = T
Sum all counts between T and T+one hour --> currentHourCount and greatestHourCount
While records exist past T+one hour
   Increment T by one minute.
   While the first element is prior to time T, subtract it
   while the last element is before time T+ one hour, add it
   If currentHourCount > greatestHourCount then
      greatestHourCount = currentHourCount
      greatestTime = T
end while

-亚当

Answer 6

这是其他 Josh 实现的一个细微变化，它放弃了直接表，并在自身上使用自联接来查找该帖子一小时内的任何帖子。

select top 1 posts.DateCreated, count (posts.datecreated),
min(minutes.DateCreated) as MinPostDate,
max(minutes.datecreated) as MaxPostDate
from posts Minutes   
left join posts on posts.datecreated >= minutes.DateCreated 
AND posts.datecreated < dateadd(hour, 1, Minutes.DateCreated)
group by posts.DateCreated
order by count(posts.datecreated) desc

从只有 6 行的表的性能角度来看，他使用该函数生成中间表的方法耗时 16 秒，而这个方法是亚秒级。

我不肯定是否有可能使用它来错过有效的时间范围，因为时间跨度是基于每个帖子的偏移量。

Answer 7

这会做到的。

SELECT DateOfEvent HourBegin, DATEADD(hh, 1, DateOfEvent)) HourEnd, COUNT(*) AS NumEventsPerHour FROM tEvents AS A JOIN tEvents AS B ON A.DateOfEvent >= B.DateOfEvents AND DATEADD(hh, 1, A.DateOfEvent) < = B.DateOfEvent 按 A.DateOfEvent 分组

Answer 8

选择 DATEPART(小时, PostDateTime) 作为 HourOfDay,
        COUNT(*) 个论坛帖子
来自帖子
按日期分组（小时，PostDateTime）

Answer 9

如果是mysql：

select substr( timestamp, 1, 16 ) as hour, count(*) as count from forum_posts group by hour order by count desc limit 1;

编辑：不确定原始问题是否意味着任何可能的 60 分钟时间

Answer 10

如果使用 MySQL：

SELECT DATE(postDate), HOUR(postDate), COUNT(*) AS n
FROM posts
GROUP BY DATE(postDate), HOUR(postDate)
ORDER BY n DESC
LIMIT 1