GTFS - 2つのフィードでのトリップの検索を改善する

Question

現在、2つのフィードを取り込み、いずれかのフィードに欠落している、またはその中に部分的に存在するトリップをプリントアウトするJavaプログラムを作成中です。たとえば、フィード1にはトリップABがあり、トリップ2にはABCDが停止しています。したがって、T2はT1のサブセットです。

基本的には、各フィードに1つのMap<Type, List<Trip>>があります。タイプはルートタイプ（バス、トラムなど）で、List<Trip>にはそのタイプのすべてのトリップが含まれています。

すべてTripオブジェクトは、指定されたフィールドがhereです。また、List<StopTime>とServiceへの参照は、ソートされた順序でストップを指定し、旅行が実行されているサービス時間を指定します。

このチェックは意図どおりに機能し、私が期待した結果が得られます。しかし、もし私が間違っていなければ、私は基本的にO（n^2）の最悪の場合には他のリストとの各トリップをチェックするので、大きなフィード（40.000以上の旅行）での実行時間はかなり長いです。

私が見なければならない旅行を最小限に抑える方法を探しています。 私ができることの1つは、旅行の日付範囲が重複している場合、小切手を移動することです。これは現在Tripオブジェクト内のList<StopTime>をチェックするときに行われます。

Answer 1

私はGTFSを知らないのですが、おそらく私の解決策を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); 
     } 
    } 
} 

は今、あなたはこのマップを持っていることをあなたに潜在的なマッチングの旅行のためにはるかに迅速に確認することができます少なくとも1つの一致する停止時間を持つトリップのみが考慮されます（停止時間はかなりユニークですこれらのほとんどは重複しています）。

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

おそらくこれはストリームとしても非常にうまく書くことができます。