CODEWITHSUNDEEP
pythonsearchsetintervals
Asmita Poddar
Asmita Poddar

Reputation: 532

Find whether an interval falls within a set of intervals Python

I am using python-intervals from portion package in Python: import portion as P

To check whether an item is contained in a set, we can do item in set, for example 2 in {2,3} gives True. (This takes O(1) time)

To check whether an interval is contained within another interval, we can do item in interval, for example P.closed(2,3) in P.open(1,10) gives True.

I would like to check whether an interval is contained in a list of intervals. The iterative way (O(n)) to do it would be:

import portion as P

intervals_set = {P.open(1,10), P.open(20,30)}
item = P.closed(2,3)
result = []
for s in intervals_set:
    if item in s:
        result.append(item)

I have to perform the search for many items (run this for loop many times) for a long set of intervals, so I was wondering if there is an efficient way to find whether an interval exists in a set of intervals?

Upvotes: 0

Views: 1264

Answers (1)

Guybrush
Guybrush

Reputation: 2780

I'm the maintainer of portion.

portion supports interval sets out of the box, so you don't need to manually create a set of intervals (e.g. no need for {P.open(1,10), P.open(20,30)}). Simply create a disjunction of these intervals, and it will work:

interval = P.open(1, 10) | P.open(20, 30)
item = P.closed(2, 3)
assert item in interval

This will be slightly faster than the solution you propose, since portion internally sorts (disjunctions of) intervals, and benefits from this sorting to make things faster.

If you have many items, then the loop becomes:

for item in items: 
  if item in interval: 
    result.append(item)

Or, using list comprehensions, [item for item in items if item in interval].

Upvotes: 4

Related Questions