python - 比较谷歌应用程序引擎数据存储中的多个日期范围(多对多，Python)

Question

我在 Google App Engine 数据存储区中有两个数据集。

class First_Set(db.Model):
  start_time = db.DateTimeProperty()
  end_time = db.DateTimeProperty()
  data1 = db.FloatProperty()
  ...

class Second_Set(db.Model):
  start_time = db.DateTimeProperty()
  end_time = db.DateTimeProperty()
  data2 = db.FloatProperty()
  ...

(它们有其他不同的数据，这就是它们位于不同数据集中的原因。)

我希望找到两个数据集中所有重叠的 start_time 和 end_time 的数据存储 ID，理想情况下无需从一个数据集中提取结果并在另一个数据集上迭代第一个结果。

初始数据集的精彩可视化来自 here (它也有在SQL中解决的问题):

1     |-----| 
2        |-----| 
3                 |--| 
4                       |-----| 
5                          |-----| 
6                                  |---| 
7                                        |---|  
8                           |---| 
9                                       |-----|

我需要的最终结果是(来自同一个example):

+----+---------------------+----+---------------------+ 
| id | start               | id | end                 | 
+----+---------------------+----+---------------------+ 
|  2 | 2008-09-01 15:02:00 |  1 | 2008-09-01 15:04:00 | 
|  5 | 2008-09-01 16:19:00 |  4 | 2008-09-01 16:23:00 | 
|  8 | 2008-09-01 16:20:00 |  4 | 2008-09-01 16:22:00 | 
|  8 | 2008-09-01 16:20:00 |  5 | 2008-09-01 16:22:00 | 
|  7 | 2008-09-01 18:18:00 |  9 | 2008-09-01 18:22:00 | 
+----+---------------------+----+---------------------+ 

SQL 解决方案在下面的示例中进行了描述，但由于缺少 JOIN，我无法在数据存储中执行此操作:

SELECT v1.id, v1.start, v2.id, LEAST(v1.end,v2.end) AS end 
FROM visits v1 
JOIN visits v2 ON v1.id <> v2.id and v1.start >= v2.start and v1.start < v2.end  
ORDER BY v1.start;

据我了解，使用 ListProperty() (来自 this question )，一对多版本相当简单。

有人能想出一个解决方案来找到重叠时间(最好是用Python)吗？

Answer 1

查看Marzullo's algorithm其时间效率为O(n log n)。
还有many question on Stackoverflow涵盖重叠间隔，可用于解决您在 AppEngine 上的问题。