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

В моем решении код для задача Эйлера проекта 11, Я получил следующие функции. Max_consecutive_prod это класс, который рассчитывает максимальное произведение последовательных input()числа, обобщенные из проблема 8. Шесть функций рассчитывают максимальное произведение в разных сериях разных направлений и начинают с разных краев сетки.

Единственная разница в этих функциях — это индексы в for Скажите, как устранить очевидное дублирование? Ситуация здесь как-то противоположна типичному применению template method шаблон: операция идентична, но структура управления отличается, есть ли другой шаблон дизайна для этого?

Изменить: все изменения, указанные в комментариях к (два) for операторы, и тело цикла в каждой функции идентично первой.

template <size_t size> unsigned process_row(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int i = 0; i < size; ++i)
{
Max_consecutive_prod mcp;
for (int j = 0; j < size; ++j)
{
mcp.input(grid[i][j]);
}
if (mcp.result() > prodMax)
{
prodMax = mcp.result();
}
}
return prodMax;
}
// exchange i, j in process_row
template <size_t size> unsigned process_col(const unsigned (&grid)[size][size])
{
// ...
}

template <size_t size> unsigned process_diag_lower(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int init = 0; init < size; ++init)
{
Max_consecutive_prod mcp;
for (int i = init, j = 0; i < size && j < size; ++i, ++j)
// ...
// ...
}
return prodMax;
}
// exchange i, j in process_diag_lower
template <size_t size> unsigned process_diag_upper(const unsigned (&grid)[size][size])
{
// ...
}
// flip j in process_diag_lower
template <size_t size> unsigned process_rev_diag_lower(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int init = 0; init < size; ++init)
{
Max_consecutive_prod mcp;
for (int i = init, j = size-1; i < size && j >= 0; ++i, --j)
// ...
// ...
}
return prodMax;
}
// change ++j in process_diag_upper to --j
template <size_t size> unsigned process_rev_diag_upper(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int init = 0; init < size; ++init)
{
Max_consecutive_prod mcp;
for (int j = init, i = 0; j >=0 && i < size; ++i, --j)
// ...
// ...
}
return prodMax;
}

Основываясь на коде случайного хакера, который показывает реальную общность и изменчивость потоков управления шестью функциями, я написал свою версию и сделал код более понятным и идиоматическим в C ++, используя stragegy класс, определяющий локальные переменные для уточнения кода и повышения эффективности. Я определяю не шаблонную версию process(), чтобы избежать раздувания двоичного кода при создании экземпляров для разных size (см. «Эффективный C ++», пункт 44).

Если вы все еще запутались, прочитайте ответ случайного хакера для объяснения. 🙂

namespace Grid_search
{
enum Step { neg = -1, nul, pos };
enum Index_t { i, j };

struct Strategy
{
Step direction[2];
Index_t varOuter;
};

const size_t typeCount = 6;
const Strategy strategy[typeCount] = { {{pos, nul}, i}, {{nul, pos}, j}, {{pos, pos}, i}, {{pos, pos}, j}, {{pos, neg}, i}, {{pos, neg}, j} };
};

template <size_t size> inline unsigned process(const Grid_search::Strategy& strategy, const unsigned (&grid)[size][size])
{
return process(strategy, reinterpret_cast<const unsigned*>(&grid), size);
}

unsigned process(const Grid_search::Strategy& strategy, const unsigned* grid, size_t size)
{
using namespace Grid_search;

const Index_t varOuter = strategy.varOuter, varInner = static_cast<Index_t>(!varOuter);
const Step di = strategy.direction[i], dj = strategy.direction[j];
const unsigned initInner = strategy.direction[varInner] == pos ? 0 : size -1;

unsigned prodMax = 0;
unsigned index[2];
unsigned &indexI = index[i], &indexJ = index[j];
for (unsigned initOuter = 0; initOuter < size; ++initOuter)
{
Max_consecutive_prod mcp;
for (index[varOuter] = initOuter, index[varInner] = initInner;
0 <= indexI && indexI < size && 0 <= indexJ && indexJ < size;
indexI += di, indexJ += dj)
{
mcp.input(grid[indexI*size + indexJ]);
if (mcp.result() > prodMax)
{
prodMax = mcp.result();
}
}
}
return prodMax;
}int main()
{
static const size_t N = 20;
unsigned grid[N][N];

std::ifstream input("d:/pro11.txt");
for (int count = 0; input >> grid[count/N][count%N]; ++count)
{
}

unsigned prodMax = 0;
for (int i = 0; i < Grid_search::typeCount; ++i)
{
unsigned prod = process(Grid_search::strategy[i], grid);
if (prod > prodMax)
{
prodMax = prod;
}
}
}

0

Решение

Хотя я думаю, что то, что у вас уже есть, будет в порядке после прикрепления блоков кода внутреннего цикла в обычной функции, как это предложили Адам Берри и Тони Д., если вы хотите, вы можете объединить циклы, используя таблицы для кодирования возможных направлений движения. Хитрость заключается в использовании массива p[2] вместо отдельных i а также j, чтобы включить вопрос какой индекс изменяется во внешнем цикле быть ведомым столом. Тогда единственная хитрость заключается в том, чтобы убедиться, что другой индекс, который будет изменяться во внутреннем цикле, должен начинаться с максимального значения (вместо 0), если он будет уменьшаться на каждом шаге:

enum indices { I, J };       // Can just use 0 and 1 if you want
template <size_t size> unsigned process(const unsigned (&grid)[size][size]) {
static int d[][2] = { {1, 0}, {0, 1}, {1, 1}, {1, -1}, {1, 1}, {1, -1} };
static int w[]    = {      J,      I,      J,       J,      I,       I };
unsigned prodMax = 0;    // Note: not 1
for (int k = 0; k < sizeof d / sizeof d[0]; ++k) {  // For each direction
for (int init = 0; init < size; ++init) {
Max_consecutive_prod mcp;
int p[2];        // p[I] is like i, p[J] is like j
for (p[w[k]] = init, p[!w[k]] = (d[k][!w[k]] == -1 ? size - 1 : 0);
min(p[I], p[J]) >= 0 && max(p[I], p[J]) < size;
p[I] += d[k][I], p[J] += d[k][J])
{
mcp.input(grid[p[I]][p[J]]);
prodMax = max(prodMax, mcp.result());
}
}
}

return prodMax;
}
0

Другие решения

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

0

Ваш process_row() имеет ошибку: из примера в ссылке, в матрице допустимы нулевые записи, поэтому, если строка начинается с, например,

x y z 0 ...

и любой из x, xy или xyz больше, чем все другие продукты с 4 элементами в остальной части этой строки и в любой другой строке в матрице, он будет неправильно сообщать, что это самый большой продукт с 4 элементами. (Я предполагаю, что здесь Max_consecutive_prod рассчитывает прокатное произведение последних 4 элементов, обеспеченных input()).

Если только ваш Max_consecutive_prod необычно осведомлен о том, как он вызывается, вы также получите ошибочные результаты «переноса» с конца одного ряда на следующий и от одного process_...() звоните к следующему.

0

Предположим, вы выровняли сетку так, чтобы в ней было всего 400 чисел подряд, читая слева направо, а затем сверху вниз. Самая верхняя строка будет состоять из первых 20 чисел (то есть индексы 0, …, 19); второе число из следующих 20 номеров и т. д. В общем, ряд i (начиная с 0) будет соответствовать индексам i*20, i*20 + 1, i*20 + 2, ..., i*20 + 19,

Теперь, как насчет столбцов? Крайний левый столбец начинается с позиции 0, как и самый верхний ряд. Это следующий элемент в позиции 20 (первый элемент во второй строке), а затем 40, и … Так что нетрудно увидеть, что индексы для столбца j являются j, j + 20, j + 40, ..., j + 19*20,

Диагонали мало чем отличаются. Попробуйте на бумаге (бумага с сеткой хороша для такого рода вещей.)

Еще один совет: имеет ли значение, если вы найдете произведение четырех элементов, умноженных слева направо, чем те же четыре элемента, умноженные справа налево?

0

Во-первых, объектный подход Context — это просто упаковка аргументов для функций поддержки, упомянутых в моем комментарии к вашему вопросу … он настолько же полезен, насколько существенной была проблема; -].

struct Context
{
unsigned& proxMax;
int i, j;
Max_consecutive_prod mcp;
Context(unsigned& prodMax) : prodMax(prodMax) { }
};

template <size_t size> unsigned process_diag_lower(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int init = 0; init < size; ++init)
{
Context context(prodMax);
for (context.i = init, context.j = 0; context.i < size && context.j < size; ++context.i, ++context.j)
loop_ij(context);
loop_outer(context);
}
return prodMax;
}

Шаблон посетителя. Теперь, я сказал в своем комментарии: «Вы не показываете нам достаточно тел циклов, чтобы увидеть общие требования», и с тех пор ничего не видел, поэтому на основе одного тела, которое я видел, а именно:

template <size_t size> unsigned process_row(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int i = 0; i < size; ++i)
{
Max_consecutive_prod mcp;
for (int j = 0; j < size; ++j)
{
mcp.input(grid[i][j]);
}
if (mcp.result() > prodMax)
{
prodMax = mcp.result();
}
}
return prodMax;
}

Выше можно разделить:

template <size_t size, template Visitor>
unsigned visit_row(const unsigned (&grid)[size][size], Visitor& visitor)
{
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < size; ++j)
visitor.inner{grid[i][j]);
visitor.outer();
}
return visitor.result();
}

struct Visitor
{
unsigned prodMax;
Max_consecutive_prod mcp;
Visitor() : prodMax(0) { }
void inner(unsigned n) {  mcp.input(n); }
void outer()
{
if (mcp.result() > prodMax) prodMax = mcp.result();
mcp = Max_consecutive_prod();  // reset for next time...
}
unsigned result() const { return prodMax; }
};

Таким образом, один и тот же класс Visitor можно комбинировать с различными процедурами итерации элементов сетки.

0