6

给定时间（例如，目前周二下午 4:24），我希望能够从一组企业中选择当前开放的所有企业。

  • 我有一周中每一天的每家企业的营业和关闭时间
  • 假设一家企业只能在每小时的 00、15、30、45 分钟标记开/关
  • 我假设每周都有相同的时间表。
  • 我最感兴趣的是能够快速查找在某个时间开放的一组业务，而不是数据的空间需求。
  • 请注意，有些我一天晚上 11 点开门，第二天凌晨 1 点关门。
  • 假期无关紧要 - 我会单独处理这些

存储这些打开/关闭时间的最有效方法是什么，以便通过单个时间/星期几元组我可以快速找出哪些企业是开放的？

我正在使用 Python、SOLR 和 mysql。我希望能够在 SOLR 中进行查询。但坦率地说，我愿意接受任何建议和替代方案。

4

7 回答 7

8

如果您愿意一次只看一个星期，您可以将所有开/关时间规范化为自一周开始以来设置的分钟数，例如周日 0 小时。对于每个商店，您创建多个 [startTime, endTime, storeId] 形式的元组。（对于跨越周日午夜的几个小时，您必须创建两个元组，一个到周末，一个从一周开始）。这组元组将在 startTime 和 endTime 上都被索引（例如，使用您将预处理的树）。元组不应该那么大：一周只有大约 10k 分钟，可以容纳 2 个字节。这种结构在具有适当索引的 MySQL 表中将是优雅的，并且在信息更改时对不断插入和删除记录非常有弹性。您的查询将只是“

如果信息不经常更改，并且您希望查找速度非常快，则可以预先解决所有可能的查询并缓存结果。例如，一周内只有 672 个刻钟。有了一个企业列表，每个企业都有一个像 Brandon Rhodes 的解决方案一样的开放和关闭时间列表，您可以简单地在一周内每隔 15 分钟迭代一次，找出谁在营业，然后将答案存储在查找表中或内存列表。

于 2009-04-22T00:25:59.623 回答
5

另一位受访者提到的位图字段将非常有效，但如果您希望能够处理半小时或四分之一小时的时间，则会变得混乱，因为您必须每次在算术上增加位数和字段的设计您遇到了必须匹配的新分辨率。

我会尝试将值作为日期时间存储在列表中：

openclosings = [ open1, close1, open2, close2, ... ]

然后，我将在其内置的“bisect”模块中使用 Python 的“bisect_right()”函数在快速 O(log n) 时间内找到您的查询时间“适合”的列表中的哪个位置。然后，查看返回的索引。如果它是偶数（0、2、4...），则时间介于“关闭”时间之一和下一个“开放”时间之间，因此商店关闭。相反，如果二等分索引是奇数（1、3、5...），则时间已落在开店时间和关店时间之间，商店开张。

不如位图快，但您不必担心分辨率，而且我想不出另一个如此优雅的 O(log n) 解决方案。

于 2009-04-22T00:08:07.357 回答
4

您说您正在使用 SOLR，不关心存储，并且希望查找速度快。然后，不要存储打开/关闭元组，而是以您需要的粒度级别（15 分钟）为每个打开的时间块索引一个条目。对于编码本身，您可以只使用累积小时：分钟。

例如，周一下午 4 点到 5 点营业的商店会为 [40:00, 40:15, 40:30, 40:45] 添加索引值。周一下午 4:24 的查询将被规范化为 40:15，因此与该商店文档匹配。

乍一看，这似乎效率低下，但对于索引速度和空间来说，这是一个相对较小的常数损失。并使搜索尽可能快。

于 2009-04-22T01:13:48.807 回答
3

抱歉，我没有一个简单的答案，但我可以告诉你，作为 90 年代后期一家公司的开发团队经理，我们的任务是解决这个问题，这很困难。

每周的工作时间并不困难，可以使用相对较小的位掩码（168 位 = 每周每小时 1 个）来完成，诀窍是每周二交替关闭的企业。

从位掩码开始，然后转到异常字段是我见过的最好的解决方案。

于 2009-04-21T23:52:58.673 回答
1

在您的 Solr 索引中，不是将每个业务作为一个以小时为单位的文档进行索引，而是在一周内为每个业务的每个“零售会话”建立索引。

例如，如果 Joe 的咖啡店在周一至周六上午 6 点至晚上 9 点营业，周日不营业，您将索引六个不同的文档，每个文档都有两个索引字段，“open”和“close”。如果您的单位是 15 分钟间隔，则值的范围可以从 0 到 7*24*4。假设您对每个企业都有一个唯一的 ID，请将其存储在每个文档中，以便您可以将会话映射到企业。

然后你可以简单地在 Solr 中进行范围搜索：

打开：[* TO N] 并关闭：[N+1 TO *]

其中 N 计算到当前时间所在的第 N 个 15 分钟间隔。例如，如果是周三上午 10:10，您的查询将是：

打开：[* TO 112] 并关闭：[113 TO *]

又名“查找在周三上午 10:00 或之前开始并在周三上午 10:15 或之后结束的会话”

如果您想在搜索中包含其他条件，例如位置或产品，您还需要将其与每个会话文档一起编入索引。这有点多余，但是如果您的索引不是很大，那应该不是问题。

于 2009-04-22T14:18:22.507 回答
0

您是否查看过有多少种独特的开/关时间组合？如果数量不多，则制作唯一组合的参考表，并针对每个业务存储相应条目的索引。然后您只需搜索参考表，然后找到具有这些索引的业务。

于 2009-04-22T02:03:30.980 回答
0

如果你能很好地控制你的数据，我看到了一个简单的解决方案，类似于@Sebastian 的。遵循创建元组的建议，除了以 [time=startTime, storeId] 和 [time=endTime, storeId] 的形式创建它们，然后在列表中对它们进行排序。要了解商店是否营业，只需执行如下查询：

select storeId
from table
where time <= '@1'
group by storeId
having count(storeId) % 2 == 1

为了优化这一点，您可以在每个时间 t 构建一个查找表，存储在 t 开放的商店，以及 t 和 t+1 之间的商店开放/关闭（对于 t 的任何分组）。

然而，这具有更难维护的缺点（重叠的打开/关闭需要合并到更长的打开关闭期间）。

于 2009-04-22T01:18:43.833 回答