Monthly Archives: Январь 2017

Пример функциональной декомпозиции

Задача вроде тех, что решают студенты на нашем экзамене после первого семестра.

«Дана прямоугольная матрица. Найти в ней первую строку, не содержащую нулей, или определить, что таких строк нет.»

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

Решение в стиле C подразумевает прототип функции вроде (матрицу можно оформить по-разному, но предпочтём пока простейший вариант):

float* find_row_without_zero
  (float **a, size_t rows, size_t cols);

— вернуть указатель на соответствующую строку, либо nullptr, если такой нет.

Итак, студент видит слово «матрица», из чего делает вывод, что здесь явно двойной цикл, и пишет что-то такое:

float* find_row_without_zero
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
        // ???
      else
        // ???

Почему-то многим очень хочется поставить else-секцию с возвратом результата. Т.е. ошибочно подменить квантор «все» (не нули) на «существует». Под if в этом случае идёт break. Положим, стало ясно, что else здесь никак не нужен. Что же делать? Типичное неказистое решение имеет следующий вид:

// Bad structured programming (using a flag variable).
float* find_row_without_zero_1
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    bool found = true;
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
      {
        found = false;
        break;
      }
    }

    if (found)
      return a[i];
  }

  return nullptr;
}

В принципе, кто-то может решиться на использование goto, что даёт избавление от лишней переменной. Но это маловероятно: в примерах goto почти не встречается, а в книгах последних десятилетий его использование традиционно порицается.

// I'm not afraid of GOTO!
float* find_row_without_zero_2
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
      if (a[i][j] == 0)
        goto next_row;

    return a[i];
  next_row:;
  }

  return nullptr;
}

На самом деле, данная задача подразумевает применение функциональной декомпозиции (основного метода программирования, кстати). Достаточно понять, что решение по сути является композицией двух линейных поисков.

// Good structured programming:
// applying functional decomposition.
float* find_value
  (float *a, size_t size, float val)
{
  for (size_t i = 0; i < size; ++i)
    if (a[i] == val)
      return a + i;
  return nullptr;
}

float* find_row_without_zero_3
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (!find_value(a[i], cols, 0))
      return a[i];
  return nullptr;
}

Если предполагается использование STL (после первого семестра это ещё не предполагается), то явный цикл можно заменить на вызов std::find, так:

// Ah, std::find does the work in C++.
float* find_row_without_zero_4
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (std::find(a[i], a[i] + cols, 0.f) == a[i] + cols)
      return a[i];
  return nullptr;
}

или даже так (ещё std::find_if, шаблон по типу данных и значение по умолчанию вместо явного нуля):

// It's not beautiful, I guess...
template <class NT>
NT* find_row_without_zero_5
  (NT **a, size_t rows, size_t cols)
{
  const auto p = std::find_if(a, a + rows,
    [cols](NT *a)
    {
      return std::find(a, a + cols, NT{}) == a + cols;
    });
  return p == a + rows? nullptr: *p;
}

Последний вариант, впрочем, наверно, избыточно «навороченный».

Ну и наконец, можно поразвлекаться в функциональном стиле (требуется C++14), отказавшись от указателей и рассматривая матрицу как диапазон диапазонов. Будем возвращать итератор в стиле STL.

using std::forward;

template <class Item>
auto equals(Item &&item)
{
  return [it = forward<Item>(item)]
  (auto &&other)
  {
    return other == it;
  };
}

template <class Pred>
auto find(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::begin;
    using std::end;

    const auto e = end(rng);
    auto p = begin(rng);
    while (p != e && !pr(*p))
      ++p;

    return p;
  };
}

template <class Pred>
auto none(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::end;
    return find(pr)(rng) == end(rng);
  };
}

Вышеприведённые определения позволяют в итоге записать решение в виде композиции:

template <class Rng2>
auto find_row_without_zero_6(Rng2 &&rows)
{
  return find(none(equals(0)))(rows);
}

Забавно, что такая конструкция применима не только, например, к вектору векторов, но и к статическому двумерному массиву:

float m[3][4]
{
  { 1, 1, 1, 0 },
  { 0, 1, 1, 1 },
  { 1, 0, 1, 1 },
};

assert(find_row_without_zero_6(m) == std::end(m));
Реклама

Conar: минипарсер параметров командной строки

Как известно, задача распознавания параметров командной строки давно и неоднократно решена. Примеры (список далеко не полон): Boost.Program_options (навороченная, и, увы, требует сборки), TCLAP, ezOptionParser, AnyOption, The Lean Mean C++ Option Parser. Обзора я делать не буду, напишу лишь, что ознакомление с данными библиотеками не отбило у меня желание сделать свою :)

Я хочу библиотеку: header-only (вообще полностью определённую в одном заголовочном файле), C++ (поддержка STL-контейнеров, анонимных функций), никакого (L)GPL (Boost-лицензия лучшая же), использование только Стандартной библиотеки C++ (пусть с элементами ещё не принятого C++17), действительно простая схема использования, не требующая писать каскады if-else или switch-case и явно использовать механизмы type-erasure (void*, any и т.п.). Производительность же не играет особого значения. Особая универсальность также мне не нужна.

Такая библиотека может быть достаточно маленькой для ad hoc программирования (без проектирования). Однако это не самое простое упражнение в программировании. Попробую описать её разработку (начата на момент написания этих строк) «в ходе процесса» в нескольких постах.

Итак, с чего начать? Начнём с названия :) У меня это будет conar.hpp («console arguments»).

#ifndef CONAR_HPP_INCLUDED_N98K2U
#define CONAR_HPP_INCLUDED_N98K2U

namespace conar
{
  // ...
}

#endif//CONAR_HPP_INCLUDED_N98K2U

Далее весь код размещается внутри пространства имён conar. Необходимые #include подразумеваются и в тексте не упоминаются.

Ключ — имя опции (параметра командной строки). Опции может соответствовать несколько ключей. Если ключ состоит из одной буквы, то предполагается, что перед ним ставится один дефис («минус»). Если ключ состоит из нескольких букв (и, возможно, цифр), то перед ним ставится два дефиса (предполагаемое автоматическое дополнение пользовательских ключей). Если хочется иной формулировки, например, на дробь / как принято в Windows, то достаточно будет явно указать этот знак. Предполагается, что ключи чувствительны к регистру (в Windows принято иначе, да…). При поиске соответствия будем пытаться подобрать наиболее длинное возможное совпадение. Навскидку наивный алгоритм даёт в худшем случае время разбора O(N L log K + S), где N — количество параметров, L — длина наиболее длинного ключа, K — общее количество ключей, S — суммарное количество символов во всех параметрах.

Опция вида -abc интерпретируется как последовательность трёх опций -a -b -c, если не заданы явно ключи -abc или -ab. В последнем случае возможна попытка прочитать это как -ab c, успешность которой зависит от того, принимает ли -ab строку или символ.

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

  /// Basic description of a command line option.
  struct Option
  {
    using Possible_keys = std::vector<std::string>;
    using Info = std::string;

    /// Keys corresponding to this option.
    Possible_keys possible_keys;
    /// Information about this option (for help).
    Info info;

    virtual ~Option() {}
    // This class may be extended later.
  };

Классы опций. Наследники класса Option. Объекты этих классов хранят обработчики (handler) распознанных параметров.

Флаг — опция без параметров, соответственно, обработчик имеет сигнатуру void().

  struct Flag_option: Option
  {
    using Handler = std::function<void()>;
    Handler handler;
  };

Значение — опция с одним параметром заданного типа T. Посему это шаблон. Обработчик имеет сигнатуру void(T) и будет вызываться для каждого удачно распознанного ключа с параметром.

Пример (-t, --time, T = int)

-t1 --time=2 -t 3 6 7 --time 4 8 9 даст четыре вызова обработчика с параметрами 1, 2, 3 и 4.

  template <class T>
  struct Value_option: Option
  {
    using Handler = std::function<void(T)>;
    Handler handler;
  };

Последовательность — опция, предполагающая передачу последовательности значений заданного типа (T) после ключа. Обработчик имеет сигнатуру void(T*, T*) и принимает диапазон массива с очередной успешно считанной последовательностью значений (их может быть несколько — для каждого упоминания ключа).

Пример (-i, --input, T = string)

-i "a b c" d e --input "next time" do this даст два вызова с массивами { «a b c», «d», «e» } и { «next time», «do», «this» }.

  template <class T>
  struct Seq_option: Option
  {
    using Handler = std::function<void(T*, T*)>;
    Handler handler;
  };

Парсер. Главный компонент библиотеки. Опции будем регистрировать, передавая объекты классов-наследников Option с помощью оператора (), который возвращает ссылку на объект парсера. Параметры функции main для распознавания (после регистрации всех опций) также передадим оператором (). Т.е. предполагается использование вроде

Parser{}(опция 1)(опция 2)(опция 3)(argc, argv);

результат вызова — список (вектор) нераспознанных параметров (в текстовой форме «как есть»).

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

Итак, заготовка Parser.

  class Parser
  {
  public:
    /// Construct a help message part that describes all the options known to the parser.
    std::string help(int key_column_width = 20, int line_width = 80, const char *line_sep = "\n") const
    {
      std::string result;
      // TODO
      return result;
    }

    /// Add an option description. Use functions flag and value for this.
    template <class Opt>
    Parser& operator()(Opt option)
    {
      static_assert(std::is_base_of<Option, Opt>::value);
      // TODO
      return *this;
    }

    /// A list of unparsed parameters.
    using Unparsed_parameters = std::vector<std::string>;

    /// Finally parse the command-line parameters given by an iterator range (of strings).
    template <class InIt>
    Unparsed_parameters operator()(InIt from, InIt to)
    {
      static_assert(std::is_convertible<
        typename std::iterator_traits<InIt>::iterator_category,
        std::input_iterator_tag>::value);

      Unparsed_parameters unparsed;
      // TODO
      return unparsed;
    }

    /// Parse arguments as they are passed to main, argv[0] is ignored.
    Unparsed_parameters operator()(int argc, char *argv[])
    {
      return (*this)(argv + 1, argv + argc);
    }
  };

Вот так, раз-два и готов файлик в сотню строк. Которые, впрочем, пока абсолютно бесполезны…

Продолжение следует.

О реализации целочисленного аналога функции sqrt

Год назад я написал пост по обращению матриц определённого вида. Он возник не на пустом месте. Исходной посылкой послужило желание сконструировать способ качественного определения быстродействия маленьких быстро выполняющихся функций в условиях, «приближенных к реальности». На тот момент я пытался сравнивать быстродействие различных вариантов реализации функции вычисления целочисленного квадратного корня.

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

Но даже двоичный поиск можно реализовать по-разному. И естественно хочется уметь сравнивать быстродействие разных вариантов в разных условиях.

Неожиданным открытием при первом простом тестировании стала зависимость скорости выполнения функции от её положения в asm-файле (для ассемблерных вариантов). Директива align перед циклами, напротив, не продемонстрировала устойчивого эффекта. Наиболее вероятным «виновником» в данном случае является предсказатель ветвлений и особенности его работы для конкретного CPU. Также может сказываться работа L1I и TLB (здесь, в частности, может удачно или неудачно подействовать директива align).

В случае «простого» тестирования вроде многократного вызова одной функции в цикле есть немалый шанс натолкнуться на проявление таких особенностей во всей их красе. Поэтому я решил поступить несколько хитрее: выполнить псевдослучайное перемешивание разных вызовов. В каждом прогоне — разное количество вызовов разных функций. Выполнив столько же прогонов, сколько у нас есть функций, получим вектор суммарных времён и матрицу количеств вызовов. Решив линейное уравнение, получим оценки времени вызова каждой функции. Можно сделать и больше прогонов и получить решение с помощью МНК (здесь не реализовано). В итоге я всё же не стал использовать аналитически обращаемую матрицу, а задействовал библиотеку uBLAS из состава Boost. См. также о влиянии фрагментации кучи на результаты тестирования.

Использовалась среда Microsoft Visual C++ 2015, компиляция под x86-64 с O2. Причёсывать код однолетней давности я уже поленился — там есть, что выкинуть, но если бы я этим занялся, то… В общем, год уже и так прошёл.

Замечание. В MSVC все исходники .c, .cpp, .asm должны иметь разные имена, так как при компиляции каждого из них порождается одноимённый .obj файл, которые сваливаются в одну общую папку и могут затирать друг друга с печальным результатом во время компоновки.

Итак, исследуемые варианты:

  1. cpp1, asm1 — цикл + ветвление;
  2. cpp2, asm2 — цикл + cmov;
  3. cpp3, asm3 — цикл + ветвление + ilog2 (целочисленный логарифм позволяет выбрать хорошее начальное приближение, для его реализации на x86 используется команда bsr или lzcnt);
  4. cpp4, asm4 — цикл + cmov + ilog2;
  5. asm5 — развёрнутый вариант asm3;
  6. asm6 — развёрнутый вариант asm4 (computed goto);
  7. fpu — использует команды SSE для вычисления isqrt (стандартный метод);
  8. null — ничего не делает, используется для оценки времени вызова.

Итак, результаты тестирования представлены на графике ниже. Числа получены следующим образом: в каждом прогоне использовалось 100’000 псевдослучайных чисел-аргументов, равномерно распределённых от нуля до числа, указанного по оси 0x (1k — 1024, 32k — 32’768, 1M — 220, 1G — 230), выполнялось 1100 повторений, из которых верхние и нижние 5% полученных оценок времён отбрасывались, а от оставшихся 1000 бралось арифметическое среднее. Всего выполнялось по 10 таких прогонов, из результатов которых для каждой функции выбиралось минимальное значение и затем вычиталось соответствующее минимальное значение функции null. В конце все результаты нормировались по функции fpu, так что по оси 0y графиков мы видим, во сколько раз все варианты медленнее вычисления isqrt на fpu.

Процессор, на котором производился тест — AMD K10. Итак, мы видим, что «бодаться» с FPU на «больших» процессорах (пусть даже старых) бессмысленно. Пиррова победа в режиме 1k у asm4/cpp4. Применение ilog2 в комбинации с cmov даёт весьма неплохой эффект, который может оказаться ещё выше на простых процессорах без хорошего предсказателя переходов. А вот разворачивание цикла здесь не помогает (впрочем, опять же на «простом» процессоре ситуация может быть другой).