Tag Archives: goto

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

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

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

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

Решение в стиле 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));

Обратно к goto

Задача

Дан текст (массив 8-битных символов), получить из него текст с нормализованными переводами строк. Предполагаются возможными следующие варианты оформления переводов строк:

  • 1-символьные: LF (linefeed, символ с кодом 10, ‘\n’, ‘\xa’), CR (carriage return, символ с кодом 13, ‘\r’, ‘\xd’);
  • 2-символьные: CR LF и LF CR.

Любой из этих вариантов должен заменяться на один символ LF.

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

Алгоритм

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

  • Все символы, кроме LF и CR просто копируются, в случае же обнаружения CR или LF записываем перевод строки и переходим в состояние «встретился CR» или «встретился LF» соответственно. Если затем встретится не (LF или CR), то записываем встретившийся символ и выходим из этих состояний в исходное состояние.
  • Если встретился тот же символ CR или LF соответственно, то записываем перевод строки и остаёмся в том же состоянии.
  • Если же встретился «перекрёстный» символ LF или CR соответственно, то переходим в новое состояние «комбинация» (отвечающее двухсимвольному переводу строки), выход из которого производится с выводом перевода строки и «другого символа», если таковой встретился, либо возможен возврат в состояния «встретился CR» и «встретился LF» при получении соответствующих символов.
  • Выход происходит, когда исходный массив будет просмотрен целиком.

Впрочем, нетрудно заметить, что по сути состояние «комбинация» совпадает с начальным состоянием «общее», т.е. состояния LF и CR попросту «поглощают» перекрёстный символ. Более подробно и ясно этот алгоритм можно представить в виде схемы конечного автомата.

Конечный автомат

CR LF finite state machine scheme

Схема конечного автомата

Программа

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

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

Итак, получим

char* normalize(const char *from, const char *end, char *to)
{
  char ch;
Begin_:
  if (from == end) return to;
  ch = *from++;
  if (ch == '\n') goto LF_;
  if (ch == '\r') goto CR_;
  *to++ = ch;
  goto Begin_;

LF_:
  *to++ = '\n';
  if (from == end) return to;
  ch = *from++;
  if (ch == '\r') goto Begin_;
  if (ch == '\n') goto LF_;
  *to++ = ch;
  goto Begin_;

CR_:
  *to++ = '\n';
  if (from == end) return to;
  ch = *from++;
  if (ch == '\n') goto Begin_;
  if (ch == '\r') goto CR_;
  *to++ = ch;
  goto Begin_;
}

Данный код достаточно эффективен (хотя я не исключаю, что для этой задачи есть реализация получше). Состояние автомата определяется тем, какой участок кода исполняет процессор в данный момент. Не вводя переменные для явного хранения состояния автомата, можно придать данному коду немного более «структурный» вид, убрав goto. Код, впрочем, становится длиннее.

char* normalize(const char *from, const char *end, char *to)
{
  char ch;
  while (from != end)
  {
    switch (ch = *from++)
    {
    case '\n':
      do
      {
        *to++ = '\n';
        if (from == end)
          return to;
        ch = *from++;
      } while (ch == '\n');
      if (ch != '\r')
        *to++ = ch;
      break;

    case '\r':
      do
      {
        *to++ = '\n';
        if (from == end)
          return to;
        ch = *from++;
      } while (ch == '\r');
      if (ch != '\n')
        *to++ = ch;
      break;

  default:
    *to++ = ch;
  }
  return to;
}

Switch-case

Стандартный «структурный» подход к переводу конечных автоматов на язык программирования заключается во введении перечислимого типа, задающего набор возможных состояний автомата, переменной state, хранящей текущее состояние явно, и кодированию действий автомата в зависимости от текущего состояния в виде конструкции switch (state) { case … }, выполняемой в цикле.

Часто разница в производительности результирующего машинного кода варианта на основе switch-case не отличается заметно от варианта на goto (банальное чтение символа из потока ввода может оказаться достаточно дорогой операцией на фоне затрат на выполнение switch-case), однако у варианта switch-case есть ещё то практическое преимущество, что такой автомат позволяет более гибкое использование (здесь для простоты не будем рассматривать сопроцедуры как вариант реализации автомата) — явно хранимое состояние можно сохранить и потом запустить автомат «со старого места».

В данной задаче можно себе представить загрузку символов в буфер (массив), обработка и… повторная загрузка и обработка, но автомат нельзя каждый раз запускать из состояния Begin, т.к. 2-символьный перевод строки может оказаться разбит между двумя загрузками и в результате интерпретирован как два перевода, а не один. Т.е. автомат должен «помнить» своё последнее состояние.

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

struct NewLineNormalizer
{
  enum State { Begin, LF, CR };
  State state;

  explicit NewLineNormalizer(State st = Begin)
    : state(st) {}

  char* operator()(const char *from, const char *end, char *to)
  {
    if (from == end)
      return to;

    char ch;
    switch (state)
    {
    case LF: goto LF_;
    case CR: goto CR_;
    default:; // Begin falls-through here
    }

    do
    {
      switch (ch = *from++)
      {
      case '\n':
        do
        {
          *to++ = '\n';
          if (from == end)
            return state = LF, to;
        LF_:
          ch = *from++;
        } while (ch == '\n');
        if (ch != '\r')
          *to++ = ch;
        break;

      case '\r':
        do
        {
          *to++ = '\n';
          if (from == end)
            return state = CR, to;
        CR_:
          ch = *from++;
        } while (ch == '\r');
        if (ch != '\n')
          *to++ = ch;
        break;

      default:
        *to++ = ch;
      }
    } while (from != end);

    state = Begin;
    return to;
  }
};

Ниже UPD 19.04.2015.

Switch-case + goto

Хотя выше и приведены варианты, «избавленные» от goto, выглядят они явно запутаннее, чем goto, отвечающие схеме автомата. В последнем случае («гибридном варианте») всё равно использовался goto для «заскока» в нужное место ранее остановленного автомата. Поэтому я решил добавить ещё один «гибридный вариант» — уже на основе оригинального goto-варианта.

class NewLineNormalizer
{
  enum { Begin, LF, CR } state;

public:
  // Конструктор устанавливает начальное состояние.
  NewLineNormalizer() : state(Other) {}

  // Оператор "скобки" позволяет вызывать объект данного класса как функцию.
  // Возвращает указатель на символ, следующий за последним записанным символом.
  char* operator()(const char *from, const char *end, char *to)
  {
    char input;
    switch (state)
    {
    Begin_:
    case Begin:
      if (from == end) // выход
        return state = Begin, to;
      input = *from++;
      if (input == '\n') goto LF_;
      if (input == '\r') goto CR_;
      *to++ = input;
      goto Begin_;

    LF_:
      *to++ = '\n';
    case LF:
      if (from == end) // выход
        return state = LF, to;
      input = *from++;
      if (input == '\r') goto Begin_;
      if (input == '\n') goto LF_;
      *to++ = input;
      goto Begin_;

    CR_:
      *to++ = '\n';
    case CR:
      if (from == end) // выход
        return state = CR, to;
      input = *from++;
      if (input == '\n') goto Begin_;
      if (input == '\r') goto CR_;
      *to++ = input;
      goto Begin_;

    default:
      assert(false);
      return to;
    }
  }
};