python - 列车时刻表搜索算法

Question

我正在尝试解决巴黎和柏林之间每隔一天运行一次火车的问题。如果火车未在 T-2 日运行，则视为"new"火车；如果未按计划在 T+2 日运行，则视为“已结束”。这些火车的出发时间可以是 (+/-)60 分钟与引用火车(我们正在与之比较)。

因此，如果我有一个月的数据集，我必须计算每次旅行是新的还是结束的。数据采用 trip_id, start_city_id, end_city_id, dep_datetime 格式。

例子

1,B,P,2018-04-01 07:50  
2,B,P,2018-04-01 13:10  
3,B,P,2018-04-01 15:40  
4,B,P,2018-04-02 08:00  
5,B,P,2018-04-02 12:50  
6,B,P,2018-04-02 15:20  
7,B,P,2018-04-03 09:50  
8,B,P,2018-04-03 13:20  
9,B,P,2018-04-03 15:40  
10,B,P,2018-04-04 09:50  
11,B,P,2018-04-04 13:20  
12,B,P,2018-04-04 14:40  

在上面的例子中=>
* train_id=1 可被视为“已结束”，因为它未计划在与 train_id=1 的时差 (+/-)60 分钟内的 T+2(4 月 3 日)运行。
* 虽然 train_id=2 可以被视为“无变化”，因为相应的列车在 4 月 3 日 @12:50 运行，即 train_id=2 出发时间的 60 分钟内
* 而 train_id=7 将被视为"new"列车，因为在 T-2(4 月 1 日)没有相应的列车在 train_id=7 的 (+/-)60 分钟出发时间内运行

我在数据库中有数据。 现在，我正在遍历数据集中的每个项目，但我不确定这是否是最佳方法

1. 您认为我应该先将所有需要的数据提取到我的程序 (python) 中，然后在其上运行算法吗？或者我应该在数据库本身上做所有事情，可能是 MySQL 中的存储过程？

2. 我应该使用哪种算法和数据结构？

Answer 1

您的方法是否足够快？称之为好。

类似于下面的查询会给出答案(您需要根据您的 SQL 方言对其进行调整)。它工作得够快吗？然后称其为好。

select *,
not exists(select * from T T2 
where T2.start_city_id=T.start_city_id
where T2.end_city_id=T.end_city_id
and T2.dep_datetime between T.dep_datetime - '49 hours'::interval and T.dep_datetime  - '47 hours'::interval) as starting,
not exists(select * from T T2 
where T2.start_city_id=T.start_city_id
where T2.end_city_id=T.end_city_id
and T2.dep_datetime between T.dep_datetime + '47 hours'::interval and T.dep_datetime  + '49 hours'::interval) as ending
from T

如果不是，请尝试在 (start_city_id, end_city_id, dep_datetime) 上添加索引。作品？称之为好。

如果不是，请尝试优化查询。您应该进行顺序扫描和 2 次索引扫描。作品？称之为好。

如果一切都失败了，获取按 (start_city_id, end_city_id, dep_datetime) 排序的数据，然后对每条记录进行二进制搜索(在 python 中)以匹配上一个或下一个连接。有点棘手，但绝对应该足够快。