Algoritmo de búsqueda pero para funciones

Question

Dada una lista de entrada (digamos que son solo enteros), y una lista de funciones (y estas funciones toman un entero, y devuelve True o False).

Tengo que tomar esta lista de entrada, y ver si alguna función en la lista devolverá True para cualquier valor en la lista.

¿Hay alguna manera de hacer esto más rápido que O (n^2)

En este momento lo que tengo es

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

Los métodos más rápidos?

Answer 1

Sin más información sobre las funciones, los resultados de las posibles llamadas a funciones len(functions) * len(values) se deben considerar independientes entre sí, por lo que no hay forma más rápida que comprobarlas todas.

Usted puede escribir esto un poco más concisa, sin embargo:

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

La función incorporada any() también cortocircuitos, al igual que su código original.

Editar: Resulta que el equivalente deseada habría sido

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

Ver los comentarios para una discusión.

Answer 2

No, no hay forma más rápida. O (m * n) es el límite. Si tiene más información sobre las funciones, es posible que pueda vencer eso, pero en el caso general, no.

Answer 3

Si sabe más acerca de las funciones o los valores, puede hacer lo que hace un motor de búsqueda normal: aplicar algún tipo de indexación sobre la lista de valores que solo requiere una sola pasada.

EDIT:

Aquí hay un acercamiento con any() que funcione para este caso de uso.

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

Answer 4

No se puede hacer nada mejor que O(nm) sólo por la consulta de ellos y sin algunos supuestos simplificadores sobre las funciones a mano.

Eso es porque la prueba de que no hay tales funciones requiere que demuestres que, para cualquier número entero y cualquier función, el resultado de la consulta es False.

Para demostrarlo, no se puede hacer menos de realizar todas las consultas, debido a que su state space es O(2^nm) y una consulta simplemente mitades del espacio de estado, por lo que necesita O(log_2(2^nm)) = O(nm) consultas para reducir su espacio de estado a la solución "cada función devuelve false por cada número entero ".

Answer 5

Esto no es en realidad O (n), pero le salva de iterar sobre las funciones de cada:

#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)) 

discutir si lambdas anidados son Pythonic es una historia completamente diferente, pero tienden a pensar en la funcionalidad términos cuando se trata de listas de funciones.