Comments 28
Скажите, а зачем нужно прерывать процесс расчёта модели при получении очередного значения целевой функции? Это из-за поступления информации от объекта в реальном времени?
… прерывать процесс расчёта моделиэто не расчёт модели, а поиск/подбор следующего шага, дающего наиболее информативный в текущей ситуации ответ от объекта. А объект уже дал новую точку, надо её учесть в промежуточной модели, поэтому поиск прекращаем, что нашли — для нового расчёта Т, а модель уточняем по «вновь возникшим обстоятельствам» :) и уже на ней ищем следующий шаг, тестирующий объект. И ищем/уточняем столько времени, сколько идёт главный расчёт Т.
Процедура задания каждого нового значения параметра в процессе исследования такого объекта уже не может быть тривиальной (равномерный шаг), она высоко затратна, и должна учитывать, по возможности, всю уже имеющуюся информацию о поведении Т.
Не смог найти в предложенном алгоритме, как получаемые значения функции Т влияют на выбор новых значений аргумента Х. Кажется, одно на другое не влияет. И в гифке функция никак не фигурирует, одни аргументы.
Новые значения Т добавляют информации об исследуемом (и моделируемом) объекте, а значит промежуточную модель, на основе которой определяется оптимальный следующий шаг, надо тоже уточнить. Алгоритм получения нового набора параметров для следующего расчёта Т использует в т.ч. процедуру/алгоритм Z. Что делает алгоритм Z — лучше прочитать в статье, в том абзаце, где он первый раз упоминается. Будет ясно, почему на гифке речь об аргументах/параметрах.
Попытался, просветления не произошло. Это не значит, что так происходит со всеми или даже с большинством читающих. Не исключаю, что всем остальным идея предельно ясна. Тем не менее, есть мое личное впечатление, что чего-то не хватает для понятности. К примеру, на примере упоминаемой в статье функции описать пару-тройку шагов с привязкой действий к шагам из схемы (блок-схемы? псевдокода?)… Что-то в таком ключе.
Попробую пояснить совсем уж «округлённо».
Статью можно разделить на 2 части:
1) описан алгоритм (Z) генерации числовых значений параметра на заданном интервале в последовательности (генерации), оптимальной для аппроксимации произвольной функции от этого параметра и имеющий предельно малые вычислительные затраты. Во второй части статьи опубликую код алгоритма с заявленными параметрами.
2) приведён подход к моделированию объекта, когда каждая новая его точка «дорого стоит». Алгоритм Z может использоваться по прямому назначению для работы с промежуточной (итерационно обновляемой) моделью объекта.
Статью можно разделить на 2 части:
1) описан алгоритм (Z) генерации числовых значений параметра на заданном интервале в последовательности (генерации), оптимальной для аппроксимации произвольной функции от этого параметра и имеющий предельно малые вычислительные затраты. Во второй части статьи опубликую код алгоритма с заявленными параметрами.
2) приведён подход к моделированию объекта, когда каждая новая его точка «дорого стоит». Алгоритм Z может использоваться по прямому назначению для работы с промежуточной (итерационно обновляемой) моделью объекта.
Во второй части статьи опубликую код алгоритма
Ну так наверняка яснее станет.
Пришёл в голову пример, поясняющий 1) из поста выше:
Представьте себе, что стоит задача построить кривую простой функции, например, Т = Х*Х на интервале (0, 2).
Сделать это надо максимально подробно, но вы заранее не знаете, когда вас «схватят за руку». Вы хотите генерировать значения Х так, чтобы в любой момент получившийся график Т(Х) максимально точно отражал функцию Т. Будет больше времени — будет точнее график, но всегда максимум из возможного на данный момент для произвольной функции.
Гифка в тексте иллюстрирует способ генерации значений, решающих задачу. То, что и вычислительные затраты минимальны — это уже второй бонус.
Представьте себе, что стоит задача построить кривую простой функции, например, Т = Х*Х на интервале (0, 2).
Сделать это надо максимально подробно, но вы заранее не знаете, когда вас «схватят за руку». Вы хотите генерировать значения Х так, чтобы в любой момент получившийся график Т(Х) максимально точно отражал функцию Т. Будет больше времени — будет точнее график, но всегда максимум из возможного на данный момент для произвольной функции.
Гифка в тексте иллюстрирует способ генерации значений, решающих задачу. То, что и вычислительные затраты минимальны — это уже второй бонус.
Постановка задачи теперь понятна (до этого условие внезапного «схватывания за руку» как-то было нечетко).
Следуем текстовому описанию:
1) Т(0) = 0
2) Т(1) = 1
3) Т(2) = 4
Далее:
Имеем отрезки X [0, 1] и [1, 2]. Середины будут Х = 0.5 и Х = 1.5.
Соответственно, следующие шаги:
4) Т(0.5) = 0.25
5) Т(1.5) = 2.25
Здесь все верно?
Замечу, что здесь мы уже сильно разошлись с гифкой.
Т = Х*Х на интервале (0, 2).
Следуем текстовому описанию:
Сначала производится расчёт по модели T(X) на 3-х точках: Xmin, (Xmin + Xmax)/2 и Xmax, т.е. по краям и посередине допустимого интервала (Xmin, Xmax).
1) Т(0) = 0
2) Т(1) = 1
3) Т(2) = 4
Далее:
Далее каждый отрезок делится пополам и вычисляются значения в серединах каждого отрезка и т.д.
Имеем отрезки X [0, 1] и [1, 2]. Середины будут Х = 0.5 и Х = 1.5.
Соответственно, следующие шаги:
4) Т(0.5) = 0.25
5) Т(1.5) = 2.25
Здесь все верно?
Замечу, что здесь мы уже сильно разошлись с гифкой.
На гифке:
2.1) изначально есть мин и макс. Пусть это Х = 0 и Х = 2 по нашему примеру.
2.2) Х = 0.5
2.3) Х = 0.75
Сравниваем с моим «проходом по шагам» выше. Шаг (2.1) здесь соответствует шагам (1) и (3). А шаг (2) в гифке отсутствует. Перед шагом (2.2) Х должен принять значение 1.
2.1) изначально есть мин и макс. Пусть это Х = 0 и Х = 2 по нашему примеру.
2.2) Х = 0.5
2.3) Х = 0.75
Сравниваем с моим «проходом по шагам» выше. Шаг (2.1) здесь соответствует шагам (1) и (3). А шаг (2) в гифке отсутствует. Перед шагом (2.2) Х должен принять значение 1.
Тут вы ошиблись, в примере интервал (0,2), а не (0,1). Точки 0, 1 и 2 — они до того считаются, алгоритм Z генерит остальное.
Представьте всё генерируемое не абс.значениями, а долями от длины интервала — и увидите, что гифка правильно отображает: 0,25 — 0,75 / 0.125 — 0,875 — 0,375 — 0,625 / 0,0625 и т.д.
Звучит как панацея. Автору необходимо уточнить к какому классу задач (подозреваю, линейным функциям переменных первого порядка) относится его статья и алгоритм. Также было бы неплохо математически доказать все высказывания из статьи.
«подозреваю, линейным функциям переменных первого порядка» — не надо ругаться :) Прочтите ещё пару раз статью, менее 3-х страниц всего. Похоже, вы не разобрались, и комментарии тоже прочтите — ваш коллега (yevgen12) начал понимать.
А насчёт «доказать» — из такового пока привел две цифры: 3/2 и 3/4 (пределы, к которым стремятся вычислительные затраты на одно значение параметра при большом количестве генерируемых точек) и эти цифры можно будет «потрогать» и проверить во второй части статьи. Там всё будет ясно (см. название статьи).
Постараюсь выложить на этой неделе.
А насчёт «доказать» — из такового пока привел две цифры: 3/2 и 3/4 (пределы, к которым стремятся вычислительные затраты на одно значение параметра при большом количестве генерируемых точек) и эти цифры можно будет «потрогать» и проверить во второй части статьи. Там всё будет ясно (см. название статьи).
Постараюсь выложить на этой неделе.
Ну в общем и целом, наверное, сам замысел я теперь понял. Навроде метода половинного деления. Только там движение сходится к решению (при наличии некоторых условий), а здесь мы движемся… в разные стороны.
При постановке задачи с внезапным «хватанием за руку» рациональное зерно есть.
Рассмотрим другой пример. Интервал от 0 так же до 2. При этом на интервале от 0 до 1.9 Т(Х) близка к линейной, а на оставшейся части имеет 20 экстремумов. Это, как вариант, полином 21-й степени.
При большом числе шагов на линейную часть будет затрачено 95% ресурсов.
Вопрос: оптимально ли решается задача?
Ответ: зависит от критерия оптимизации)
Вот это бы почетче, какая экономия нужна. Мы считаем затраты, отнесенные к количеству точек? Но стоимость каждой точки одинакова, если не брать в расчет вычисление нового значения Х (у нас ведь именно Т(Х) получить дорого стоит?). Общее количество точек определяется моментом «схватывания за руку» и от алгоритма выбора значений Х не зависит.
Наиболее ясна для меня следующая постановка:
Но если от этого отталкиваться, то критерий должен быть завязан на качество модели. То есть если предлагаемый алгоритм лучше остальных, то это значит, что он обеспечивает максимальное качество модели (измеряемое такими-то и такими-то показателями — отдельный вопрос критериев) при равном количестве шагов вычислений.
При постановке задачи с внезапным «хватанием за руку» рациональное зерно есть.
Рассмотрим другой пример. Интервал от 0 так же до 2. При этом на интервале от 0 до 1.9 Т(Х) близка к линейной, а на оставшейся части имеет 20 экстремумов. Это, как вариант, полином 21-й степени.
При большом числе шагов на линейную часть будет затрачено 95% ресурсов.
Вопрос: оптимально ли решается задача?
Ответ: зависит от критерия оптимизации)
Автор утверждает, что не существует более экономичного алгоритма с точки зрения вычислительных затрат на генерируемую точку.
Вот это бы почетче, какая экономия нужна. Мы считаем затраты, отнесенные к количеству точек? Но стоимость каждой точки одинакова, если не брать в расчет вычисление нового значения Х (у нас ведь именно Т(Х) получить дорого стоит?). Общее количество точек определяется моментом «схватывания за руку» и от алгоритма выбора значений Х не зависит.
Наиболее ясна для меня следующая постановка:
Сделать это надо максимально подробно, но вы заранее не знаете, когда вас «схватят за руку». Вы хотите генерировать значения Х так, чтобы в любой момент получившийся график Т(Х) максимально точно отражал функцию Т. Будет больше времени — будет точнее график, но всегда максимум из возможного на данный момент для произвольной функции.
Но если от этого отталкиваться, то критерий должен быть завязан на качество модели. То есть если предлагаемый алгоритм лучше остальных, то это значит, что он обеспечивает максимальное качество модели (измеряемое такими-то и такими-то показателями — отдельный вопрос критериев) при равном количестве шагов вычислений.
наверное, сам замысел я теперь понял.Самое время ещё раз прочесть статью :)
Только там движение сходится к решению (при наличии некоторых условий), а здесь мы движемся… в разные стороны.Ну, во-первых, не в разные стороны, а от краёв интервала к середине. А во-вторых, здесь работает фактор максимизации полученного решения (наилучший следующий шаг) от итерационной модели исследуемого «тяжёлого» объекта за то время, которое окажется в распоряжении процедуры выбора шага (и там внутри используется алгоритм Z). Никакого «сходится к решению» нет (зъист то она зъист, только кто ж ей даст :)
Вопрос: оптимально ли решается задача?
Никакая «задача в общем» не может решаться оптимально:
… будет точнее график, но всегда максимум из возможного на данный момент для произвольной функции.
нас ведь именно Т(Х) получить дорого стоит?Различайте стоимость расчёта/получения Т(Х) и стоимость (никакую в сравнении с первым) расчёта по итеративно обновляемой модели Т(Х).
если предлагаемый алгоритм лучше остальных, то это значит, что он обеспечивает максимальное качество моделиНельзя говорить о качестве модели в общем случае, это не цель статьи. «он обеспечивает максимальное качество» расчёта следующего шага за то время, которое оказалось в распоряжении поиска. Потому что время, затраченное на некоторые вспомогательные процедуры (алгоритм Z) было минимально возможным. А качество и затраты на построение и итерационное обновление модели и собственно на выбор следующего шага — это другая задача, не решаемая в общем смысле — всегда свои частности.
Это применимо же только тогда, когда модель априори задана, полином, например, или сумма гармоник и просто увеличиваем количество членов для большей точности? Перейти от полинома к гармоника не получится, так?
Закройте, наконец, учебник — в жизни нет никаких полиномов и гармоник! Зато есть ошибки измерения, физические и теоретические модели объектов, которым не хватает данных и полноты представления, и настоящие "чёрные ящики", про содержимое (и взаимовлияние) которых априори не известно почти ничего!
И здесь не обсуждается сама модель и способ поиска оптимального следующего шага, ибо это сильно индивидуально. А только общий подход и алгоритм (Z) исследования/тестирования модели итерационной, которая будет приближаться к искомой.
И здесь не обсуждается сама модель и способ поиска оптимального следующего шага, ибо это сильно индивидуально. А только общий подход и алгоритм (Z) исследования/тестирования модели итерационной, которая будет приближаться к искомой.
Главная проблема статьи в том, что автор думает, что заголовок многое объясняет.
Я понимаю, что автор находится в своем контексте и окружен этой проблемой, которую описывает в статье. А поэтому многие вещи считает понятными и не требующими объяснения. А выбор хабов и тегов, видимо, должны сделать все остальное.
Но есть огромное количество людей для которых тема далека от повседневности. Им нужны вводные данные или может быть тема ТУ вовсе не интересна
Я не знаю как эта статья попала мне в выдачу, но т.к. попала, то и оцениваю из своего контекста: постановка задачи не ясна, область решаемых задач не определена, заголовок ни о чем.
Человек, который будет искать решение подобной задачи никогда не найдет этой статьи, и не подумает ее открыть в поисках решения. Я надеюсь автор исправится, поправит статью и десятки или сотни людей, для которых тема актуальна, смогут использовать решение из второй части на практике и дадут автору фидбек.
Я понимаю, что автор находится в своем контексте и окружен этой проблемой, которую описывает в статье. А поэтому многие вещи считает понятными и не требующими объяснения. А выбор хабов и тегов, видимо, должны сделать все остальное.
Но есть огромное количество людей для которых тема далека от повседневности. Им нужны вводные данные или может быть тема ТУ вовсе не интересна
Я не знаю как эта статья попала мне в выдачу, но т.к. попала, то и оцениваю из своего контекста: постановка задачи не ясна, область решаемых задач не определена, заголовок ни о чем.
Человек, который будет искать решение подобной задачи никогда не найдет этой статьи, и не подумает ее открыть в поисках решения. Я надеюсь автор исправится, поправит статью и десятки или сотни людей, для которых тема актуальна, смогут использовать решение из второй части на практике и дадут автору фидбек.
Спасибо за ответ. Действительно, находясь глубоко в проблеме, трудно выстроить «тропинку», доходчиво приводящую к пониманию изложенного для стороннего читателя. Здесь дилемма: или много и подробно, тогда устанут читать и разбираться, или кратко (менее 3 страниц), а непонятое пояснить в комментах. Во второй части добавлю поясняющие примеры с учётом комментариев.
Насчёт выдачи в ленту — полагаю, это не заголовком определяется, а ключевыми словами и индексацией. В отборе первых не силён, мог и напутать — подскажите.
автор думает, что заголовок многое объясняетНет, он отражает незнание — кто уже этой проблемой занимался и как её решал. Мне кажется, что решение общей задачи (Т) достаточно ясно изложено (можно ещё раз прочитать + комменты), а предложенный (и обязательный) компонент её решения (алгоритм Z) хоть и прост — это я так думаю, но для других может оказаться и неочевидным. Зато Z имеет веское право на существование из-за минимальности вычислительных затрат при «правильном» порядке выдачи значений.
Насчёт выдачи в ленту — полагаю, это не заголовком определяется, а ключевыми словами и индексацией. В отборе первых не силён, мог и напутать — подскажите.
Для одномерного случая при достаточно большом количестве точек, получаемых на интервале (Xmin, Xmax), вычислительные затраты стремятся к 3/2 операции сложения (или вычитания, считаем их эквивалентными) на точку. Более простыми операциями присвоения и организации циклов пренебрегаем, ибо цикл и так участвует в самой процедуре аппроксимации.
Для двумерного случая вычислительные затраты стремятся к ¾ (!) операции сложения.
Автор утверждает, что не существует более экономичного алгоритма с точки зрения вычислительных затрат на генерируемую точку.
Экономичный алгоритм генерации точек? Хм.
Во-первых, доля времени генерации точек в алгоритме оптимизации обычно невелика. Скорость равномерной "генерации точек" обычным циклом for — порядка миллиарда точек в секунду. Это и так неплохо. Оптимизируя скорость генерации, весь алгоритм существенно не ускорить.
Во-вторых, вы уверены, что "Для двумерного случая вычислительные затраты стремятся к ¾ (!) операции сложения"? Означает ли это, что для генерации 100 различных точек достаточно 75 операций АЛУ? Это звучит очень неправдоподобно. Приведите, пожалуйста, подробный протокол генерации точек — формулы для генерации 100 точек (или хотя бы 20 точек), где арифметико-логических операций около 75 (или около 15 в сокращённом варианте).
Во-первых, вы правы, но я об этом сказал:
Чтобы реализовать эти преимущества с обычным подходом (дихотомия) потребовались бы дополнительные программные сложности и вычислительные затраты.
Во-вторых, да, парадоксально, но
На этой неделе!
Конечно, доля вычислительных затрат на получение набора значений каждого параметра с заданным шагом… обычно намного меньше затрат на остальные расчёты по выбору шага для оценки ТНо вы не учли ещё важные преимущества алгоритма Z:
В среднем плотность точек, генерируемых алгоритмом Z, выше на краях диапазона...и из комментариев:
Зато Z имеет веское право на существование из-за минимальности вычислительных затрат при «правильном» порядке выдачи значений.и тут.
Чтобы реализовать эти преимущества с обычным подходом (дихотомия) потребовались бы дополнительные программные сложности и вычислительные затраты.
Во-вторых, да, парадоксально, но
при достаточно большом количестве точек(100, и тем более 20, точек это уже большое?) затраты на одну точку в двумерном случае будут стремиться к 3/4 сложения/вычитания. В этом можно будет легко убедиться во второй части статьи, ибо текст программы (на VBA) прост — менее 25 операторов основного цикла.
На этой неделе!
Вы можете привести пример лога с "достаточно большим" количеством точек. Кстати, сколько это?
Вместе с текстом программы готовлю аналитическое выражение для количества всех операций, необходимых для получения одной точки в зависимости от их числа К. Предел при К ⇒ ∞ покажет картину вычислительных затрат. Можно будет и график от К нарисовать.
Например, для 196 точек (размерность 2, аналог показанного на GIF одномерного случая) потребуется 171/196 операций сложения, уже менее одного сложения/вычитания на точку.
Например, для 196 точек (размерность 2, аналог показанного на GIF одномерного случая) потребуется 171/196 операций сложения, уже менее одного сложения/вычитания на точку.
Уточнение: для 84 точек (размерность 2, аналог показанного на GIF одномерного случая, цикл 3) потребуется в среднем 90/84 операций сложения, а в следующем цикле (4), для 340 точек — 308/340, т.е. уже менее одного сложения/вычитания на точку.
Быть может, точки у вас имеют совпадающие отдельные координаты?
Например, оси X,Y, вычисляем x0=a, y0=b, x1=x0+c, y1=y0+d. Это формально 2 сложения. И мы можем получить 4 точки (x0,y0), (x1,y0), (x0,y1), (x1,y1), если запомним (в массивах?) числа x0, x1, y0, y1.
Операция доступа к массиву на типичных архитектурах содержит (целочисленное) сложение (x[1] это *(x+1)), но, думаю, в каких-то случаях (прямая адресация) или в каких-то других архитектурах можно просто выставить адрес (или номер регистра) на шине. Так что, формально, операций сложения (особенно если считать только сложения с плавающей запятой) действительно может быть меньше, чем точек.
Поправил в тексте статьи последнюю ссылку, извиняюсь.
Sign up to leave a comment.
То что ясно всем