Русский
Русский
English
Статистика
Реклама

Что сказал-то?

То что ясно всем, ещё кто-то должен сказать
Типа эпиграфа, 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) / 2L = 2Sx = 0For 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 + LNext n

Алгоритм Z, двумерный случай, язык VBA:

Xmax = '65 - значения для примера выше, GIFXmin = '1Ymax = '65Ymin = '1Dx = (Xmax - Xmin) / 2Dy = (Ymax - Ymin) / 2L = 2Sx = 0Sy = 0For n = 1 To K'K = 3для примера GIF      Dx = Dx / 2      Dy = Dy / 2      Tx = Dx      For j = 1 To L Step 2X1 = Xmin + Tx        X2 = Xmax - TxTy = 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 + LNext n

Вычислительные затраты:



В квадратных скобках обозначены основные операции, используемые в расчётах (затраты на организацию циклов не учитываются).

Здесь надо заметить, что достаточно тяжёлая операция деления [] в данном случае не является затратной, ибо целочисленное деление на 2 это сдвиг на один разряд. Относительные затраты на операцию деления и присваивания ([=], второе слагаемое) с ростом K быстро стремятся к нулю.

Всего точек:



Средние затраты:



Для первых значений K проведём расчёты по этим формулам и заполним таблицу:



Здесь доля интервала относительный шаг между точками в конце цикла по n.
Последняя строка (среднее) показывает относительные затраты на точку долю сложений/вычитаний. Предел стремится к 0,5625 или ~1/1,7(7) операции сложения.

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

Прошу помощи в распространении и внедрении как в программном, так и аппаратном исполнении.
Источник: habr.com
К списку статей
Опубликовано: 13.11.2020 18:10:19
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Анализ и проектирование систем

Проектирование и рефакторинг

Математика

Параллельное программирование

Промышленное программирование

Оптимизация

Оптимизация программ

Алгоритмы

Минимизация затрат

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru