3

我正在尝试将 10000 个事件安排到不同的通道中。每个事件都有开始和结束日期。任何事件都不能在通道中重叠。

    ======================================================================
Lane 1   [Event1]      [Event4       ]  [Event7   ]
    ======================================================================
    ======================================================================
Lane 2         [Event2]            [Event 5]      [Event 8]
    ======================================================================
    ======================================================================
Lane 3     [Event3        ]       [Event6]      
    ======================================================================
    ========time along x axis        >>>>>>>>>>>>>>>>>>>>>>>>>>

所以我的问题是有效地为活动确定合适的车道。我从数据库中获取按开始时间排序的事件。我采取的第一种方法是为每个车道设置一个 last_end_time。对于每个新事件，我都会检查每个车道，如果事件的 start_time 早于车道的 last_end_time，我会向下移动并检查下一个车道。如果我找不到适合它的通道，我会创建一个新通道。

class LaneManager
  def initialize
    @lanes = []
  end

  # Find the free lane given start and end of an event
  def nextFreeLane start_date, end_date
    @lanes.each_with_index do |lane, index|
      if start_date > lane.last_date
        lane.last_date = end_date
        return index
      end
    end
    lane = Lane.new
    lane.last_date = end_date
    @lanes << lane
    @lanes.length - 1
  end
end

class Lane
  attr_accessor :last_date
end

然而，这存在另一个问题。如果我有 5000 个具有相同开始和结束的事件，那么要为 5001 事件找到一个插槽，我最终会检查之前的 5000 个通道，依此类推......性能只会下降。

有关如何有效存储、查询事件的任何建议？我需要在网页上呈现它们。我有水平和垂直滚动来平移事件。对于垂直滚动，我告诉我的服务器 - 这些是我需要的通道（比如通道 5 到通道 10）。对于水平滚动，我只需使用新的时间窗口和所需的通道进行新查询，这基本上是一组新的事件。

我的问题是垂直滚动，我需要有效地将所有事件插入正确的通道。如果我能有效地做到这一点，那么我可以在我的服务器上查询 26-30 车道中的事件。将不胜感激任何建议。

4

3 回答 3

2

我将扩展我的评论问题作为答案，因为样本数据太长了。

样本数据为：

create table events (
    id          serial primary key,
    startend    tsrange not null
);

insert into events (startend)
select tsrange(now()::timestamp(0) + i * interval '1 minute', now()::timestamp(0) + i * interval '1 minute 30 second' + (i % 6) * interval '10 second')
from generate_series(1,100) i;

一个简单的连接，比如这个：

with events as (
select  evt.id as evt_id,
        evt.startend as evt_startend,
        chk.id as chk_id,
        chk.startend as chk_startend
from    events evt
join    events chk on evt.startend && chk.startend
)
select  *
from events
order by evt_startend, chk_startend
limit 10;

产生类似于以下集合的东西：

 evt_id |                 evt_startend                  | chk_id |                 chk_startend                  
--------+-----------------------------------------------+--------+-----------------------------------------------
      1 | ["2013-06-24 15:03:27","2013-06-24 15:04:07") |      1 | ["2013-06-24 15:03:27","2013-06-24 15:04:07")
      2 | ["2013-06-24 15:04:27","2013-06-24 15:05:47") |      2 | ["2013-06-24 15:04:27","2013-06-24 15:05:47")
      2 | ["2013-06-24 15:04:27","2013-06-24 15:05:47") |      3 | ["2013-06-24 15:05:27","2013-06-24 15:07:27")
      3 | ["2013-06-24 15:05:27","2013-06-24 15:07:27") |      2 | ["2013-06-24 15:04:27","2013-06-24 15:05:47")
      3 | ["2013-06-24 15:05:27","2013-06-24 15:07:27") |      3 | ["2013-06-24 15:05:27","2013-06-24 15:07:27")
      3 | ["2013-06-24 15:05:27","2013-06-24 15:07:27") |      4 | ["2013-06-24 15:06:27","2013-06-24 15:09:07")
      4 | ["2013-06-24 15:06:27","2013-06-24 15:09:07") |      3 | ["2013-06-24 15:05:27","2013-06-24 15:07:27")
      4 | ["2013-06-24 15:06:27","2013-06-24 15:09:07") |      4 | ["2013-06-24 15:06:27","2013-06-24 15:09:07")
      4 | ["2013-06-24 15:06:27","2013-06-24 15:09:07") |      5 | ["2013-06-24 15:07:27","2013-06-24 15:10:47")
      4 | ["2013-06-24 15:06:27","2013-06-24 15:09:07") |      6 | ["2013-06-24 15:08:27","2013-06-24 15:11:27")
(10 rows)

正如您在上面看到的，对于任何给定事件，您可以轻松确定潜在的并发事件数量（给定 的右侧的列），从而确定给定事件的潜在车道数。但是，它只是一个范围：对于右侧的任何给定行 ID，有多种可能性将车道号播种到左侧。

带有一些窗口函数的有点难看的查询可能会让您确定何时需要重置车道号。问题是，重置到什么？...

了解后者的唯一方法是确定一个完全没有事件的时间点（在这种情况下，车道 = 1）。对于任何其他时间点，您能说的最好的就是有一条空闲通道，或者您需要创建一条新通道。

因此，假设这是您的一个选项，我建议您实际存储车道编号，并使用触发器自动生成它。在触发器中，对并发事件的简单查询会产生一个繁忙通道列表，让您可以安全地选择或创建一个不忙的通道 - 如果在该时间点没有分配通道，则可以选择通道 1。

您的架构将看起来更像这样：

create table events (
    id          serial primary key,
    startend    tsrange not null,
    lane        int not null
);

水平和垂直滚动的查询变得微不足道。

于 2013-06-24T13:24:37.573 回答
2

首先，将开始时间和结束时间放在一个集合中，然后按时间排序。对于每个结尾，找到最近的下一个开头，并链接到它。完成后，解开线程：从捆绑包中取出第一个开头，并将其连同与其相关的整个事件链（请记住，每一端都链接到最近的开头）。重复该过程，直到捆绑中没有事件开始（因此没有事件）。

于 2013-06-24T12:23:33.167 回答
1

这称为区间分区或区间图着色。例如，请参见此处。您的方法几乎与最佳算法相同，只是您需要从正确数量的车道开始，而不是根据需要添加它们。为了有效地实现它，保留一组当前空闲的通道（例如作为平衡搜索树）并在间隔开始或结束时更新它。

于 2013-07-11T10:38:22.260 回答