Python - Apply an conditional function (intersection) to every element of a list

Question

I have a python list of ints, a. I also have another list, b, which is a tuple of 2 values (c, d). I need to see if any elements of a have values that are between any of the tuple elements of b.

I think there is a way to do this using map(), but I can't figure out how to pass in the values of my tuple list.

For example, my data structure looks like:

a = [1, 2, 3, 4, 5, 6, 7]
b = [(12,14), (54, 78), (2,3), (9,11)]

I am trying to find out if any of the elements in a have values between any of the tuple elements of b. In the above case, 2 and 3 (from a) are inside (inclusive) of the tuple (2,3) in b. So my final answer would be True.

Does anyone have any idea how to do this in a performat way? Right now, I am looping through each element of a and then looping through each element of b. This is ok for small amounts of data, but my arrays are quite large and this step takes way to long.

I don't think there's going to be a way to do it for arbitrary data without looping over everything. You could try to do optimization tweaks like preprocessing the `b` list to find the overall max and min, then excluding values from `a` that are outside that range, but whether that will improve things depends on what the data are like. — BrenBarn, Nov 19 '14 at 20:05
Can the tuples in `b` overlap? i.e. is `b = [(1, 5), (3, 7)]` possible? Put differently, do you expect there to be a single tuple defining the range that `a` is within, or can there be several? — Stuart, Nov 19 '14 at 20:30

score 1 · Answer 1 · answered Nov 19 '14 at 20:16

If the (c, d) values restricted to a certain range (say 0-100), you could calculate a boolean array of allowed values, and compare a against that with a simple index lookup.

If you the values are not restricted or the range would be too large, put the values of b into a sorted data structure. Then you can look up a against that quickly, without needing to go through the whole list every time. While building this lookup data structure, you would have to look out for overlapping ranges, and merge them.

ha9u63a7 · Accepted Answer · 2014-11-19T21:29:24.743

1

dId you want this?

[c in range(k[0], k[1]+1) for c in a for k in b]

returns:

[False, False, False, False,  # 1 is in any ofthe tuple range in b?
 False, False, True, False,   # 2 is in any of the tuple range in b?
 False, False, True, False,   # etc. etc....
 False, False, False, False,
 False, False, False, False,
 False, False, False, False, 
 False, False, False, False] # searches for each element in a within the range specified by the tuple elements in b

If you wanted to do something else like check every element in a using each element of b first then swap the order of the fors:

[c in range(k[0], k[1]+1) for k in b for c in a]

returns:

[False, False, False, False, False, False, False, // is b[0] range covers 1-7?
 False, False, False, False, False, False, False, // etc. etc. 
 False, True, True, False, False, False, False, 
 False, False, False, False, False, False, False]

I assumed this is what you didn't want....but thought I would post it to you anyway

edited Nov 19 '14 at 21:29

answered Nov 19 '14 at 21:07

ha9u63a7

6,233
16
73
108

This is perfect. I followed it up with a `any()` to get a single `True` or `False`, which fits my use case. – Brett Nov 19 '14 at 21:16
This loops through each element of a and then loops through each element of b. I thought that was what you were trying to avoid...? – Stuart Nov 19 '14 at 21:18
Sorry for giving you half working solution as I know how much you will want each of the row to indicate which number in a it managed to match. – ha9u63a7 Nov 19 '14 at 21:18

Stuart · Answer 3 · 2014-11-19T22:24:25.320

If you sort first you can avoid checking every value in a against every tuple in b. The tuples that have already been checked against lower values of a can be discarded, which will make the check much faster.

def check_value_in_ranges(a, b):
    a = sorted(set(a))
    b = sorted(set(b), reverse=True)
    lower, upper = b.pop()
    for value in a:
        while value >= lower:
            if value <= upper:
                return True
            elif not b:                
                return False           # no tuples left to check against
            lower, upper = b.pop()     
    return False                       # no values of a left to check

I think this works whether the tuples are overlapping or not - check here.

Python - Apply an conditional function (intersection) to every element of a list

3 Answers3