Математика нужна программистам, или задача, которую мне пришлось решать

    Всем привет!

    Я работаю над WebRTC - фреймворком для аудио-видео конференций (или звонков? проще говоря - real time communication). В этой статье я хочу описать интересную задачу и как она была решена. В задаче, по сути, потребовалось минимизировать lcm нескольких вещественных чисел с дополнительными ограничениями. Пришлось применить совсем чуть чуть теории чисел или хотя бы логики.

    Если вам интересна только задача - то можете смело проматывать до секции "Формулировка задачи". Следующая секция объясняет откуда она такая взялась и в чем ее смысл.

    Введение

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

    Но нельзя просто задать желаемые разрешения, нет - это было бы слишком просто. Дело в том, что источник (например, камера в хроме) может выдавать видео какого угодно разрешения. А еще есть механизм обратной связи и при высокой нагрузке на CPU входящее разрешение снижается. Короче говоря, пользователь задает коэффициенты масштабированияS_i \ge 1.0. Потом входящий кадр сжимается в заданное количество раз, кодируется и отправляется по сети получателям.

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

    Самый эффективный способ этого добиться, это требовать от источника, чтобы разрешение делилось на некоторое заданное число: alignment. Например, для стандартных коэффициентов {1.0, 2.0, 4.0} и требования четности для энкодера, можно легко попросить у источникаalignment=8. Источник чуть-чуть обрежет изображения. Это приведет к незначительному искажению соотношения сторон у видео, зато сделает переключение между потоками незаметным. В итоге, входящее разрешение, кратное 8 можно спокойно делить в 1, 2 или 4 раза и получать четное разрешение, которое енкодер с радостью закодирует.

    Но что делать, если заданы коэффициенты {1, 1.7, 2.3}? Минимальное целое, "делящееся" нацело на все эти коэффициенты - 391. А чтобы результат был четным, нужно вообще взять 782. Согласитесь, это весьма нагло требовать от источника выдавать разрешение, делящееся на 782. Это значит, что даже VGA (640x480) видео уже не послать вообще никак. На практике - максимально допустимое выравнивание, которое мы можем попросить должно быть ограничено, чтобы, во-первых, допускать маленькие разрешения и, во-вторых, не очень сильно искажать соотношение сторон.

    Но, раз уж мы уже немного искажаем настройки пользователя, округляя входящее разрешение, то почему бы и не округлить чуть чуть коэффициенты масштабирования? Например, можно было бы взять коэффициенты {1, 1.6, 2.4} вместо {1, 1.7, 2.3} и получить необходимую делимость в 48 (сильно лучше 782). Если еще больше поменять коэффициенты, то можно получить и меньшее выравнивание.

    Формулировка задачи

    Дано: d \in \mathbb{N},\ S_i \ge 1, S_i \in \mathbb{R}, i=1..n

    Найти: A \in \mathbb{N},\ A \le MaxA,\ S'_i \in \mathbb{R} ,\ S'_i \ge 1,\ i=1..n

    При условии:

    \sum_{i=1}^n\left(S_i -S'_i\right)^2 \rightarrow min\frac{A}{S'_i \cdot d} \in \mathbb{N}, i=1..n \ \ \ \ \ \ \ \ \  (1)

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

    Решение

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

    Следующее наблюдение - можно оптимизировать все коэффициенты масштабирования независимо друг от друга, соблюдая условие (1), ведь в целевую функцию они входят отдельными слагаемыми. Далее сфокусируемся на i-ом коэффициенте.

    Поскольку в условии A/(S'_i \cdot d), A, d \in \mathbb{N}, то получается, что S'_i \in \mathbb{Q}илиS'_i = N_i/D_i. Потому что только рациональные числа можно домножить и поделить на целое и получить в итоге целое.

    Можно потребовать, чтобы дробь была неприводимая: GCD(N_i, D_i) = 1

    Подставим дробь в (1) и получим \frac{A \cdot D_i}{N_i \cdot d} \in \mathbb{N}откуда следует, что

    N_i \cdot d \vert A \cdot D_i  \ \ \ \ \ \ \ (2)

    (запись означает: левая часть делит правую).

    Тут немного теории чисел или просто логики. N_iвзаимно просто сD_i по условию, но делит правую часть. Значит N_iцеликом содержится в оставшемся множителе или N_i \vert A, отсюда можно записать

    A=N_i \cdot f,\ f \in \mathbb{N} \ \ \ \ \ \ (3)

    Далее, домножим обе части уравнения (2) на f:

    f \cdot N_i \cdot d \vert f\cdot  A \cdot D_i

    Подставим выражение (3) для Aвыше:

    A \cdot d \vert f \cdot A \cdot D_i

    сократим A

    d \vert f \cdot D_i

    Раз левая часть делит правую, то можно переписать уравнение так:

    f \cdot D_i = k \cdot d, k \in \mathbb{N} \ \ \ \ \ \ \ \ \ \ (4)

    Теперь вспомним выражение для S'_iв виде дроби и домножим числитель и знаменатель на f и применим (3) и (4):

    S'_i = \frac{N_i\cdot f}{ D_i \cdot f} = \frac{A}{f \cdot D_i} = \frac{A}{k \cdot d},\ \  k \in \mathbb{N} \ \ \ \ \ \ \ \ (5)

    Добавив к этому условие, что коэффициенты S'_iне могут быть меньше 1 (ведь растягивать изображения смысла вообще нет) мы получим:

    k \le \frac{A}{d}   \ \ \ \ \ \ \     (6)

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

    А можно и не перебирать. Ведь целевая функция, если рассматривать непрерывнуюk  выпуклая и имеет минимум, равный 0, в точке k^*=\frac{A}{S_i \cdot d}  . Значит, достаточно рассмотреть 2 ближайших целых значения k=min\{\lfloor k^* \rfloor ,\ \lceil k^* \rceil\}   . Все, что левее левой точки - хуже ее, ведь она сама левее минимума выпуклой функции. Аналогично и с правой точкой. Еще надо аккуратно проверить, что эти точки положительные и удовлетворяют (6).

    Итого, получаем такое решение (тут для простоты нет проверок входных данных):

    const int kMaxAlignment = 16;
    
    // Находит лучшее приближение scale_factor (S_i) при заданном 
    // выравнивании энкодера (d) и результирующем выравнивании источника (A).
    // Ошибка приближения прибавляется к error_acc.
    float GetApprox(int encoder_alignment, int requested_alignment, 
                    float scale_factor, float *error_acc) {
      int k = static_cast<int> ((requested_alignment + 0.0) / 
                                (encoder_alignment * scale_factor));
      float best_error = 1e90;
      float best_approx = 1.0;
      for (int i = 0; i < 2; i++, k++) {
        if (k == 0 || k * encoder_alignment > requested_alignment) continue;
        float approx = (requested_alignment +0.0) / (k * encoder_alignment);
        float error = (approx - scale_factor) * (approx - scale_factor);
        if (error < best_error) {
          best_error = error;
          best_approx = approx;
        }
      }
      *error_acc += best_error;
      return best_approx;
    }
    
    // Решает задачу. Возвращает измененные коэффициенты (S'_i)
    // и результирующее выравнивание (A) в параметре requested_alignment.
    std::vector<float> CalulateAlignmentAndScaleFactors(
        int encoder_alignment, std::vector<float> scale_factors, 
        int *requested_alignment) {
      float best_error = 1e90;
      int best_alignment = 1;
      std::vector<float> best_factors;
      std::vector<float> cur_factors;
      
      for (int a = 1; a <= kMaxAlignment; ++a) {
        float cur_error = 0;
        cur_factors.clear();
        for (float factor: scale_factors) {
          float approx = GetApprox(encoder_alignment, a, factor, &cur_error);
          cur_factors.push_back(approx);
        }
        if (cur_error < best_error) {
          best_error = cur_error;
          best_factors = cur_factors;
          best_alignment = a;
        }
      }
      *requested_alignment = best_alignment;
      return best_factors;
    }

    Заключение

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

    Да, без математики еще можно убедить себя, что выданные этим кодом коэффициенты будут подходить под условие задачи (числитель делит вычисленное выравнивание, поэтому все поделиться нацело, а знаменатель дает делимость на необходимое выравнивание для энкодера). Но без цепочки рассуждений (1) => (4),(5) вообще неясно, как этот код находит оптимальное решение.

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 87

      +17

      Круто, намного интереснее читать чем обзор очередного фреймворка для создания формочек.

        +2
        Я работаю над WebRTC — фреймворком для аудио-видео конференций (или звонков? проще говоря — real time communication).

        Создается впечатление, что фреймворк над которым вы работаете называется WebRTC. Но ведь это же API. Может, чтобы избежать путаницы, назвать как-то по другому?
          +7

          Нет, это еще и фреймворк. Вы его не только в браузере можете использовать но и встроить в ваше приложение. На нем работают аудио/видео звонки в многих мессенджерах, например. А API назвается PeerConnection.

            +1
            Простите, вы член IETF, и то, что вы разрабатываете, станет частью стандарта? Или вы все-таки делаете какое-то свое законченное решение, следующее стандарту WebRTC?
            Если второе, то коллега, по-видимому, имел в виду, что вместо тире в данном случае нужно использовать дефис: «Я работаю надо WebRTC-фреймворком» (т.е. над отдельным фреймворком, использующем WebRTC), а не «Я работаю над WebRTC <. WebRTC это >— фреймворком для аудио-видео конференций».
              +6
              Простите, вы член IETF, и то, что вы разрабатываете, станет частью стандарта?

              Лично я — нет, но коллеги по команде — да.


              Про второе: тут путаница из-за того что web api называется "webrtc" и фреймворк называется точно также. Исторически был сначала этот проект, потом гугл стал его встраивать в браузеры и стандартизовывать к нему АПИ.

                +3
                а не «Я работаю над WebRTC <. WebRTC это >— фреймворком

                Хабр съел часть комментария, я так подозреваю?

            +27

            Лучше рывки при переключении и чёрные полоски вокруг, чем незначительное искажение соотношения сторон. Нужно принять закон о защите соотношения сторон.

              +5
              иногда решения по производительности мешают визуальному восприятию картинки. как пример, запомнилось описание решения, которое было в игре — там было динамическое изменение количества полигонов в кадре, чтобы поддерживать постоянное количество кадров в секунду. В итоге, алгоритм работал так — если скорость кадров падала, уменьшалось количество полигонов в кадре, после этого сложность сцены уменьшалась и скорость росла — количество полигонов увеличивалось, скорость падала из-за сложности сцены — все повторялось снова. В итоге, вместо приятной плавности игры, на экране было постоянное мельтешение из-за изменения количество полигонов.
                +13

                Выглядит как типичная задача ТАУ.

                  +3

                  причем решенная неверно

                    0
                    А какое верное? Я не знаю правильных решений, далек от геймдева — но я бы сделал такой алгоритм: при пресечении порогового фреймрета, происходит автопонижение качества рендеринга. Для повышения обратно пользователь должен менять вручную настройки)
                      +1
                      Очевидно, это не сработает. Фреймрейт не очень стабильная величина, и может ненадолго снизиться по куче разных причин. Может быть что-то ещё запустилось в системе, и вам не хватило ресурсов. Или, бывает, это происходит в начале сцены, пока остальное ещё догружается.
                        +1
                        Вообще, принципиально подход конечно правильный: упала производительность — снижай нагрузку, и наоборот. Только сам этот автоподстраиватель тоже надо настраивать. И насколько я знаю, в современных играх стараются сразу делать сцены такими, чтобы фреймрейт был «хорошим». Потом тестируют и исправляют, так что у пользователей уже никакой автомагии не происходит.
                          +1
                          Только к стабильному фреймрейту этот подход не ведёт.

                          В большей части современных игр просто делают настройки графики и стараются не делать сфер на миллион треугольников. На этом все старания и заканчиваются.
                            0

                            Я правильно вас понял, что пока игру делают, никто не бегает по локациям и не смотрит где тормозит?

                              +1
                              Ага, так и есть. Иногда даже под релиз этого не делают. Афины в assassin's creed odyssey хороший тому пример.
                                +1
                                бегают, обязательно бегают!
                                но у тех, кто бегает — тестовые настройки (а то и вообще — однотонные текстуры), потому бегать уже надо а красивости еще не завезли,
                                у тех у кого должны быть все текстуры и модельки — те их усиленно пилят, чтобы успеть к релизу,
                                а ЛПР (лица, принимающие решения) — бегать некогда, они максимум смотрят на рендеры: «красиво» или «некрасиво»…
                                (семь нянек, классика )
                            0

                            Если максимально упрощенно, то ваше решение более-менее правильное. Как минимум не будет шататься туда-сюда, но (скорее всего) будут проблемы со скоростью адаптации и/или оптимальности подбора условного качества.


                            Если не упрощенно то см "Критерии устойчивости" в wiki-статье (на всякий — там могут быть ошибки, сам не вычитывал).

                              0
                              Скорее менее правильное.

                              Никаких критериев устойчивости в геймдеве никто не использует. Ни в одной игре не видал настройки авто.

                              Есть вполне стандартный метод лодирования, он большинство устраивает. И не нужно в геймдев тянуть ТАУ, и так проблем овер дофига.
                              0
                                0

                                Хм, может какой-нибудь ПИД-регулятор?

                              +3

                              И оттуда же можно позаимствовать рецепт для избавления от мельтешения: гистерезис.

                              +1
                              Это плохой код, фреймрейт в играх так не фиксируется уже лет 30.
                            +10

                            Заголовок слишком громкий и категоричный. Правильнее было бы "Математика нужна программистам, решающим задачу выбора разрешений в WebRTC" :)

                              +8

                              Ну давайте в логику: Обратное утверждение "Математика не нужна программистам" опровергается тем, что я программист и мне нужна математика. А если серьезно, то заголовки должны быть громкими.

                                +8
                                А на ваше обратное утверждение найдется армия формошлепов-CRUD-щиков, которым она не нужна. Мир не бинарный, и что прямое, что обратное утверждение некорректны. А в реальном мире, например, есть ещё выражения «иногда», «в разной степени» или «для определенных задач» :) Точно так же как у научных законов и концепций бывают границы применимости.

                                А что до громких заголовков — этим страдает обычно жёлтая пресса и один вечно ноющий многим известный хабраюзер. Не надо так.
                                  +8
                                  Я скажу честно: увидев раздел «Формулировка задачи», даже не стал читать. Согласен и насчет того, что заголовок слишком провокационный (я как раз только что закрыл статью «как НЕ на надо изучать программирование»), и насчет того, что заголовок должен быть громким. Но раз уж встал вопрос о заголовке, наиболее емко отражающем суть, мое мнение таково, что в данном конкретном случае математика — это чистой воды предметная область, а не общее требование к разработчику. Или, если уж говорить о конкретном заголовке, то он скорее все был бы таким: «Математика может пригодиться программисту».
                                    0

                                    Вот почему математика является предметной областью веб API (приведенная задача происходит задолго до, собственно, сжатия видео и к кодекам имеет весьма отдаленное отношение)? Из-за того, что речь идет о разрешении картинок?

                                      +1
                                      Действительно, а причем здесь вообще веб-API? Я вроде про него ни слова не упомянул :) Да и вы сами, собственно говоря, это затронули. Есть весьма изолированная задача, условия и ограничения для которой пришли извне. В данном случае «из веба», но для самой задачи, а равно как и для того, кто будет ее решать, это не имеет никакого значения. От веба мы абстрагировались. Далее… Задача требует преимущественно математического решения, а значит, если бы мы говорили об идеальном мире и идеальной компании, в которой вы работаете, экспертизу в математике предоставил бы отдельный человек — математик, который, в свою очередь, может ничего не знать о программировании. То есть это все же предметная область, экспертиза в которой необходима для решения определенного круга задач в вашем проекте. И если Ваших познаний в ней оказалось достаточно — это прекрасно. Но все же правильно это сформулировать как то, что математика Вам пригодилась. Но это далеко не «математика нужна программистам». И если, допустим, весь ваш проект или существенная его часть постоянно сопряжены с математикой, как в приведенной задаче, то это, очевидно, задача работодателя нанимать разработчиков, обладающих определенными познаниями в математике, если отдельного математика со своей экспертизой содержать нецелесообразно. Но так же очевидно, что далеко не во всех проектах реального мира требуются эти знания. Равно, как и наоборот: есть множество проектов, где полезны знания в совершенно других областях. Вот только найти программиста, готового предоставить экспертизу, например, по химии, или по любой другой предметной области, не всегда просто, надо полагать. А в данных примерах нет причин считать, что химия отличается от математики как абстрактная предметная область.
                                        +1
                                        Далее… Задача требует преимущественно математического решения, а значит, если бы мы говорили об идеальном мире и идеальной компании, в которой вы работаете, экспертизу в математике предоставил бы отдельный человек

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


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


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

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


                                        Вот вам очевидно, что для этого проекта нужно нанимать специальных математиков? И если еще можно как-то предположить, что раз там ключевое слово "видео" рядом, то всякая обработка сигналов, преобразования Фурье там, свертки, вот это вот все, могли бы пригодится, то каким боком тут теория чисел вылезла?


                                        Это уже когда задача возникла и найдено решение, можно утверждать, что да — в этом проекте математика нужна.


                                        Подчеркну еще раз — у проекта нет какой-то особой "математичности". Математика вылезает в неожиданных местах.


                                        Но это далеко не «математика нужна программистам».

                                        Давайте договоримся, что в заголовке пропущено слово "некоторым" ради авторского стиля и акцента на основной идее?

                                          +1
                                          Собственно говоря, я не столько заголовок уже пытался оспорить, сколько то, что математика — это все же предметная область, или, если эта формулировка смущает, — область знаний, которая пригодилась :) Ну а то, что она может быть нужна некоторым программистам, очевидно :)
                                  +20
                                  «Математика нужна программистам, решающим задачу выбора разрешений в WebRTC»

                                  Это тоже слишком громкий и категоричный заголовок. Правильнее было бы «Математика нужна некоторым программистам, решающим задачу выбора разрешений в WebRTC, некоторым программистам, решающим другие задачи, некоторым людям, не являющимися программистами, и некоторым существам, отличным от людей»

                                  .
                                  Занудствовать начал не я.
                                    +5

                                    Вы пропустили некоторых программистов, не решающих никаких задач

                                      +3

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

                                  –26
                                  Программист должен прогать, т.е. понимать что такое иде, пакеты, ооп, как эффективно разрулить код, как его повторно использовать, знать жылезо и как гоняются байты в нём, всякие кеши и как они эффективно работают. И проблем тут море, на всю жизнь хватит.
                                  В общем и целом прогир из математики должен знать только одно. Всё что есть — это множество. И есть ещё функция отображения множества в другое множество. На этом математика для прогира и оканчивается.

                                  А вот функцию отображения должен предоставить математик. И это вовсе не прихоть. Математик иногда прям таки на несколько «порядков» круче может заваять эту функцию отображения.

                                  Джентельмены, чюдес не бывает. Либо вы годный прогир, либо математик. Быть годным враз пока ни у кого не получалось. Хирург должен резать, продавец продавать, прогир прогать, математик — матемачить.

                                  П.С.: уважаемые прогиры, то что вы там пытаетесь из себя математически извергнуть — это детский лепет для математика, и падавляюще часто — для математика же громкий смех, по причине того, что это всё — древние математические бояны, давным давно придуманные, давным давно успешно устаревшие и никому уже не нужные. И то что на вас навешивают некие проблемы, где вы никак не являетесь профессионалами своего дела — ну это уже ваши проблемы, господа. :)) Если вы на это ведётесь, то сами и виноваты, уж извините…
                                    +4

                                    У вас в команде есть выделенный математик? Вот пришла программисту задача — сделать так, чтобы всем энкодерам приходили кадры с четным разрешением и пользователям "было хорошо". Как понять, что эту задачу надо сначала дать математику?

                                      +10
                                      А собственно почему так категорически нельзя быть годным «прогиром» и математиком одновременно? Так-то понимание предметной области еще ни одному программисту не навредило, а знание «иде, пакетов и ооп» не настолько сакральное, чтоб человеческой жизни не хватило им овладеть на достаточном уровне для решения этой задачи.
                                        –1
                                        А собственно почему так категорически нельзя быть годным «прогиром» и математиком одновременно?
                                        Почему категорически нельзя? Можно. Однако же вероятность этого весьма мала. Если вы стремитесь к малым вероятностям, то вы как минимум «фантазёр». :) И да, т.к. вероятности сего малы, то ни вы ни кто бы то ни было из ближнего и среднего окружения «прогирами и математиками» враз не являются.
                                        Идём далее, предположим что вам повезло, и вы или кто-то из вашего окружения «попал» в эту маленькую вероятность и стал таки математическим программистом. Так и это невозможно. Математик — это прежде всего учёный. Публикующийся. Вот скажите мне, у вас будет время прогать и писать статьи одновременно? А если вы не пишите статьи, то какой же вы к чорту математик? :)
                                        Понимание предметной области — это ничто. Много кто из нас понимает всякое, но быть действительно специалистом сразу многих областях — ни у кого не получается. Чюдес не бывает. И в таком случае вместо мат.прогира вы получите что-то одно и только одно. Либо действительно получите мат.прогира, но сильно остановившегося в развитии.
                                        И да, у меня есть математики. И их много. И я ищу ещё. Это же просто. Идите по универам и скупайте их за еду. Они будут рады. Вы даже не представляете сколько людей действительно занимаются математикой, но не знают где себя применить, хотя бы как-то…
                                        И не ждите чюдес. Математик — это другой взгляд на вашу деятельность, не более. Однако же иногда этот взгляд со стороны действительно приводит к колоссальным решениям.

                                        По поводу фреймворка — ну тут всё очевидно. Расколупайте фреймворк, найдите низкоуровневую часть. В высокоуровневой части прогиры разберутся, это абстракции. А в низкоуровневой не разберутся никогда, это же математика. :) Итого. Распотрошите фреймворк, поймите как он работает, найдите низкоуровневую часть, поймите через математика как она работает, и вставьте нужные вам две строчки. Да да, чюдес не бывает. Всё остальное — это палнейшая фигня, что бы вы не предлагали.

                                        Если вы делаете иначе [а вы делаете иначе] — то это же костыль. Который однозначно снижает производительность. Либо нарушает логику работы фреймворка. Либо что-то ещё. Либо всё враз. :)) И не стоит употреблять фраз типа «а вот мне сказали сделать, или заказали» и хоть убейся но оно должно работать так как заказали. Послушайте, вы не являетесь средством от всех болезней, и не стоит поддаваться чьим то прихотям. И многое вы не можете. А в таком случае не решайте эту задачу. Это не ваша задача. Не стоит уподобляться животному, и искать путей решения чего бы это не стоило.
                                          +3
                                          Математик — это прежде всего учёный.
                                          Есть ученые-математики, есть прикладные математики, больше инженера чем ученые. Очевидно, что разработка математической модели — это прикладная задача, которая требует инженерного подхода, а не научное исследование. Поэтому довольно странно думать, что с ней лучше справится человек, у которого есть научные публикации.
                                            0
                                            Дайте определение прикладного математика, которого вы называете больше инженером, и обычного математика и определите разницу. И почему один может, а другой нет.
                                            На научные публикации рецензентов пол-планеты. Весьма странно думать, что очередной какой нибудь sha лучше сделает математик-инженер [новый термин изобретённый на хабре, крайне редко встречающийся], чем действительно публикующийся профильный математик, которого контр-статьями абстучали тысячи таких же со всего мира.
                                      +4

                                      А я бы по-другому задачу решал. Я бы задал crop area по краям картинки, в которых могут быть пикселы, а могут и не быть (они не выводятся при выводе изображения). Входящий кадр от камеры подрезается по требованиям кодеков, при декодировании ещё раз подрезается (чтобы показать область, которую сумеют все кодеки).

                                        0

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

                                          +4

                                          На входе у нас разрешение 667x401, допустим.


                                          Набор требований:
                                          codec1: кратно 2
                                          codec2: кратно 4
                                          codec3: соотношение сторон — целое число.


                                          codec1, codec2 => x:667->664, y: 401->400.
                                          codec3 => y: 400->332 (альтернативно: x: 400, y:400).


                                          Итого, наш кроп вырезает из картинки 667x401 картинку 664x332.


                                          Считаем границы кропа: x: [2-666] y:[34;366]


                                          Дальше мы либо уже это готовое изображение всем кодекам отдаём, либо отдаём каждому кодеку его картинку (минимальное изменение), а crop делаем на получателе.


                                          Итог — каждый кодек получает картинку, которую хочет, а картинка у получателя привязана к оригинальному пикселу и не двигается. Примерно такой алгоритм используют стабилизаторы видео — какие-то точки не двигаются, хотя границы картинки могут дёргаться.

                                            0
                                            codec3: соотношение сторон — целое число.

                                            Это странное требование, которое я нигде не упоминал. Если codec3 кодирует полное изображение, то можно просить просто, чтобы разрешение было целым (т.е. нет никаких ограничений). Судя по вашему примеру, codec1 кодирует уполовиненное разрешение, а codec2 — четверть.


                                            Ваш кроп по сути и есть то самое "запросить у источника разрешение делящееся на 4". Тогда codec1 делит разрешение в 2 раза, codec2 в 4 раза, codec3 — просто кодирует.


                                            Проблемы встают во весь рост, если соотношение размеров кадров у разных кодеков не такое тривиальное. Например, уже указанные в примере {1, 1.7, 2.3}.

                                              +1
                                              а как насчет паддить по краям черными\белыми пикселями? (я думаю любой самый захудалый кодек одтнотонные пространства будет очень эффективно сжимать)
                                              т.е. посчитать рамку выходного изображения, а на кодеки «посредине» либо ничего не делать (если соотношение уже замечательное) либо добавлять пикселов с той стороны, где это надо?

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

                                                С паддингом кадров та же проблема — до какого размера паддить, что бы после сжатия в 1, 1.7 и 2.3 раз пиксели не съезжали относительно друг друга? Потом, а каким цветом дополнять? В браузерах фон белый, у мобильных клиентов видео занимает весь экран и лучше черный фон. А еще паддить дороже, чем обрезать: Надо обязательно копировать куда-то кадр, когда как обрезание — это сдвиг каких-то указателей и изменение переменной — размера.


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

                                                  0
                                                  подождите, я думал там про соотношение сторон в 1,1.7 и 2.3, а вы сейчас про сжатие.

                                                  Дополнять пикселы — это только для работы кодека, во время показа — рендерить так, чтобы этой «добавки» не было видно (из самого-рассамого простейшего — сделать размер видимой части контрола-контейнера равной видимой части изображения).

                                                  Копировать нужно только то, что является изображением в принципе многие кодеки умеют рендерить кадр где кроме
                                                  1) начала буфера кадра FRAME_START и
                                                  2и3) строк ROWS_N со столбцами COLS_N,
                                                  4) есть еще длина строки ROW_LENGTH (или ROW_PADDING так что ROW_LENGTH = COLS_N + ROW_PADDING, либо указание на выравнивания степени 2 — «до ближайшего числа сверху делящегося на 4 или 8» ит.д.)
                                                  5) и длина буфера кадра FRAME_LENGTH (которая кстати может как и добавлять пустые строки, так и «обрезать» паддинг последней строки.
                                                  У меня был однажды случай что я копировал кадр как массив байт COLS_N*ROWS_LENGTH — т.е. без учета FRAME_LENGTH, а драйвер камеры выделял последовательный участок памяти под буферы для 20 кадров — так что такое копирование первых 19 кадров работало нормально, а 20го — выдавало segfault из-за выхода за границы памяти :DDD ).
                                                  Есть конечно еще разные старинные места, где 4 и 5 нет, но их можно добавить гораздо меньшей кровью чем обработка изображений.

                                                  Смысл этого паддинга не в том, чтобы что-то копировать, а наоборот — чтобы из одного кодека можно было взять например в буфер в памяти кадр 432 на 432 пиксел (пусть это будет RGBA) с паддингом 192 байта, а в другой кодек из этого же буфера передать кадр 480 х 480 пиксел с паддингом 0 байт.
                                        0
                                        А не совсем понял, зачем нагружать канал и слать несколько потоков от источника? Не проще делать это на сервере? Просто на слабых пк или телефонах, это вызовет неплохую нагрузку.
                                          +1

                                          Серверов не напасешься. Перекодирование — довольно дорогая операция, и делать ее для всех клиентов — мало кто может.

                                          +5

                                          Что вы хотите. Сейчас полно программистов, которые ничего не слышали даже о теории алгоритмов. И ни на что кроме формошлепства они негодны.

                                            +4

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

                                              +5
                                              А совсем уж фатальные вещи типа недопустимости вложенных циклов с O(n²) без проблем можно объяснить за один вечер даже школьнику.

                                              Не делите мир на черное и белое. Задачи бывают разные и вложенные циклы для определенных задач являются вполне допустимым решением.
                                            +2
                                            Например, для стандартных коэффициентов {1.0, 2.0, 4.0}
                                            Но что делать, если заданы коэффициенты {1, 1.7, 2.3}?

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

                                              Ну, может в вашем приложении вы видите говорящего человека на весь экран, а сбоку присобачены аватарки остальных участников, которые в 10 раз меньше — тогда вам могут понадобиться коэффициенты {1, 10}. А еще, вдруг у вас смартфон, который снимает в 320x240 и посылает по 3g. Делить его в 2 и в 4 раза слишком пиксельно. Кроме того, некоторые аппаратные кодеки тупо не поддерживают такое низкое разрешение. Поэтому вам могут понадобится коэффициенты {1, 1.5}.


                                              Раз какая-то гибкость в API нужна, то есть и коэффициенты. Никаких причин прибить стандартные {1, 2, 4} гвоздями к документации нет. А дальше уже, черт его знает, что кому в голову взбредет.

                                              +5
                                              Но ведь никто не говорит, что математика не нужна в драйверах и кодеках. Говорят, что не нужна в CRUD/ETL-кодинге. Которого в 100500 раз больше, чем драйверов. Вот щас работаю на проекте. Математики и имиж процессинга строк где-то 200к. Пишут 10 человек. Оставшиеся 100 пишут 2кк строк бизнес-логики и нон-фанкшионал реквармента. А матан спрашивают у всех на собеседовании.
                                                0
                                                Но ведь никто не говорит, что математика не нужна в драйверах и кодеках.

                                                Эта задача вообще не о кодеках. Она о масштабировании изображений. И до драйверов тут как до луны. Этот код из недр реализации API — тупо переводит пользовательские данные в формат, понятный следующему уровню абстракции.

                                                  +6
                                                  Да и не только в классических CRUD/ETL, а еще очень много где.
                                                  Когда я будучи «молодым специалистом» сразу после университета пошел работать в компанию, занимающуюся промышленной автоматикой и всякими измерениями, то думал, вот наверное математики вагон и маленькая тележка будет… Ага, щас. Мы делали как средний (контроллерный) уровень — штучные и серийные установки для замеров нефти и газа на нефтяных кустах, удаленного управления задвижками на трубопроводах, контроля скважинных насосов и насосных станций, управления блоками дозирования реагента, охранно-пожарные сигнализации, и т.д. и т.п, на базе ПЛК и полностью своих изделий, так и верхний (серверный) уровень для диспетчеров и технологов, чтобы они могли контроллировать весь нефтепромысел в реальном времени, анализировать архивные данные, и т.д. Интеграция с десятками разных сторонних приборов, передача данных по радиоканалу, и подобное. Было много реверс-инжиниринга коммуникационных протоколов, обход ограничений железа (когда сторонняя железка каких-то сумрачных гениев требует обязательно два стоп-бита на последовательном интерфейсе, а UART твоего контроллера в такое не умеет в принципе), оптимизация радиообмена, разработка фреймворка для визуализации, и много другого интересного. А математику вспоминать не пришлось вообще, вся обработка измерений и данных с датчиков сводилась к элементарным переводам единиц измерения, нахождению средних значений, простых пропорций (масштабирование сигналов), и прочей фигни выполняемой в одно-два действия. Расчет обводненности — ничего изобретать не надо, формулы выведены разными там институтами и утверждены, самодеятельностью заниматься нельзя, да и операции там на уровне 8-го класса школы. Алгоритмы управления вовсе не хитрые, вида «если то, то то, а если то, то это и это». По некоторым параметрам система весьма неслабо так опережала ближайших конкурентов, заказчики в целом были очень довольны. Проработал там почти 6 лет от джуниора до ведущего инженера, потом переехал в другой город, и начал работать в команде, разрабатывающей систему развертывания, контроля и мониторинга для сетевого оборудования и некоторых специализированных железок (типа гибрида Ansible и Zabbix/Nagios, но со своей спецификой)… и там математики оказалось еще меньше. Потом сменил работу, стал в одной большой и всем известной компании разрабатывать браузер и среду исполнения веб-приложений для смарт-телевизоров (иногда контрибьютя в апстрим Chromium)… ну, вы наверное догадаетесь, что я скажу дальше :)
                                                  прям напоминает бородатый анекдот
                                                  Один еврей долго не женился и вся родня ему говорила жениться и завести детей, мол, а то перед смертью будет даже некому подать стакан воды. Вот он женился, нарожал много детей и, дожив до глубокой старости, умирает. Лежит на смертном одре, вокруг него собралась многочисленная его семья, обвёл он их всех взглядом и говорит: «Б… ть, а пить то совсем не хочется!».
                                                  Не, я прекрасно понимаю, что возможно сделав чуть шаг влево или чуть шаг вправо я бы погрузился в задачи требующие суровую математику по самые уши. Но как показывает практика, интересных задач, где никакого матана не нужно, на нашем веку на всех хватит, да и для наших потомков тоже.
                                                  0
                                                  А здесь точно не случай «математику нужно программирование»?
                                                    +1

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

                                                      +2

                                                      С моей позиции тимлида могу сказать, что я бы выдал что-то вроде "решение точно должно быть, но не в моей компетенции", и задача ушла бы на аутсорс студенту-выпускнику какого-нибудь матфака. А уже продукт его "компетенции" ушёл ко мне на реализацию.

                                                    +1
                                                    Клиенты могут настроить WebRTC кодировать входящий поток сразу в нескольких разрешениях. Например, это может быть полезно в видео конференциях: каждый клиент посылает на сервер несколько потоков с разным разрешением и битрейтом, а сервер пересылает всем остальным только тот поток, который помещается в пропускную способность до клиента.

                                                    Толстые клиенты (особенно записывающий) и тонкий сервер?
                                                    Это же ошибка в архитектуре системы.
                                                    Обычно пишущий посылает наилучшее возможное качество на сервер, сервер преобразует во что надо, в т.ч одним нужно mpeg, вторые могут показать VP9, третьи и AV1 тянут. И сервер можно убыстрить аппаратными ускорителями хоть на ПЛИС.
                                                    В вашем случае
                                                    1. Пишущий клиент будет неэффективно использовать ПСП, передавая много копий некачественного потока.
                                                    2. Снижается показатель использования установленной мощности.
                                                      +3

                                                      Когда-то давно так и делали. И пользоваться системами конференц-связи было невозможно. Были дикие задержки. Когда кто-то представил систему с симулкастом — это была революция.


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


                                                      1) Что делать, если у вас сотни тысяч активных клиентов? Сколько и каких серверов вам надо для декодирования сотен тысяч HD потоков? Это очень дорого, даже с ПЛИС, даже новейшими технологиями. Мне неизвестен ни один большой сервис видео конференций, который бы так делал.


                                                      2) Перекодирование увеличивает задержку. Особенно этим страдают аппаратные ускорители декодирования. У них большая пропускная способность, но задержки ужасны.


                                                      Симулкаст — не идеальное решение, но альтернативы тоже не без недостатков.

                                                        0

                                                        Не супер идея для групповой видеосвязи. Для каждого из N участников серверу придётся готовить N-1 потоков, в худшем случае в разных разрешениях и форматах. Горячо. А клиентское железо, в т.ч. такое, которое умеет аппаратно кодировать, будет простаивать.


                                                        Мне видится более рациональным идея снимать и гнать на сервер действительно максимально качественный поток, другим участникам раздавать его же — а ресайзить уже на получателе. Хоть в шестиугольное окно.


                                                        С третьей стороны, так получателя не переключить на более низкое качество в случае просадки сети, тоже не супер.

                                                          0
                                                          Мне видится более рациональным идея снимать и гнать на сервер действительно максимально качественный поток, другим участникам раздавать его же — а ресайзить уже на получателе. Хоть в шестиугольное окно.

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


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

                                                        0
                                                        То что математика нужна программистам — это однозначно.
                                                        я уже показывал habr.com/ru/post/436966/#comment_19641126 свою поделку.
                                                        пришлось вспоминать курс тригонометрии, и прочих сопутствующих наук из школы.
                                                        ещё раньше пришлось поднимать знания уже из института, когда потребовалось управлять ТЭНами использую ПИД-алгоритм… интегралы, дифференциалы…
                                                          0
                                                          Началь читать и сразу же завис «каждый клиент посылает на сервер несколько потоков с разным разрешением и битрейтом».
                                                          Одного потока с самым высоким качеством будет недостаточно?
                                                            0

                                                            Читайте дальше:


                                                            а сервер пересылает всем остальным только тот поток, который помещается в пропускную способность до клиента.

                                                            Иначе, что делать, когда у вас в конференции 3 человека с 10мб/c соединениями и один несчастный с 300кб/c? Все смотрят на большие красивые пиксели в 300кб/с? Потом, а если у вас в конференции 11 человек — каждый будет получать 10 HD потоков? Это слишком жирно, что для сети, что для процессора получающего.


                                                            Варианты с перекодированием на сервере обсуждаются в этой ветке, если интересно.

                                                            0

                                                            Я уже 20 лет в embedded разработке. Занимался и мелкими микроконтроллерами и системами с Linux внутри. Успел поработать и с мультимедиа и с электромобилями и датацентрами. Математика выше школьной никогда не нужна была. Собственно так же как и алгоритмы сложнее сортировок. Но у меня на интервью это все ниразу и не спрашивали.

                                                              0
                                                              Может я что-то не понимаю, но в математической части в переходе от:
                                                              A/(S_i' d) \in N
                                                              к выражению
                                                              S_i' = A / (N d) > 1
                                                              нет никакой математики…
                                                                +2

                                                                В практических задачах — вот если понадобится мне последовательность простых чисел (например, для хэш-таблицы) — я просто нагуглю её, отфильтрую нужные числа и положу в табличку. Пусть там будет целых 10, или даже 1000 чисел! Оно будет компактно и просто работать. Хотя да, можно было бы написать мини-тулзу, которая всё посчитает (наверное, банальным сделанным на коленке решетом Эратосфена по битовой маске). Основная мысль простая — будучи однажды посчитанным, там больше ничего не поменяется. Так зачем тратить на это рантайм?
                                                                И такое встречается достаточно часто. Начинаешь мудрить с математикой для неких абстрактных X и Y, выводишь формулы, кодишь алгоритм… А на практике оказывается что реальных значений того и другого, всего, скажем, по 10 вариантов. И внезапно получается, что вместо математики с формулами достаточно закодить табличку 10х10 + элементарный аксессор к ней. И это зачастую мало того, что реально занимает меньше места (сколько байт программного кода нагенерит компилятор по сравнению с местом, занимаемым готовой табличкой), так и ещё и работает быстрее (если табличка легко влезает в кэш), и код из двух строчек гораздо понятнее, чем какие-то формулы.
                                                                Остаётся только референсный "математический" код положить рядом в комментарии (на случай, если табличку надо будет поменять/дополнить) и… собственно всё!

                                                                  0
                                                                  Так таблицы синусов и косинусов в программы закладывали, когда не было 8087 на борту
                                                                    0

                                                                    Код все же лучше таблички. Но бывает, когда это "Гуд энаф" чтобы решить поставленную задачу.

                                                                      0

                                                                      Да вот не всегда. Обычно исходит из конкретных целей.
                                                                      Например, escape для json.


                                                                      Если хочется краткости — strchr по строчке из спец. символов. Этакий хакерский "однострочник". Но — читаемость — нулевая; скорость тоже так себе.


                                                                      Если нужно для наглядности — switch на пять спец. символов + дефолтный кейс. Всё стройно, прямо, понятно. Воспринимается одним взглядом, скорость тоже стабильна.


                                                                      Если нужно для скорости — lookup-table на 128 символов. Выглядит не так наглядно (поэтому перед табличкой можно комментарием вариант со свичем приложить), зато время работы за счёт умещения всей таблички в кэш-линии становится практически неизмеримым.


                                                                      И вот дальше уже цели. Если мне нужно прочитать/записать конфиг в жсоне однажды при старте/завершении сервиса — свитч. А если сам сервис гоняет туда-сюда жсоны гигабитными потоками — табличка. А если надо демку, типа полноценный сервис, исходники которого помещаются на бумажке размером с кредитку — strchr.

                                                                        0

                                                                        С примером жсона — я просто возьму либу санитайзер, на крайняк сниппет из интернета, и вставлю его прям со ссылкой на то откуда я его взял. Так что от задачи сильно зависит. Такие типовые вещи решаются элементарно, или библиотекой или просто гуглом. Задача как у автора — уже сложнее, и либы может не оказаться. Тогда подобные рассуждения очень полезны.


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

                                                                          0
                                                                          Алгоритм работает ровно до момента переноса кода на другие системы. Тут опять же по силам и развитию нужно выбирать. Таблицу всегда можно забрать с сервера, а вот код — опасно.
                                                                          Много раз встречал восьмибитные системы с расчетами плавающей запятой без float, только спец таблицы, например перевод в двоичный вид и сдвиг влево до ухода запятой, после сокращения по простой и неочевидной математике. Если программист умеет в матан, то он молодец, но за мою жизнь было очень мало проектов, где он требуется, ну либо (как выше написали) пишешь сетевую функцию на табличных данных и отдаешь на аутсорс математику на вывод формулы.
                                                                          Да и основной кодек 264 имеет свои ограничения, плюс если брать мобилку, то часто есть 4 хардварных потока на декодинг и 1 поток на кодинг видео, остальное будет нагружать процессор. Да и джиттеры и задержки в 2-5 секунд никто не отменял при любом подходе. Пока только одноклассники описывали как переписать TCP стек (или сделать эмуляцию), чтобы решить вопрос с размером фрейма TCP и слипанием пакетов. Но автор с этим не столкнется, так как генерит довольно большой поток данных.
                                                                            +1

                                                                            Ну это уже странные люди пишут странные аглоритмы.


                                                                            Мои знакомые которые пишут пишут исключительно переносимый код. size_t/int32_t, и прочие бест практисы которые способствуют возможности бездумного переписывания на любую мыслимую платформу.

                                                                              +2
                                                                              ну попробуйте как нибудь перенести float на 8-битную платформу, где у тебя меньше мегабайта памяти на всё :)
                                                                                0
                                                                                увы, встроенные платформы еще не везде умеют в 32 бита (забацал я недавно небольшое уравнение второй степени, где и вход и выход были до 1000. А вот квадрат переполнился за int16 :( — и вопрос от тестера «а почему это железяка до ~600 работает, а потом скачет??? хмм...» )
                                                                      0
                                                                      Уииии… А сколько таких эпизодов было в карьере?
                                                                        0
                                                                        И в самом деле, зачем математика нужна программистам, если они не понимают ее и не умеют ее применять?

                                                                        Знаете, откуда взялся метод наименьших квадратов и какие задачи он решает?
                                                                        А он позволяет отделить полезный сигнал или систематический результат измерений от помех или ошибок измерений. НО…

                                                                        1. Отклонения в сигнале или измерениях должны быть именно случайными ошибками/помехами.
                                                                        2. Они должны быть вызваны большим числом неучтенных факторов и иметь, вследствие этого, нормальный закон распределения.

                                                                        Т.е. решают такую задачу: Подбирают такие параметры процесса, при котором отклонения имеют нормальный закон распределения. После чего говорят: «Смотрите! Отклонения распределены нормально. Следовательно, они — случайные ошибки измерений или случайные помехи. А параметры описывают реальный, лишенный ошибок процесс!»

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

                                                                        А раз так, так следует искать другие критерии оптимизации. Например, минимизация максимального отклонения AR. Или минимизация суммы абсолютных значений их отклонений.
                                                                          +1

                                                                          Но это не метод наименьших квадратов. Это минимизация метрики L2. Можно спорить, какая метрика лучше — L2 или L_infinity. Квадраты лучше минимизации суммы абсолютных значений тем, что чувствительнее к отдельным большим значениям. Брать просто максимум всех значений тоже можно, но тогда невозможно отличить 2 решения, где максимум одинаковый, но в одном больше нулей.

                                                                            0
                                                                            Но это не метод наименьших квадратов.

                                                                            Значит, я не так понял это:

                                                                            При условии:

                                                                            \sum_{i=1}^n\left(S_i -S'_i\right)^2 \rightarrow min

                                                                            Прошу прощения — в комментах TeX не работает.
                                                                              0
                                                                              Брать просто максимум всех значений тоже можно, но тогда невозможно отличить 2 решения, где максимум одинаковый, но в одном больше нулей.

                                                                              А такое возможно? Тогда исключаем найденный минимизированный максимум и повторяем оптимизацию для оставшегося набора.
                                                                                +1

                                                                                Можно и так. А можно просто поменять целевую функцию, как нам хочется.

                                                                              0
                                                                              Про хорошесть МНК — это прогон для студентов. МНК удобен для расчётов на бумаге. Другие методы, доступные аналитически, сильно плохи и их не упоминают.
                                                                                0
                                                                                Дело в том, что МНК имеет строго ограниченную применяемость. Его можно использовать в том случае, если нужно отделить сигнал от шума или измеряемую величину от погрешностей измерений. В любом случае погрешность/шум должны быть случайной величиной с нормальным распределением. Если это не так, то применение МНК является некорректным. Если повезет, то хуже не будет. Иначе надо искать более удачные и обоснованные критерии.
                                                                                  0
                                                                                  Это у вас книжные знания, действительность намного богаче.
                                                                                  Строгая ограниченная применяемость нужна для приёма-сдачи экзаменов, на деле бывает всякое. Отделить измеряемую величину от случайной погрешностей измерений вообще невозможно. Ну и т.д.

                                                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                            Самое читаемое