Many optimizations require trips to be in sorted order. They usually should be, but this is not guaranteed due to the possibility of real-time updates. This is the same reason we are doing a linear search instead of a binary search for departures, and we are doing a slow linear search for re-boarding instead of just stepping backward a couple of cells.
FIFO or near-FIFO trip ordering allows the algorithm to be significantly more efficient, but FIFO ordering is not realistic in real operation. We could in principle have two different search modes: real-time and non-real-time, one using linear search and the other binary.
However the speedup should be considered before introducing the optimization. If I remember right it's only about 20 percent speed change, so worth asking if it's worth the additional complexity to have two search methods.
Many optimizations require trips to be in sorted order. They usually should be, but this is not guaranteed due to the possibility of real-time updates. This is the same reason we are doing a linear search instead of a binary search for departures, and we are doing a slow linear search for re-boarding instead of just stepping backward a couple of cells.
FIFO or near-FIFO trip ordering allows the algorithm to be significantly more efficient, but FIFO ordering is not realistic in real operation. We could in principle have two different search modes: real-time and non-real-time, one using linear search and the other binary.
However the speedup should be considered before introducing the optimization. If I remember right it's only about 20 percent speed change, so worth asking if it's worth the additional complexity to have two search methods.