Как избежать дублирования кода, когда единственным отличием являются операторы управления циклами (с теми же операторами в теле цикла)?
В моем коде решения для задачи 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;
}
}
}
5 ответов
Хотя я думаю, что то, что у вас уже есть, будет хорошо после того, как вы вставите блоки кода внутреннего цикла в обычную функцию, как предложили Адам Берри и Тони Д., если вы хотите, вы можете объединить циклы, используя таблицы для кодирования возможных направлений для перемещения. Хитрость заключается в использовании массива 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;
}
Предположим, вы выровняли сетку так, чтобы в ней было всего 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,
Диагонали мало чем отличаются. Попробуйте на бумаге (бумага с сеткой хороша для такого рода вещей.)
Еще один совет: имеет ли значение, если вы найдете произведение четырех элементов, умноженных слева направо, чем те же четыре элемента, умноженные справа налево?
Вы можете создать перечисление для разных состояний и затем передать его в функцию. Затем вы должны создать оператор if, который будет устанавливать значения на основе переданного значения.
Ваш process_row() имеет ошибку: из примера в ссылке, в матрице допустимы нулевые записи, поэтому, если строка начинается с, например,
x y z 0 ...
и любой из x, xy или xyz больше, чем все другие продукты из 4 элементов в остальной части этой строки и в любой другой строке в матрице, он будет неверно сообщать, что это самый большой продукт из 4 элементов. (Я предполагаю, что здесь Max_consecutive_prod рассчитывает прокатное произведение последних 4 элементов, обеспеченных input()).
Если только ваш Max_consecutive_prod необычно осведомлен о том, как он вызывается, вы также получите ошибочные результаты "переноса" с конца одного ряда на следующий и от одного process_...() звоните к следующему.
Во-первых, объектный подход 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 можно комбинировать с различными процедурами итерации элементов сетки.