Search algorithm but for functions

Question

Given an input list (let it be said that they are just integers) and a list of functions (and these functions take an integer and return either True or False).

I need to take this input list and see if any function in the list will return True for any value in the list.

Is there a way to do this faster than O (n ^ 2)

Now i have

for v in values: for f in functions: if f(v): # do something to v break 

Any faster methods?

Answer 1

Without additional information about functions, the results len(functions) * len(values) possible function calls should be considered independent of each other, so there is no faster way than checking them all.

You can write this a little more succinctly, though:

 any(f(v) for v in values for f in functions) 

The built-in function any() as short-circuited as the source code.

Change It turns out that the desired equivalent would be

 all(any(f(v) for f in functions) for v in values) 

See discussion comments.

Answer 2

No, there is no faster way. O (m * n) is the limit. If you had more information about the functions, you could beat this, but in general not.

Answer 3

If you know more about functions or values, you can do what a regular search engine does - apply some indexing on a list of values, which only requires one pass.

EDIT:

Here's an approach with any() that works for this use case.

 for v in values: if any(f(v) for f in functions): #do something to v 

Answer 4

You cannot do better than O(nm) by only querying them and without any simplifying assumptions regarding the available functions.

This is because proving the absence of such functions requires you to prove that for any integer and any function, the result of the query is False .

To prove this, you cannot do less than execute all the queries, because your space <<22> and the query is halved so you need O(log_2(2^nm)) = O(nm) queries to reduce the space states before the decision "each function returns false for each integer."

Answer 5

This is actually not O (n), but it saves you from iterating over functions every time:

 #combine all funcs into one with `or` newFunc = reduce(lambda f,g: (lambda x: f(x) or g(x)), funcs) #cleaner than for, i think satisfied = any(map(newFunc, values)) 

Discussing whether nested lambdas are pythons is a completely different story, but I tend to think in functional terms when working with function lists.