Как найти максимум между двумя точками на дискретном графике?

Question

[koliane]

дан график из точек. Нужно найти максимальное значение между любыми двумя точками (включая сами эти крайние точки).

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

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

Пример:

Возьмем пару точек с порядковыми номерами {1,4}. Тут максимальное значение между ними = 4.
Возьмем пару точек с порядковыми номерами {4,5}. Тут максимальное значение между ними = 3.

Есть ли алгоритмы какие-то для этого? Можно ли вообще такое сделать?

Comments

[MagicMight]

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

[koliane]

MagicMight, дополнил вопрос, максимум мы должны получить только исходя из данных, хранящихся в этих двух точках

[MagicMight]

koliane, не хватает данных, чтобы ответить.

на входе программы - две точки

А остальные точки как представлены? Что за метаинформация?

[koliane]

MagicMight, задача программная, поэтому можно представить, что значение точки и метаинформацию мы храним в объекте, например, так:

{
     value: 4,
     meta1: 1.234,
     meta2: 4 
     ...
}

[MagicMight]

koliane, для всего остального графика точки известны? Весь миллион оставшихся?

[koliane]

MagicMight, да, конечно, т.е. есть, сами значения самих точек известны, если вы про это

[MagicMight]

koliane, я переформулирую задачу, а Вы скажете, насколько я близок к ее пониманию.
Есть условный миллион точек графика. При вводе пары любых точек (хоть разнесенных в разные концы графика), мы должны получить локальный максимум этого отрезка?

Предлагаю мысленный эксперимент. Миллион точек, на вход подается первая и последняя точка графика. Выходит, что пара точек должна хранить информацию о всех остальных точках графика, чтобы знать, какая из них максимальная. Пусть, для примера, она окажется 500-й. Меняем первую точку на тысячную. Мы получаем новое значение максимума, определенного почти на миллионе значений, поменяв всего одну точку?

[MagicMight]

koliane, у меня, все-таки, более фундаментальный вопрос.
В чем состоит изначальная задача, что нельзя потратить линейное время на перебор интервала?

[MagicMight]

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

[koliane]

Чуть ниже на часть вопроса уже ответил, но повторюсь)
тут дело в оптимизации производительности.
Мне за раз нужно найти несколько таких максимумов. Например, найти все пары точек, максимумы которых > 3.
Или например, найти все такие комбинации пар точек, где максимум одной пары >= 2* максимум другой пары точек и т.д.

Т.е., если иначе никак, то придется перебирать.

Предлагаю мысленный эксперимент. Миллион точек, на вход подается первая и последняя точка графика. Выходит, что пара точек должна хранить информацию о всех остальных точках графика, чтобы знать, какая из них максимальная. Пусть, для примера, она окажется 500-й. Меняем первую точку на тысячную. Мы получаем новое значение максимума, определенного почти на миллионе значений, поменяв всего одну точку?

Тут честно говоря, не совсем понял, про то, что мы меняем первую точку на тысячную. Если меняем исходные данные, то да, максимум должен быть другим, т.к. прежний максимум был 500й, а сейчас отсчет от 1000.

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

Т.е. я представляю какой-то такой вариант:
как по формуле, максимум=точка1*метаинформация2 - точка2*метаинформ....

Если добавляется в исходный набор точек, еще одна точка, то эта формула "пересобирается"

[MagicMight]

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

[koliane]

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

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

[MagicMight]

koliane, что сплайны, что интерполяционные полиномы - дикая вещь. Я молчу, например, про Лагранжа, где степень старшего члена определяется количеством узлов исходного дискретного графика.
Хранение формулы - половина беды. Представьте, что у Вас есть полином, выдающий значение в точке по координате. Чтобы вычислить того же лагранжа, надо будет по той же формуле сделать невероятное количество операций. Например, на первом шаге надо будет возвести число в миллионную степень. Потом в 999999, и так далее.

Answer 1

[Армянское Радио]

На дискретном графике максимум может быть только в узловой точке.

Comments

[MagicMight]

Собственно, о том и речь. Я не могу понять, в чем проблема простого перебора)

Answer 2

[Rsa97]

В каждой точке хранить массив максимумов справа от неё. Потом перебором до конца интервала искать значение.
1: {1: 1, 2: 2, 3: 4}
2: {2: 2, 3: 4}
3: {3: 4}
4: {4: 0.3, 5: 3}
5: {5: 3}
6: {6: 1}

{1, 4} => Берём массив в точке 1, движемся по нему, ближайшее меньшее 4 - 3. Максимум 4.

Comments

[koliane]

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

[MagicMight]

Массив каких максимумов? У него задача по поиску локального максимума на заданном вручную интервале.
Если мы разделим график на отрезки с шагом в 1, мы можем получить до миллиона максимумов (по миллиону точек, тк на каждом отрезке будет максимум), с шагом 2 - до полумиллиона.

[Rsa97]

koliane, MagicMight,
Всё просто. Если мы имеем доступ только к данным двух точек, то перебор непосредственно по точкам не получится.
Но можно заранее посмотреть, какие максимумы есть справа от точки и сохранить только их.
Решение сильно неуниверсальное, но как раз для ломаных линий, лежащих в ограниченном диапазоне значений оно может подойти.

[MagicMight]

Rsa97, автор сказал, что мы имеем, все-таки, доступ к данным остальных точек

[koliane]

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

[MagicMight]

koliane, так Вы определите задачу - надо получить эффективный алгоритм нахождения максимума на дискретном графике, а хранение информации - это Ваше предположение, или же хранение данных является нерушимым постулатом исходной задачи?

[koliane]

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

[MagicMight]

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

[koliane]

MagicMight, я эту задачу решаю с использованием графовой СУБД neo4j, а там такое представление данных)
Но все равно, интересно услышать про другие адекватные варианты

[MagicMight]

koliane,
Мои топовые графике в пеинте.
Сделать предрасчет 1000 локальных максимумов на интервалах [0...1000] [1000, 2000] , ...
Пусть есть две точки А и B. От точки A надо найти найти максимум, перебрав 300 элементов справа (до начала нового интервала). От точки B надо найти максимум, перебрав 400 элементов слева. Теперь у нас есть 4 числа - max(a'), max(m2), max(m3), max(b'). Найденный максимум на 4 значениях и есть максимум между A и B.
Таким образом, на интервале, содержащем 2700 точек, мы делаем (300+400+4 = 704) проверки.

[MagicMight]

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

[koliane]

MagicMight, на деле могут быть и сотни миллиардов точек, просто это будут достаточно редкие случаи, поэтому оптимизация бы не помешала

[MagicMight]

koliane, ну, тогда можно предрассчитать дерево максимумов по интервалам.
На каждой 1000 точек определить локальный максимум. Потом взять тысячу таких блоков, определить максимум на них, и т.д.
Выбирать интервалы, исходя из удаленности точек и перебирать не точки, а интервалы

[koliane]

MagicMight, да, так и попробую, либо что-то аналогичное с деревьями
Спасибо!

[MagicMight]

koliane, обращайтесь)

Answer 3

[Ritchi]

Апроксимируйте полиномом второй или третьей степени и найдите максимум по производной. Посмотрите по сплайны.

Comments

[koliane]

Не совсем понимаю, как можно сплайны прикрутить к этой задаче, чтобы найти максимум только по инфе двух точек.
И по производной может быть несколько максимумов, т.е. нужна еще будет доп. аналитика

[Ritchi]

Да, скорее всего это не то, что тут нужно