Модульное тестирование, наука и математика


    Предисловие


    Модульное тестирование (unit testing) применяется повсеместно. Кажется, уже никто без него не обходится, все пишут тесты, а их отсутствие в сколь-нибудь серьёзном проекте вызывает, как минимум, непонимание. Однако, многие воспринимают тестирование как некий ритуал, совершаемый для того, чтобы не разгневать "бога программирования". Мол, так надо. Почему? Потому что.


    Буду говорить страшные вещи.


    Не важно, что брать за единицу тестирования. Не важно, как сгруппированы тесты. Не важно, пишутся ли они до кода или после. TDD или не TDD? Всё равно. Доля покрытия? Наплевать. В конце концов, тестов может совсем не быть. Всё это совершенно не важно. Важно, чтобы выполнялись требования, предъявляемые к ПО.


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


    Постойте, причём же тут наука с математикой?


    Содержание



    1. Гарантии и вероятности
    2. Программирование как построение теории
    3. Тестирование как доказательство теорем
    4. Что важно, а что нет
    5. Нужно ли тестировать тесты


    Гарантии и вероятности


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


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


    Но фундамент фунтаментом, а любые тесты — вероятностная история. Тесты — это не про гарантии. Тесты — это про вероятность. Чем больше тестов, чем они лучше и качественнее и чем более они автоматизированы, тем больше вероятность, что в программа работает так, как от неё требуется.


    Тест никогда не доказывает отсутствие ошибок и правильность работы программы. Он может доказать только наличие ошибки. Это любопытная особенность нашей работы: мы, программисты, никогда не можем быть уверены на 100%, что наша программа работает правильно.


    Но мы можем повышать вероятность.



    Программирование как построение теории


    Представим на секунду написание программ как своеобразную "науку". Допустим, тесты написаны, в них нет ошибок, и они полностью покрывают все требования, наложенные на нашу программу. Тогда эти тесты можно рассматривать как объективную реальность, окружающий мир, который мы будем моделировать с помощью нашей программы. Будем выдвигать "гипотезы" и проверять их "эксперементально". То есть будем писать код и смотреть, проходит ли он тесты. Если не проходит, значит, наша "гипотеза" была неверна, и её нужно либо отвергнуть, либо уточнить. Таким образом напишем программу, и если она хорошо моделирует "реальность", то есть проходит все тесты, то считаем, что программа готова.


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


    Так и есть, и поэтому перехожу к другой, более важной метафоре.



    Тестирование как доказательство теорем


    Метафора проста. Мы будем представлять каждый тест как "теорему", которую нужно "доказать". Каждая такая "теорема" базируется на других "теоремах" и "аксиомах".


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


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


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


    Рассмотрим пример. Допустим, мы разработали класс std::vector, и хотим протестировать метод clear. Вернее, хотим "доказать", что он работает правильно.

    Что вообще он делает? Полностью очищает контейнер, не изменяя при этом его вместимости (capacity). Значит, на этом уровне мы можем сформулировать сразу несколько "теорем":
    1. После вызова метода clear() размер контейнера равен нулю, то есть метод size() возвращает ноль;
    2. После вызова метода clear() контейнер пуст, то есть метод empty() возвращает true;
    3. После вызова метода clear() вместимость контейнера не меняется, то есть метод capacity() возвращает то же значение, что и до вызова метода clear().
    4. Вызов метода clear() приводит к тому, что у всех элементов, которые находились в контейнере, вызывается деструктор.


    Попробуем "доказать" первую из "теорем":
    test_case("После вызова метода `clear()` размер контейнера равен нулю")
    {
        std::vector<int> v{1, 2, 3, 4};
    
        v.clear();
    
        check(v.size() == 0);
    }


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

    Мы создали контейнер, затем очистили его и проверили, что размер равен нулю. Однако создание контейнера и взятие его размера — это тоже работа с нашей программой, то есть не "аксиомы". Получается, что в доказательстве нашей "теоремы" мы пользуемся другими "теоремами" о корректном конструировании вектора, а также о корректной работе метода size(). И их мы тоже должны "доказать".

    Допустим, мы "доказали", что контейнер создаётся правильно с помощью конкретного конструктора std::vector<int> v{1, 2, 3, 4}. Но у вектора есть много разных конструкторов. И что, для каждого из них "доказывать", что размер именно так сконструированного вектора равен нулю после очистки? Это было бы слишком расточительно, поскольку методов у вектора много, и пришлось бы каждый из них тестировать для каждого конструктора. А если вдруг появится новый конструктор? Придётся дублировать для него каждый такой тест, ничего не пропустить, и не ошибиться при копипасте (а она будет, мы же ленивые).

    Вместо этого лучше "доказать" эквивалентность разных способов конструирования вектора, и тогда не нужно никакого дублирования, кроме одного: нужно "доказать", что вектор, в котором изначально не было ни одного элемента, после очистки также остаётся пустым. Допустим, "доказали".

    Осталось "доказать", что метод size() выдаёт именно размер, то есть текущее количество элементов в контейнере. Но здесь мы поступаем аналогично: отдельный случай для пустого по построению вектора, и отдельный случай для непустого. А эквивалентность конструкторов мы уже "доказали", так что можно брать любой.

    И вот только теперь мы можем считать "доказанной" изначальную "теорему".

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



    Что важно, а что нет


    Если есть такая система утверждений, то не важно, что считать единицей, и как группировать тесты (хотя, действительно, удобно отнести тесты к какой-то конкретной программной сущности — классу или функции — и сложить их в отдельный файл). Важно только то, что "доказаны" все "теоремы". А как они сгруппированы и разбросаны по файлам — наплевать.


    Аналогично, не имеет значения, когда пишутся тесты: до написания кода, или после (хотя использовать методологию TDD тоже бывает удобно). Но что на самом деле важно — это принцип описанной "математичности". Потому что если есть чёткое понимание того, что требуется от программы, и не пропущено ни одной "теоремы", то программа будет одинакова хороша и с TDD, и без.


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


    В общем, важно, чтобы тесты формировали теорию о работоспособности программы, а не проверяли отдельные случаи.



    Нужно ли тестировать тесты


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


    Таким образом наши метафорические "наука", то есть код, и "объективная реальность", то есть тесты, двигаются друг другу навстречу, никогда не достигая идеала, но увеличивая желанную вероятность.

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 58

      +1
      За одно только предисловие сталю плюс! :)
      Давно хочу написать статью на эту, только немного подробнее
        0

        Флаг в руки, коллега.

        +1

        Тесты мне больше напоминают не доказательство теорем, а экспериментальную проверку гипотезы. А TDD — создание хорошей теории по набору экспериментов — минимальной и покрыващей все случаи (ну и разработку дополнительных экспериментов для проверки теории)

          0
          Юнит-тесты — это вообще ни о чем. Ничего не тестируют, ничем не помогают.
          А вот бренч-тесты — незаменимый инструмент отладки — т.е. ускоряют процесс а не замедляют. Да и 100% покрытие того что должно быть покрыто еще при отладке всегда есть. Ну а заодно поощряют писать код компонентов так, чтобы любой компонент после отладки никогда не требовал рефакторинга.
            –1

            Было бы неплохо всё-таки прочитать статью перед комментированием.

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

              Т.е. для того чтобы появился набор теорем, тест должен строится на основании внутренней структуры тестируемого компонента. И именно на этом факте нужно акцентировать внимание. Тогда к примеру и эквивалентность конструкторов доказывается элементарно — фактом независимости набора возможных состояний и функций перехода между ними от того каким именно конструктором сконструирован объект, что при статической типизации свойственно вообще для всех объектов.
              Юнит-тесты же софта по методу «черного ящика» — действительно ни что иное, как экспериментальное гадание на кофейной гуще.
              Аналогично, не имеет значения, когда пишутся тесты: до написания кода, или после (хотя использовать методологию TDD тоже бывает удобно).
              Имеет и огромное. Абстракции имеют свойство наращиваться слоями. А соответственно нет никакого смысла начинать разработку зависимых компонентов/функциональности до того, как слой от которого они зависят, не будет полностью отлажен. К примеру разрабатывать изменение количества элементов вектора бесполезно до того, как будет полностью отлажено изменение емкости буфера, а его в свою очередь бесполезно разрабатывать до того, как будут полностью отлажен смарт-поинтер, который хранит указатель на буфер. А вот для облегчения оной отладки и применяются тесты — в силу того что бренч-тесты завязаны на внутреннюю структуру отлаживаемого компонента, они, в отличии от юнит-тестов, показывают не только работает/не работает, но и что именно не работает, а зачастую и почему именно не работает. При этом стоит добавить что бренч-тесты имеют смысл только при 100% покрытии тестируемой функциональности, и в случае рефакторинга должны перерабатываться. В отличии от юнит-тестов которые вроде бы как должны тестировать неизменность поведения при рефакторинге а не корректность работы.
                0

                Такого лютого треша и угара в моих публикациях, по-моему, ещё не было.
                Жги, чертяка!

                • UFO just landed and posted this here
                    0
                    Потому что выходное состояние будет определяться не только значением на входах, но и внутренним состоянием.
                      0

                      Коих для конечного автомата тоже конечное число.

                      • UFO just landed and posted this here
                          0

                          А внутренние состояния определяются чем?

                            0
                            А внутренние состояния определяются чем?

                            Внутренней структурой
                              +1

                              А не тем какие взаимодействия со внейшней средой были в прошлом?

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

                                  А с чего вы решили что юнит тестирование делается по методу черного ящика?

                                    0
                                    А с чего вы решили что юнит тестирование делается по методу черного ящика?

                                    А потому что иначе тесты должны зависить от реализации компонента и это будет уже что угодно но не юнит-тестирование.
                                      0

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


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

                                        0
                                        Например, если я вижу непокрытую ветку, я могу добавить тест на то внешнее поведение, которое она реализует.

                                        У другой реализации банально другой набор веток. К примеру непрерывный и сегментированный аллокаторы вектора будут работать абсолютно по разному и иметь абсолютно разную внутреннюю структуру. И даже абсолютно разные итераторы.
                                          0

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


                                          Соответственно, эти требования могут быть выражены через тесты.

                        0
                        Любая программа явно или неявно является конечным автоматом.

                        double absolute_difference(double a, double b) {
                            return std::abs(a - b);
                        }

                        Ну и где тут конечный автомат?

                          0
                          Ну и где тут конечный автомат?
                          Результат любого элементарного выражения есть ни что иное как результат побочного эффекта работы конечного автомата. Т.е. любое элементарное выражение это декларативная группировка автоматов. Это еще можно тестировать как черный ящик (во всяком случае пока операторы не перегружены). В чуть более сложной программе (любой где есть ветвление) автомат просматривается уже более явно и там нужно тестировать уже каждую такую элементарную ветку для чего нужно знать внутреннюю структуру.
                      0

                      Эээ как вы определяете юнгит тесты и бранч тесты? Я нашел только определение бранч тестинга, и TDD, как мне кажется, неплохо на него ложится.

                        0
                        Эээ как вы определяете юнгит тесты и бранч тесты?

                        Бренч тесты — тесты тестирующие все внутренние ветки переходов тестируемой функциональности (от слова «бренч» — на буржуйском наречии «ветвление»). Назначение — тестирование функций перехода компонента из одного состояния в другое. Должны покрывать 100% внутренних веток функций перехода, иначе бессмысленны. Назначение — значительное ускорение отладки. По сути позволяют находить причину ошибки методом исключения веток. При изменении реализации тесты требуют соответствующей переработки. Офигенное средство отладки позволяющее при условии правильной архитектуры/постановки добиться того чтобы один раз написанный и отлаженный компонент больше никогда не требовал рефакторинга. Любимая фишка программистов.

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

                        Да очень похоже по назначению. И то и то используется для послойной отладки и тестирования непосредственно при создании кода. Но опять же TDD это юниты не завязанные на внутреннюю структуру. Хотя бы потому что для того чтобы знать внутреннюю структуру функций перехода код этих функций перехода уже должен быть.
                          0
                          Но опять же TDD это юниты не завязанные на внутреннюю структуру. Хотя бы потому что для того чтобы знать внутреннюю структуру функций перехода код этих функций перехода уже должен быть.

                          Не должен — должна быть идея этого кода.

                      0
                      Постойте, причём же тут наука с математикой?

                      К юнит-тестам софта? Вообще ни причем. Это прекрасный инструмент для тестирования аналоговых устройств, не имеющих внутренних состояний. Именно для них он был изобретен и для них он абсолютно научен.
                      Но тестирование с его помощью софта и любых устройств имеющих внутренние состояния — абсолютно бессмысленно с точки зрения все той же математики.
                        0
                        Практика написания тестов таким образом называется property based testing. Распространена в функциональном программировании
                          0
                          Практика написания тестов таким образом называется property based testing

                          Наконец-то комментарий по существу.


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

                            0
                            Генерация и рандомизация — это всего лишь инструменты, которые позволяют покрыть большее количество случаев. Ключевая идея состоит в проверке различных инвариантов.
                          0
                          Тест никогда не доказывает отсутствие ошибок и правильность работы программы.
                          Вспомнился баг. Есть класс, вычисляющий нечто на графе (на подобие раскраски). Где-то в недрах алгоритма в условии вместо nodes[i] проскакивает nodes[0] из за ошибки при вычислении этого i. И итоге все работает правильно почти всегда, исключая не частые случаи, когда некие атрибуты в узле графа nodes[0] отличаются от nodes[i].
                          Всегда было интересно, удается ли обычно покрыть подобные ситуации тестами.
                            0

                            Очевидно, чем сложнее программная сущность, тем сложнее её тестировать.
                            Но если сложное вычисление максимально декомпозировать и свести к известным более простым решениям, каждое из которых само по себе хорошо протестировано, то ситуация улучшается.

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

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

                                  0
                                  Конкретно для этого алгоритма одна только голая логика его работы занимает примерно 13 тысяч строк и создается одним программистом в срок 1-2 года (общая задача — выбор оптимального варианта действий в системе, которая описывается графом). При этом во-первых, разработка ведется итерационно, т.е. в каждый конкретный момент непонятно как все это должно работать в итоге и все переделывается несколько раз. Во-вторых, как водится, алгоритм находится на грани возможностей мозга разработчика а сроки на грани того, что рынок может ждать. В третьих, разработчик является по совместительству специалистом в предметной области и следовательно не является супер-гуру в программировании (если бы дали задачу чистому программисту, то он утонул бы в деталях предметной области).
                                  Получается, что если необходимость тестируемости кода заметно усложнит разработчику задачу, то все, он просто не справиться в установленный срок или не справится вообще.
                                  Поэтому идея обложить подобного монстра и его внутренние модули юнит-тестами, насколько это возможно, довольно привлекательна. Только бог его знает как такие вещи осуществляются на практике и насколько эффективными бывают.
                                    0

                                    Тут я вижу сразу две ошибки, причём не технические, а организационные.


                                    1. В каждый конкретный момент нужно всё-таки знать, что хочется получить. Или, по крайней мере, должна быть генеральная линия;
                                    2. Жадность, попытка сэкономить на ФОТ. Для создания программного продукта нужны программисты, а не только хороший технарь в предметной обасти.

                                    Без решения этих проблем нет смысла приступать к решению проблем кода.

                                      0
                                      В каждый конкретный момент нужно всё-таки знать, что хочется получить.
                                      Так не получается, потому что это новый программный продукт а не типовая задача. В начале изучаем проблему и пишем алгоритм, который находит решения. Потом изучаем эти решения, понимаем что они довольно далеки от жизни и думает слишком долго, переделываем алгоритм, уточняем постановку задачи, и так много итераций. Ведь нельзя же, скажем, спроектировать и запустить ракету в космос с первого раза, если еще не знаешь (и не можешь узнать) ничего ни о ракетах ни о космосе. Всегда нужны огневые испытания и прочее.
                                      Жадность, попытка сэкономить на ФОТ.
                                      Понятное дело. И в конкурентной борьбе победят самые жадные и быстрые. Потом если продукт победит на рынке, хорошие программисты смогут 3 раза переписать это все еще раз поверх. Правда не знаю насколько это типичная ситуация.
                                        –1
                                        Так не получается...

                                        Тогда не надо говорить про "сроки на грани того, что рынок может ждать". Не знаем, что хотим — не знаем, когда получим.


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

                                        Видали, знаем. С такими не по пути.

                                          +1
                                          Для меня это странный подход. Вам приходилось работать в продуктовых компаниях, которые сами находят потребности рынка, создают продукты и затем пытаются их продавать? Там нету кого-то кто может поставить задачи и сроки настолько четко. Но именно там есть интересная работа.
                                          Наверно если бы это был аутсорсный проект и заказчик хотел бы непонятно чего в указанные сроки, меня это бы тоже не устроило, но когда это собственный продукт, тут успех продукта — единственный критерий.
                                            +1
                                            Конкретно для этого алгоритма одна только голая логика его работы занимает примерно 13 тысяч строк и создается одним программистом в срок 1-2 года (общая задача — выбор оптимального варианта действий в системе, которая описывается графом)
                                            Вот это несуразица абсолютная. Поиск в графе и его оптимизация — это профиль именно программиста.
                                            При этом «найти в графе» с 13k строк и 1-2 года, как то очень не стыкуются.
                                            А профиль оного товарища из предметной области циферьки в узлах/на дугах графа намалевать, которые как оценки при поиске пользуются. Причем не самому малевать а опять же формулами расписать принцип их формирования. Т.е. проблема таки в отсутствии декомпозиции. Причем отсутствие декомпозиции кода — это тока следствие отсутствия декомпозиции задачи по профилям специалистов.

                                            13k строк кода на плюсах без декомпозиции скорее призовут диавола чем заработают.
                                            А с нормальной декомпозицией — способны изловить диавола, заставить его перекроить мироздание по желанию программиста, после чего изгнать лукаваго обратно в адские чертоги.
                                              0
                                              То что вы описываете хорошо выглядит теоретически, но я не представляю как это может работать в реальности.
                                              Не работал в геймдеве, но пусть будет пример оттуда. Например, нам нужен навороченный AI для персонажей, который тоже займет десятки тысяч строк. Как он делается? Один человек, специалист по игровому AI рисует расписывает циферками, формулами и алгоритмами, а потом программист не понимающий в этих AI и играх особо пишет программу по этим алгоритмам? Или все это создает по сути один человек, который может отдать другим в лучшем случае писать тесты или вспомогательные модули (т.н. «хирургическая бригада»)? В моем случае это второй вариант. Первый наверно возможен, но потребовал бы двух классных узких специалистов вместо одного среднего универсального и времени у них ушло бы больше.
                                              При этом «найти в графе» с 13k строк и 1-2 года, как то очень не стыкуются.
                                              Да, на самом деле не совсем так. Собственно библиотека которая ставит в соответствие модели из доменных объектов граф и поддерживает его анализ с разного рода кэшированиями имеет размер 3-4 тысячи строк. Остальное это алгоритм выбора решения, работающий поверх этой библиотеки. Здесь есть декомпозиция. Внутри этих основных модулей с ней сложнее. Есть еще абстрактный «искатель решения», абстрактно решающий задачу принятия решения и окружающий код, извлекающий из графа и доменной модели то что нужно этому искателю в процессе поиска решения…
                                                0
                                                специалист по игровому AI рисует расписывает циферками,
                                                Уже абсолютно не стыкуется с тем что он не программист.
                                                а потом программист не понимающий в этих AI и играх особо пишет программу по этим алгоритмам
                                                Та нет. Программист адаптирует модель к машинному счету. Это значит что разбирает все это досканально до последнего винтика. Чем доводит таки этого специалиста до того что в его формулах все начинает стыковаться. Вообще в плане математической подготовки с программистам могут разве что чистые математики соревноваться. И то местами. У программистов эта подготовка гораздо более широкий список разделов и с учетом особенностей адаптации к машинному счету. А с технарями там без вариантов — у них вся вышка как у программистов один из разделов математики.
                                                Остальное это алгоритм выбора решения, работающий поверх этой библиотеки.
                                                От как то эти оставшиеся 9-10k строк кода не стыкуются с поиском на графе от слова абсолютно. Обычно ищется кратчайший путь на графе. И это, так же как и другие алгоритмы на графах, не 10k а дай бог чтобы десятки строк.
                                                Т.е. похоже на то что однозначные оценки в узлах/на дугах не проставлены а значит и поиск ни к чему не приведет. Даже если критерии расстановки этих оценок сложные — ну существуют методы получения четкой цифери из этих сложных критериев.
                                                  0
                                                  А с технарями там без вариантов — у них вся вышка как у программистов один из разделов математики.
                                                  Или наоборот, программирование для специалиста — это один из самых простых разделов математики. Правда это касается задач покруче чем мы обычно решаем.
                                                  От как то эти оставшиеся 9-10k строк кода не стыкуются с поиском на графе от слова абсолютно. Обычно ищется кратчайший путь на графе. И это, так же как и другие алгоритмы на графах, не 10k а дай бог чтобы десятки строк.
                                                  Здесь задача намного сложнее — поиск последовательности действий на графе. Т.е. можно «отключать» или «включать» ребра графа и нужно сделать это в оптимальной последовательности. Можно просто перебирать все возможные последовательности (N!) и вычислять целевую функцию для каждой. Но во-первых, во всем графе десятки тысяч ветвей и нужно локализовать задачу, во вторых в любом случае вариантов слишком много и каждое вычисление целевой функции требует решения множества задач раскраски графа в десятках вариаций. Значит результаты раскраски графа нужно хранить и переиспользовать и кроме того использовать нечто вроде метода ветвей и границ с дополнительным сохранением и переиспользованием уже найденных частных решений. Дальше, некоторые действия можно группировать. Некоторые можно выполнять один раз а некоторые сколько угодно раз. Некоторые последовательности не имеет смысла проверять. Некоторые действия нужно выполнить сразу как только это возможно. Если все это не помогает сократить число вариантов до десятков тысяч, нужно переходить к случайному поиску решения, отказавшись от полного перебора. Все эти факторы сплетаются и нужны дополнительные усилия, чтобы привести их всех в гармонию в коде. Получаем, около 2 тысяч строк алгоритма оптимизации поверх графа и еще несколько тысяч строк кода для поддержки вычисления целевой функции и ограничений. Остальной код решает задачи привязки алгоритма к реальным задачам над доменной моделью.
                                                  Понятно, что как-то это надо обкладывать тестами. Главная проблема, которую я вижу заключается в том, что любые изощренные искусственные сценарии тестирования всегда оказываются проще чем реальные ситуации с которыми сталкиваются алгоритмы.
                                                  Например, можно в юнит-тестах нарисовать несколько случайных простых графов и погонять алгоритмы анализа, графа на них. Но алгоритм не стейт-лесс, он переиспользует результаты. Значит нужно гонять на довольно сложных сценариях. При этом тестовые задачи всегда довольно однородны и представляют типичные ситуации. В реальной жизни все всегда перекошено и ситуации бывают самые неожиданные. Т.е. что бы я не придумал, чтобы сломать алгоритм реальные задачи в большинстве случаев придумывают что-то похуже.
                                                  Следующий слой — алгоритм оптимизации тестировать еще сложнее, потому что запускать его без нижнего слоя, работающего с реальным графом довольно сложная задача и не факт, что показательная в части выявления багов.
                                                  Это я все к тому, что рассуждать о том как протестировать алгоритм на несколько десятков строк другим алгоритмом на десяток строк легко. Интереснее вопрос о том, как тестировать реальные по настоящему сложные алгоритмы.
                              –1
                              Всегда было интересно, удается ли обычно покрыть подобные ситуации тестами.
                              Юнит-тестами по методике тестирования «черного ящика» — разве что случайно.
                              Бренч-тестами с отладкой по слоям абстракции — сначала будет на 100% отлажен, а значит и оттестирован расчет оного i, а потом уже написан слой его использующий.
                              В таких случаях быстродействие очень критично. Декомпозиция может его начисто убить, если речь о декомпозиции алгоритма.

                              Заклинание inline и прочая черная шаблонная магия в таких случаях обычно помогают на овер 100%.
                              0
                              Это любопытная особенность нашей работы: мы, программисты, никогда не можем быть уверены на 100%, что наша программа работает правильно.

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

                                0

                                Ждал этого комментария.
                                К сожалению, нет, потому что это тоже программа, в которой могут быть ошибки.

                                  +2

                                  Ну так и фреймворк для тестирования — тоже код, в котором могут быть ошибки. И в ОС, на котором вы её запускаете, тоже могут быть ошибки. Значит, тесты бесполезны?


                                  Надо как-то договориться о том, чему вы доверяете.

                                    0

                                    Доверяете и 100% — разные вещи.

                                      0

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

                                        0
                                        Иначе определение становится неконструктивным...

                                        Определение чего?


                                        … сложить лапки...

                                        Я где-то это предлагал?

                                          0
                                          Определение чего?

                                          Уверенности. Зачем вам определение уверенности в чём-то, если вы заранее можете сказать, что вы не доверяете X для любого X?


                                          Я где-то это предлагал?

                                          Не, это, наоборот, у меня такое желание иногда возникает, когда задача тем или иным образом демотивирует.

                                            +1

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

                                              0

                                              Супер! Полностью согласен с таким подходом!


                                              Но тогда и получается, что 100%-ая уверенность быть таки может, потому что ваше формальное доказательство проверяет чужая (и на самом деле очень тупая) программа. Она правда очень тупая, тот же quickcheck сложнее будет.

                                                0

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


                                                Но когда мы пишем тесты, мы закрываем на это глаза, потому что иначе, как вы и говорите, не было бы смысла вообще что-то делать.

                                    0
                                    К сожалению, нет, потому что это тоже программа, в которой могут быть ошибки

                                    Возьмем минимальную программу. К примеру int a = 0; Для нее мы можем со 100% вероятностью гарантировать, что если a после ее выполнения окажется не равно 0 то ошибка где то в другом месте, а соответственно этот код на 100% корректен.
                                    Почему вы считаете что методом последовательного исключения такую гарантию нельзя расширить на большие масштабы? Принцип то не меняется, а оные большие масштабы собираются из элементарных фрагментов.
                                    Т.е. соответствие кода постановке задачи доказать можно со 100% гарантией.
                                    Открытым остается вопрос соответствия задаче самой постановки. Но это вопрос уже из более другой песочницы, нежели тестирование.
                                    0

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

                                      0

                                      Оба этих вопроса решаются ровно теми же инструментами для формальных доказательств. Ошибки в доказательствах они найдут, а доказательства никто в явном виде всё равно читать не будет (спросите фанатов tactic-based proving, они эти доказательства в явном виде даже не пишут).

                                        0

                                        Буду благодарен, если подкинете ссылки, с которых можно начать изучать вопрос.

                                          0

                                          Зависит от математического бекграунда и от того, что конкретно вы хотите изучить. Если системы формальных доказательств вообще — можно начать с книг Type-driven development with Idris (это чтобы зависимых типов не бояться) и Type theory and formal proof (это чтобы их метатеорию немножко изучить, pdf'ка sci-hub'ится). Если конкретно тактики — Certified Programming with Dependent Types (есть публичная pdf'ка).

                                  Only users with full accounts can post comments. Log in, please.