0

I have a list of objects that have durations,

ProcedurePart
  Start: double
  Stop: double
  Instructions: string

they occur sequentially after each other:

stepOne                   stepTwo                      stepThree
Start: 0.0                Start: 1.56                  Start: 5.443
Stop: 1.56                Stop: 5.443                  Stop: 10.9
"Take the dinglebop"      "Smooth it with shleem"      "Push it through the gru...

I want to pull out items using a timestamp, the item retrieved should be the step within which that timestamp falls.

E.g., for the above sequence:

sequence[0.0] = stepOne
sequence[1.0] = stepOne
sequence[1.56] = stepTwo
sequence[2.578281] = stepTwo
sequence[10.0] = stepThree

The precision is only limited by the data-type (C#'s double), and because times are continuous I can't create a look-up table using all possible discrete input values. Is there a data structure that can store this sequence and allow for anything better than O(log(N)) look-up times (better than binary search)?

8
  • What about using a normalized DateTime instead of double, maybe with a custom comparator?
    – πάντα ῥεῖ
    Commented Aug 25, 2020 at 12:36
  • @πάνταῥεῖ how will that allow for faster than O(logN) look up?
    – minseong
    Commented Aug 25, 2020 at 12:58
  • 4
    Why do you need better than binary search algorithm? How many steps are you expecting? Billions? And even in such case, having 5 000 000 000 steps, binary search would need ~30 iterations at worst, which is pretty much nothing.
    – Andy
    Commented Aug 25, 2020 at 12:59
  • @Andy I don't expect that many steps, but I will be "indexing" (using different times) lots and lots of times. 30 iterations for billions is a good point though, I honestly hadn't thought of it. I was just excited by the theory behind a possible fast algorithm for this.
    – minseong
    Commented Aug 25, 2020 at 13:16
  • 1
    @Kain0_0 "time step cells" .... theoretically infinite memory usage?
    – minseong
    Commented Aug 26, 2020 at 9:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.