Быстрый алгоритм поиска максимума в колоколообразном списке значений

Question

У меня есть список значений, который увеличивается до максимума, а затем снова уменьшается (это наблюдаемое распределение Гаусса / колоколообразное).

values = [0, 4, 5, 15, 30, 20, 10, 5, 0];

Но распределение также может быть смещено:

values = [0, 0, 0, 1, 2, 3, 8, 15, 30];

Или аналогично:

values = [30, 20, 5, 2, 1, 1, 0, 0, 0];

Определение значения по определенному индексу очень дорого в этом конкретном приложении, поэтому важно использовать как можно меньше поисков в массиве.

Такие решения, как восхождение на гору или вариант бинарного поиска, должны работать. Что такое алгоритм с наименьшими возможными шагами?

Долгое время поиска обусловлено реальным измерительным устройством (время в секундах).

Answer 1

Вы ищете троичный поиск, возможно, с некоторой эвристикой из интерполяционного поиска.

Начнем с

def search(f, begin, end):
    if end - begin <= 3:
        return max(map(f, range(begin, end)))
    low = (begin * 2 + end) / 3
    high = (begin + end * 2) / 3
    if f(low) > f(high):
        return search(f, begin, high - 1)
    else:
        return search(f, low + 1, end)

Асимптотически это лучшее, что вы можете сделать, не полагаясь на некоторые свойства ваших значений. Если это не достаточно хорошо, измените выражения для low а также high чтобы лучше соответствовать вашим реальным данным.

Answer 2

Предполагая, что у вас нет локальных максимумов (как это обычно бывает с измерениями), двоичный поиск является самым быстрым способом. Если у вас, скажем, 1000 точек данных, вы получите около 10 проверок в худшем случае, когда максимум находится где-то посередине.

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

Answer 3

Как отметил Ф.Давидов, вы должны использовать вариант бинарного поиска, так как вам нужен только доступ вокруг ceil[O(logn)] индексы в худшем случае.

Псевдокод варианта бинарного поиска будет выглядеть так:

left := 0
right := n - 1
while left < right do
    mid := left + (right - left) / 2
    if values[mid] > values[mid + 1] 
         right := mid
    else
         left := mid 
end

print left

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

Если вам не нужен точный результат и близкое приближение приемлемо, вы можете попробовать троичный поиск.