Алгоритм поиска, но для функций

Question

Учитывая список входных данных (допустим, это просто целые числа) и список функций (и эти функции принимают целое число и возвращают True или False).

Мне нужно взять этот список ввода и посмотреть, вернет ли какая-либо функция в списке True для любого значения в списке.

Есть ли способ сделать это быстрее, чем O (N^2)

Прямо сейчас, что у меня есть

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

быстрее методы?

Answer 1

Без дополнительной информации о функциях, результаты возможных вызовов функций должны считаться независимыми друг от друга, поэтому нет более быстрого способа, чем проверка их всех.

Вы можете написать это немного более сжато, хотя:

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

встроенную функцию any() также короткого замыкания, так же, как ваш исходный код.

Edit: Получается, что желаемый эквивалент был бы

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

Смотрите комментарии для обсуждения.

Answer 2

Нет, нет более быстрого пути. O (m * n) - предел. Если бы у вас было больше информации о функциях, вы могли бы побить это, но в общем случае нет.

Answer 3

Если вы знаете больше о функциях или значениях, вы можете сделать то, что делает обычная поисковая система, - примените некоторую индексацию по списку значений, для которой требуется только один проход.

EDIT:

Вот подход с any(), который работает для этого использования.

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

Answer 4

Вы не можете сделать лучше, чем O(nm) лишь их запросов и без каких-либо упрощающих предположений о функциях под рукой.

Это потому, что доказательство отсутствия таких функций требует, чтобы вы доказали, что для любого целого и любой функции результатом запроса является False.

Чтобы доказать это, вы не можете сделать меньше, чем выполнять все запросы, потому что ваш state space является O(2^nm) и запрос только половины пространства состояний, так что вам нужно O(log_2(2^nm)) = O(nm) запросы, чтобы уменьшить пространство состояний для решения «каждая функция возвращает ложь для каждого целого числа ".

Answer 5

Это на самом деле не O (п), но это спасает вас от итерации функции каждый раз:

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

Обсуждая ли вложенные лямбды являются вещим это совсем другой история, но я склонен думать в функциональном при рассмотрении списков функций.