[Анализ и проектирование систем, Проектирование и рефакторинг, Математика, Параллельное программирование, Промышленное программирование] Что сказал-то?
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
«То что ясно всем, ещё кто-то должен сказать»
Типа эпиграфа, Google/Яндекс автора не сыскали
Это вторая часть статьи «То что ясно всем».
Для лучшего понимания изложенного в ней алгоритма Z добавлю здесь удачный пример, приведённый ранее в обсуждении/комментах.
Представьте себе, что стоит задача построить кривую некоей функции Т(Х) на заданном интервале (допустимых) значений. Сделать это желательно максимально подробно, но вы заранее не знаете, когда вас «схватят за руку». Вы хотите генерировать значения Х так, чтобы в любой момент, когда прервётся построение кривой (генерация параметров Х на интервале и вычисление Т(Х)), получившийся график максимально точно отражал эту функцию. Окажется больше времени — график будет точнее, но — всегда максимум из возможного на данный момент для произвольной функции.
Конечно, для известной функции алгоритм разбиения интервала может учитывать её поведение, но здесь речь идёт об общем подходе, дающем искомый результат с минимальными «потерями». Для двумерного случая можно привести пример отображения некоего рельефа/поверхности и желать быть уверенным, что сколько успели — отобразили максимум его особенностей.
Задача и объекты моделирования (из первой части) в общем случае могут сильно различаться: есть теоретическая/физическая модель или приближение или нет этого (чёрный ящик) — везде будут свои нюансы в построении моделей. Но необходимость генерации параметров (в т.ч. алгоритм Z) — общая и неотъемлемая часть для всех. Есть объекты (например такие), когда время на получение Т слишком велико (дни и недели), тогда алгоритм выбора нового шага останавливается по другим критериям, не по причине завершения цикла основного расчёта в параллельном процессе. Нет смысла далее уменьшать шаг для улучшения поиска следующего прогноза Т, если ожидаемое улучшение заведомо хуже погрешности модели и/или ошибок измерения Т.
Приведу ещё одну иллюстрацию разбиения допустимого интервала для двумерного случая алгоритма Z (K = 3 на поле 64*64):
Точки, выделенные на рисунке (9 шт.) — это начальные точки краёв и середины интервала, они, если это необходимо, считаются вне алгоритма Z. Можно заметить, что по горизонтальным и вертикальным направлениям/«дорожкам», соединяющим эти точки, генерируемые алгоритмом Z значения не попадают. Дополнительные точки тут несложно рассчитать отдельно, но с ростом числа точек вдоль этих направлений/«дорожек» представление функции будет улучшаться («дорожки» становятся уже) и необходимости дополнять сам алгоритм (надо 7 строк, из них 4 оператора в основном цикле по n, см. ниже) или создавать отдельный расчёт я не вижу. Тем более, что в этом случае ухудшается средняя эффективность алгоритма, а особого улучшения представления модели не будет (уже при n > 4 шаг по параметру меньше 1/1000, см. таблицу ниже).
Второй особенностью алгоритма Z является (для двумерного случая) несимметрия порядка добавления точек — по оси/параметру Y они в среднем чаще, картина выравнивается в конце каждого цикла по n.
Алгоритм Z, одномерный случай, на языке VBA:
Xmax =
Xmin =
Dx = (Xmax - Xmin) / 2
L = 2
Sx = 0
For n = 1 To K
Dx = Dx / 2
D = Dx
For j = 1 To L Step 2
X = Xmin + D
Cells(5, X) = "O" 'здесь и ниже - вызов/расчёт модели T(X)
X = Xmax - D
Cells(5, X) = "O"
D = D + Sx
Next j
Sx = Dx
L = L + L
Next n
Алгоритм Z, двумерный случай, язык VBA:
Xmax = ' 65 - значения для примера выше, GIF
Xmin = ' 1
Ymax = ' 65
Ymin = ' 1
Dx = (Xmax - Xmin) / 2
Dy = (Ymax - Ymin) / 2
L = 2
Sx = 0
Sy = 0
For n = 1 To K ' K = 3 для примера GIF
Dx = Dx / 2
Dy = Dy / 2
Tx = Dx
For j = 1 To L Step 2
X1 = Xmin + Tx
X2 = Xmax - Tx
Ty = Dy
For i = 1 To L Step 2
Y = Ymin + Ty
Cells(Y, X1) = "O" 'здесь и ниже - вызов/расчёт модели T(Y,X)
Cells(Y, X2) = "O"
Y = Ymax - Ty
Cells(Y, X1) = "O"
Cells(Y, X2) = "O"
Ty = Ty + Sy
Next i
Tx = Tx + Sx
Next j
Sx = Dx
Sy = Dy
L = L + L
Next n
Вычислительные затраты:
В квадратных скобках обозначены основные операции, используемые в расчётах (затраты на организацию циклов не учитываются).
Здесь надо заметить, что достаточно «тяжёлая» операция деления [÷] в данном случае не является затратной, ибо целочисленное деление на 2 — это сдвиг на один разряд. Относительные затраты на операцию деления и присваивания ([=], второе слагаемое) с ростом K быстро стремятся к нулю.
Всего точек:
Средние затраты:
Для первых значений K проведём расчёты по этим формулам и заполним таблицу:
Здесь «доля интервала» — относительный шаг между точками в конце цикла по n.
Последняя строка («среднее») показывает относительные затраты на точку — долю сложений/вычитаний. Предел стремится к 0,5625 или ~1/1,7(7) операции сложения.
Возвращаясь к утверждению из первой части статьи, здесь показано что «предлагаемый к обсуждению алгоритм демонстрирует предельно малые вычислительные затраты и не влечёт недостатков или сложностей», а в условиях внезапного прерывания вычислений дополнительно имеет преимущества. Разумно его использовать во всех подходящих применениях.
Прошу помощи в распространении и внедрении как в программном, так и аппаратном исполнении.
===========
Источник:
habr.com
===========
Похожие новости:
- [Клиентская оптимизация, Управление сообществом, Управление e-commerce, Контент-маркетинг, Email-маркетинг] What is an SEO Company?
- [Big Data, Научно-популярное, Лайфхаки для гиков, Будущее здесь] Что в контенте тебе моем? Многовековая эволюция и основные принципы персонализации контента
- [TensorFlow] Оптимизация моделей в Tensorflow 1.x
- [Математика] Вычисляем последовательность Фибоначчи за логарифмическое время (перевод)
- [Исследования и прогнозы в IT, Карьера в IT-индустрии] Зачем тратить деньги на юристов?
- [Анализ и проектирование систем, ERP-системы, Научно-популярное] Ваши АСУ ни разу ни… У
- [Алгоритмы] Укрощаем динамику в задаче о палиндромах
- [Математика, Бизнес-модели] Цепочки поставок с учетом производственно-коммерческих ограничений
- [Семантика] Когда можно обойтись без SEO или каким проектам поисковая оптимизация не нужна
- [Промышленное программирование, Разработка робототехники, Программирование микроконтроллеров, Производство и разработка электроники] ModBus Slave RTU/ASCII без смс и регистрации. Версия 3
Теги для поиска: #_analiz_i_proektirovanie_sistem (Анализ и проектирование систем), #_proektirovanie_i_refaktoring (Проектирование и рефакторинг), #_matematika (Математика), #_parallelnoe_programmirovanie (Параллельное программирование), #_promyshlennoe_programmirovanie (Промышленное программирование), #_optimizatsija (оптимизация), #_optimizatsija_programm (оптимизация программ), #_algoritmy (алгоритмы), #_minimizatsija_zatrat (минимизация затрат), #_analiz_i_proektirovanie_sistem (
Анализ и проектирование систем
), #_proektirovanie_i_refaktoring (
Проектирование и рефакторинг
), #_matematika (
Математика
), #_parallelnoe_programmirovanie (
Параллельное программирование
), #_promyshlennoe_programmirovanie (
Промышленное программирование
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 22:33
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
«То что ясно всем, ещё кто-то должен сказать» Типа эпиграфа, Google/Яндекс автора не сыскали Это вторая часть статьи «То что ясно всем». Для лучшего понимания изложенного в ней алгоритма Z добавлю здесь удачный пример, приведённый ранее в обсуждении/комментах. Представьте себе, что стоит задача построить кривую некоей функции Т(Х) на заданном интервале (допустимых) значений. Сделать это желательно максимально подробно, но вы заранее не знаете, когда вас «схватят за руку». Вы хотите генерировать значения Х так, чтобы в любой момент, когда прервётся построение кривой (генерация параметров Х на интервале и вычисление Т(Х)), получившийся график максимально точно отражал эту функцию. Окажется больше времени — график будет точнее, но — всегда максимум из возможного на данный момент для произвольной функции. Конечно, для известной функции алгоритм разбиения интервала может учитывать её поведение, но здесь речь идёт об общем подходе, дающем искомый результат с минимальными «потерями». Для двумерного случая можно привести пример отображения некоего рельефа/поверхности и желать быть уверенным, что сколько успели — отобразили максимум его особенностей. Задача и объекты моделирования (из первой части) в общем случае могут сильно различаться: есть теоретическая/физическая модель или приближение или нет этого (чёрный ящик) — везде будут свои нюансы в построении моделей. Но необходимость генерации параметров (в т.ч. алгоритм Z) — общая и неотъемлемая часть для всех. Есть объекты (например такие), когда время на получение Т слишком велико (дни и недели), тогда алгоритм выбора нового шага останавливается по другим критериям, не по причине завершения цикла основного расчёта в параллельном процессе. Нет смысла далее уменьшать шаг для улучшения поиска следующего прогноза Т, если ожидаемое улучшение заведомо хуже погрешности модели и/или ошибок измерения Т. Приведу ещё одну иллюстрацию разбиения допустимого интервала для двумерного случая алгоритма Z (K = 3 на поле 64*64):  Точки, выделенные на рисунке (9 шт.) — это начальные точки краёв и середины интервала, они, если это необходимо, считаются вне алгоритма Z. Можно заметить, что по горизонтальным и вертикальным направлениям/«дорожкам», соединяющим эти точки, генерируемые алгоритмом Z значения не попадают. Дополнительные точки тут несложно рассчитать отдельно, но с ростом числа точек вдоль этих направлений/«дорожек» представление функции будет улучшаться («дорожки» становятся уже) и необходимости дополнять сам алгоритм (надо 7 строк, из них 4 оператора в основном цикле по n, см. ниже) или создавать отдельный расчёт я не вижу. Тем более, что в этом случае ухудшается средняя эффективность алгоритма, а особого улучшения представления модели не будет (уже при n > 4 шаг по параметру меньше 1/1000, см. таблицу ниже). Второй особенностью алгоритма Z является (для двумерного случая) несимметрия порядка добавления точек — по оси/параметру Y они в среднем чаще, картина выравнивается в конце каждого цикла по n. Алгоритм Z, одномерный случай, на языке VBA: Xmax =
Xmin = Dx = (Xmax - Xmin) / 2 L = 2 Sx = 0 For n = 1 To K Dx = Dx / 2 D = Dx For j = 1 To L Step 2 X = Xmin + D Cells(5, X) = "O" 'здесь и ниже - вызов/расчёт модели T(X) X = Xmax - D Cells(5, X) = "O" D = D + Sx Next j Sx = Dx L = L + L Next n Алгоритм Z, двумерный случай, язык VBA: Xmax = ' 65 - значения для примера выше, GIF
Xmin = ' 1 Ymax = ' 65 Ymin = ' 1 Dx = (Xmax - Xmin) / 2 Dy = (Ymax - Ymin) / 2 L = 2 Sx = 0 Sy = 0 For n = 1 To K ' K = 3 для примера GIF Dx = Dx / 2 Dy = Dy / 2 Tx = Dx For j = 1 To L Step 2 X1 = Xmin + Tx X2 = Xmax - Tx Ty = Dy For i = 1 To L Step 2 Y = Ymin + Ty Cells(Y, X1) = "O" 'здесь и ниже - вызов/расчёт модели T(Y,X) Cells(Y, X2) = "O" Y = Ymax - Ty Cells(Y, X1) = "O" Cells(Y, X2) = "O" Ty = Ty + Sy Next i Tx = Tx + Sx Next j Sx = Dx Sy = Dy L = L + L Next n Вычислительные затраты:  В квадратных скобках обозначены основные операции, используемые в расчётах (затраты на организацию циклов не учитываются). Здесь надо заметить, что достаточно «тяжёлая» операция деления [÷] в данном случае не является затратной, ибо целочисленное деление на 2 — это сдвиг на один разряд. Относительные затраты на операцию деления и присваивания ([=], второе слагаемое) с ростом K быстро стремятся к нулю. Всего точек:  Средние затраты:  Для первых значений K проведём расчёты по этим формулам и заполним таблицу:  Здесь «доля интервала» — относительный шаг между точками в конце цикла по n. Последняя строка («среднее») показывает относительные затраты на точку — долю сложений/вычитаний. Предел стремится к 0,5625 или ~1/1,7(7) операции сложения. Возвращаясь к утверждению из первой части статьи, здесь показано что «предлагаемый к обсуждению алгоритм демонстрирует предельно малые вычислительные затраты и не влечёт недостатков или сложностей», а в условиях внезапного прерывания вычислений дополнительно имеет преимущества. Разумно его использовать во всех подходящих применениях. Прошу помощи в распространении и внедрении как в программном, так и аппаратном исполнении. =========== Источник: habr.com =========== Похожие новости:
Анализ и проектирование систем ), #_proektirovanie_i_refaktoring ( Проектирование и рефакторинг ), #_matematika ( Математика ), #_parallelnoe_programmirovanie ( Параллельное программирование ), #_promyshlennoe_programmirovanie ( Промышленное программирование ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 22:33
Часовой пояс: UTC + 5