GTFS

Question

我目前正在开发一个 java 程序，该程序接收两个提要并打印出其中任何一个提要中缺少或部分包含的行程。例如，Feed 1 的行程 T1 停靠点 ABCDE，而 Feed 2 的行程 T2 停靠点 ABCD。所以 T2 是 T1 的子集。

我基本上每个 Feed 都有一个 Map<Type, List<Trip>>。 Type 是路线类型（公共汽车、电车等），List<Trip> 包含该类型的所有行程。

所有 Trip 个对象都具有指定的字段 here。以及对 List<StopTime> 和 Service 的引用，它们按排序顺序指定停靠点以及行程为运行.

时的服务时间

检查按预期进行，我得到了预期的结果。但是运行大量提要（40.000 次和更多行程）的时间相当长，因为我基本上会检查一个列表中的每个行程与另一个列表，如果我不这样做，在最坏的情况下将是 O(n^2)打错了。

我正在寻找一种方法来最大程度地减少我必须查看的行程。我可以做的一件事是在检查 Trip 对象内的 List<StopTime> 时移动检查行程 overlap.This 的日期范围是否当前完成。

Answer 1

我不知道 GTFS，但是，也许你可以将我的解决方案翻译成它。我要做的是为第二个提要构建一个这样的地图：

Map<StopTime, List<Trip>> tripsByStopTime;

您可以像这样浏览第二个提要（例如，只要您获得上面的地图，您就可以按照自己喜欢的方式进行）- 因为我使用的是 StopTime作为密钥，确保它有正确的 equals 和 hashCode:

for (List<Trip> trips : feed2.values()) {
    for (Trip trip : trips) {
        for (StopTime stopTime : trip.getStopTimes()) {
            tripsByStopTime.computeIfAbsent(stopTime, k -> new ArrayList<>())
                 .add(trip);
        }
    }
}

现在您有了这张地图，您可以更快地检查潜在的匹配行程，因为只有至少有一个匹配停止时间的行程才被视为（请注意，我假设停止时间是相当独特的，如果大多数它们是重复的这种方法不能很好地扩展):

for (List<Trip> trips : feed1.values()) {
    for (Trip trip : trips) {
        Set<Trip> potentialMatchingTrips = new HashSet<>();

        for (StopTime stopTime : trip.getStopTimes()) {
            List<Trip> list = tripsByStopTime.get(stopTime);

            if (list != null) {
                potentialMatchingTrips.add(list);
            }
        }

        for (Trip potentialMatchingTrip : potentialMatchingTrips) {
              // Check here if it was a subset.
        }
    }
}

你也可以将它写成流。

GTFS - 改进两个提要中的旅行搜索

GTFS - Improving search for trips in two feeds

java