GTFS - Улучшение поиска поездок в двух лентах

В настоящее время я работаю над java-программой, которая принимает два канала и распечатывает поездки, которые отсутствуют в одном из каналов или частично в нем. Например, у Feed 1 есть рейс T1 с остановками ABCDE, а у Feed 2 есть рейс T2 с остановками ABCD. Таким образом, T2 является подмножеством T1.

В основном у меня есть один Map<Type, List<Trip>> для каждого фида. Тип — это тип маршрута (автобус, трамвай и т. д.), а List<Trip> содержит все поездки этого типа.

Все объекты Trip имеют поля, указанные здесь. А также ссылка на List<StopTime> и Service, которые указывают остановки в отсортированном порядке и время обслуживания во время поездки.

Проверка работает по назначению, и я получаю ожидаемые результаты. Но время работы с большими потоками (40 000 и более поездок) довольно велико, потому что я в основном проверяю каждую поездку из одного списка с другим, что в худшем случае будет O (n ^ 2), если я не ошибаюсь.

Я ищу способ свести к минимуму поездки, на которые я должен смотреть. Одна вещь, которую я мог бы сделать, это переместить проверку, если диапазоны дат поездок перекрываются. В настоящее время это делается при проверке List<StopTime>внутри объекта Trip.


java gtfs
person Kazanagi    schedule 11.03.2017    source источник
comment
Ваш пример нельзя воспроизвести на самом деле *, но вы можете попробовать ParallelStreams и ConcurrentHashMap в Java 8. * stackoverflow.com/help/mcve, * radar.oreilly.com/2015/02/   -  person Tony Laidig    schedule 12.03.2017

Ответы (1)


arrow_upward
1
arrow_downward

Я не знаю 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.
        }
    }
}

Вы, вероятно, можете написать это довольно красиво и как поток.

person john16384    schedule 11.03.2017
comment
Спасибо за ваш ответ. Я смог перевести ваше решение, и оно работает как шарм :) - person Kazanagi; 12.03.2017