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

Question

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

我基本上有一个Map<Type, List<Trip>>对于每个饲料。 Type 是路线类型(公交车、电车等)，List<Trip>包含该类型的所有行程。

全部Trip对象具有指定的字段 here 。还有对 List<StopTime> 的引用和一个 Service其中按排序顺序指定了行程运行时的停靠站和服务时间。

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

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

Answer 1

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

Map<StopTime, List<Trip>> tripsByStopTime;

您可以通过像这样浏览第二个提要来完成此操作(例如，只要您获得上面的 map ，您就可以按照自己喜欢的方式进行操作)——因为我正在使用 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);
        }
    }
}

既然你有了这张 map ，你就可以更快地检查潜在的匹配行程，因为只有至少有一个匹配停止时间的行程才会被考虑(注意，我假设停止时间是相当独特的，如果它们中的大多数都是)重复此方法无法很好地扩展):

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.
        }
    }
}

您也可以将其很好地编写为流。