Re: Need efficient search strategy in list of time intervals

On 31 Jul., 14:31, Lasse Reichstein Nielsen <l...@xxxxxxxxxx> wrote:
lemmi <dlemmerm...@xxxxxxxxx> writes:
I have a list of time intervals ([long,long]). The list is sorted
based on the start times of the intervals. I now need a fast
algorithm, which takes a time span TS as input and returns the index
of the first time interval A in the list that is contained in the
given time span. The rendering engine of my UI framework will then
iterate over the list starting at the calculated index.

Why iterate? The next element can't be assumed to be hit by TS, so you
might have to iterate over a long list of irrelevant objects anyway.

The iteration is smart enough to stop when it reaches a time span with
a start time larger than TS. So if a list contains 100 entries and the
index is (for example 33) then the paint method iterates over 33, 34,
35
and might stop at 36 if its start time is larger than TS.end.

.

Relevant Pages

  • Re: Need efficient search strategy in list of time intervals
    ... which takes a time span TS as input and returns the index ... iterate over the list starting at the calculated index. ... You should consider whether there is a better data structure than a list ...
    (comp.lang.java.programmer)
  • Re: Need efficient search strategy in list of time intervals
    ... which takes a time span TS as input and returns the index ... The algorithm gets constantly called as part of a paintmethod so it ... and the you can do a binary search for the Instant. ... dependent on the data a little more, one long interval can cause a big ...
    (comp.lang.java.programmer)
  • Re: Need efficient search strategy in list of time intervals
    ... algorithm, which takes a time span TS as input and returns the index ... iterate over the list starting at the calculated index. ... That sounds like a job for a binary search. ...
    (comp.lang.java.programmer)