Бинарный поиск по «бесконечной» последовательности. С чего мне начать?

Question

У меня интересная проблема. Я столкнулся с функцией, которая занимает много времени для вычисления значения на основе некоторого индекса. Назовите это takes_a_long_time(index). Значения, возвращаемые этой функцией, гарантированно имеют глобальный минимум, но нет никаких гарантий, что индекс, связанный с, будет близок к нулю.

Поскольку takes_a_long_time принимает в качестве индекса произвольно большие натуральные числа, существуют уникальные ограничения на то, как начать двоичный поиск. Мне нужен способ создать конечный интервал для поиска точного минимума. Моей первой мыслью было проверить все большие интервалы, начиная с нуля. Что-то вроде:

def find_interval_with_minimum():
    start = 0
    end = 1
    interval_size = 1
    minimum_in_interval = check_minimum_in(start, end)
    while not minimum_in_interval:
        interval_size = interval_size * 2
        start = end
        end = start + interval_size
        minimum_in_interval = check_minimum_in(start, end)
    return start, end

Казалось бы, это работает нормально, но есть дополнительная деталь, которая действительно отбрасывает вещи. takes_a_long_time требует экспоненциально больше времени для вычисления значения, когда индексы приближаются к нулю. Поскольку для check_minimum_in потребуется несколько вызовов на takes_a_long_time, я бы хотел не начинать с нуля.

Так что мой вопрос, учитывая, что минимум может быть где угодно на [0, + бесконечность), есть ли какой-нибудь разумный способ запустить это "назад"? Или есть какая-то хорошая эвристика, которую можно использовать, чтобы избежать проверки низких индексов, если в этом нет необходимости?

Я бы хотел решение, не зависящее от языка. Тем не менее, я пишу это на Python, поэтому, если к этому применяется специфичный для Python подход, я бы тоже это принял.

Answer 1

Из комментариев к вопросу, кривая хорошо себя ведет, и вы можете использовать что-то вроде троичный поиск . Тогда единственная проблема заключается в том, как справиться с неудобным поведением при нулевом подходе. Так что не начинайте с нуля: определите новую функцию g из вашей функции f с помощью g(x) = f(1/x). Ищите это, начиная с x=0 и небольшого значения, удваивая или увеличивая размер интервала до тех пор, пока он не будет содержать минимум.

Чтобы сделать это, вам нужно знать предел f, когда его аргумент приближается к бесконечности, или эквивалентный предел g, когда его аргумент стремится к нулю. Если это не может быть оценено явно, я бы попробовал числовое приближение.

См. Комментарии к ответу, чтобы узнать, как увеличить размер интервала, особенно это касается Стива Джессопа.

Answer 2

Похоже, нужно выбрать большое число, достаточно большое, чтобы takes_a_long_time не занимало слишком много времени, чтобы быть приемлемым. Запустите два потока: один, который начинает смотреть в сторону положительной бесконечности для диапазона, содержащего минимум, и другой, который начинает смотреть в сторону нуля для диапазона, содержащего минимум. Из-за экспоненциального увеличения времени 0 также может находиться на бесконечности, что касается поиска. Какой бы поток ни нашел результат, отмените другой.

Но тогда, если вы не хотите использовать преимущества нескольких ядер ЦП, не запускайте два потока (и если вы это делаете, не запускайте ровно два потока, запускайте по одному на ядро ​​или около того). Просто чередуйте работу на стороне или на другой.

Учитывая эту базовую стратегию, теперь вам нужно настроить скорость, с которой вы приближаетесь к 0. Чем быстрее вы приближаетесь к нему, тем меньше шагов, чтобы найти минимум, если он действительно на этой стороне, но чем больше диапазон, оставшийся, чтобы быть двоичным искали, потому что в среднем вы будете "перебегать" дальше к нулю. Если кривая производительности является взаимно экспоненциальной, то, по-видимому, вы хотите сбросить как можно меньше, поэтому следует очень медленно приближаться к 0. Возможно даже, что ваша задача невыполнима в вычислительном отношении, «экспоненциальный» часто означает «невозможный».

Очевидно, я не могу ничего сказать о том, каким должно быть первоначальное «большое число». Сто терпимо? Это миллион? Номер Грэма? Если вы даже не знаете, что может иметь приемлемую производительность, вы можете узнать, запустив параллельно (опять же, через потоки или через ласточкин хвост) набор вычислений takes_a_long_time для разных индексов, пока один из них не завершится. Опять же, нет никакой гарантии, что это выполнимо в вычислительном отношении - если каждый отдельный индекс, который помещается в память вашего компьютера, занимает не менее миллиарда лет, вы застряли на практике, даже если у вас есть теоретическое решение.