Блог

Я решаю задачу из Project Euler, которая включает в себя поиск треугольных, квадратных, пятиугольных, …, восьмиугольных чисел, поэтому я пытаюсь создать эту утилиту, которая будет проверять каждый вид чисел. Я решил создать сита для каждого набора чисел для быстрого доступа, и я сохраняю его в статическом массиве. Я смог создать универсальную функцию, которая будет генерировать каждое сито, но это оставляет каждую из функций проверки чрезвычайно похожей. Я не вижу хорошего способа избежать повторения кода в этих функциях из-за того, как они используют статические массивы bool. Какие у вас есть идеи по удалению этого?

 #ifndef FIGURATE_NUMBERS
#define FIGURATE_NUMBERS

#define SIEVE_MAX 10000

void populateFigurateSieve(bool* sieve, const int ADDER_INCREASE)
{
    int number = 0;
    int adder = 1;

    for (int i = 0; i < SIEVE_MAX; i  )
    {
        if (i == number)
        {
            sieve[i] = true;
            number  = adder;
            adder  = ADDER_INCREASE;
        }
        else
        {
            sieve[i] = false;
        }
    }

    return;
}

bool isTriangleNumber(long long int n)
{
    static bool triangleNumberSieve[SIEVE_MAX];
    static bool initialized = false;

    if (!initialized)
    {
        populateFigurateSieve(triangleNumberSieve, 1);
        initialized = true;
    }

    return triangleNumberSieve[n];
}

bool isSquareNumber(long long int n)
{
    static bool squareNumberSieve[SIEVE_MAX];
    static bool initialized = false;

    if (!initialized)
    {
        populateFigurateSieve(squareNumberSieve, 2);
        initialized = true;
    }

    return squareNumberSieve[n];
}

bool isPentagonalNumber(long long int n)
{
    static bool pentagonalNumberSieve[SIEVE_MAX];
    static bool initialized = false;

    if (!initialized)
    {
        populateFigurateSieve(pentagonalNumberSieve, 3);
        initialized = true;
    }

    return pentagonalNumberSieve[n];
}

#endif
  

Я восхищаюсь вашим подходом на C, но здесь, на C , людям нравятся классы. (-: Например, они позволяют вам не повторяться, абстрагируясь от постоянных значений. У вас есть один и тот же код для трех разных констант шага: 1, 2 и 3, поэтому вы можете создать шаблон для них, используя что-то вроде этого:

 #include <vector>

constexpr long long SIEVE_MAX = 10000;

template <int ADDER_INCREASE>
class GenericSieve
{
    static std::vector<bool> Sieve;

    static std::vector<bool> populated_sieve()
    {
        int number = 0;
        int adder = 1;
        std::vector<bool> sieve(SIEVE_MAX);

        for (int i = 0; i < SIEVE_MAX; i  )
        {
            if (i == number)
            {
                sieve[i] = true;
                number  = adder;
                adder  = ADDER_INCREASE;
            }
            else
            {
                sieve[i] = false;
            }
        }

        return sieve;
    }
public:
    static bool belongs(long long n)
    {
        if (Sieve.size() == 0)
        {
            Sieve = populated_sieve();
        }
        return Sieve.at(n);
    }
};
template<int inc>
std::vector<bool> GenericSieve<inc>::Sieve;

// define a sieve for every number you like
using TriangularSieve = GenericSieve<1>;
using SquareSieve = GenericSieve<2>;
using PentagonalSieve = GenericSieve<3>;

// define functions if you will
bool isTriangleNumber(long long int n)
{
    return TriangularSieve::belongs(n);
}
bool isSquareNumber(long long int n)
{
    return SquareSieve::belongs(n);
}
bool isPentagonalNumber(long long int n)
{
    return PentagonalSieve::belongs(n);
}

  

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

Шаблон действительно является способом факторизации кода, например:

 template <std::size_t N>
constexpr std::array<bool, N> make_sieve(std::size_t ADDER_INCREASE)
{
    std::size_t number = 0;
    std::size_t adder = 1;
    std::array<bool, N> sieve{};

    for (std::size_t i = 0; i < N; i  )
    {
        if (i == number)
        {
            sieve[i] = true;
            number  = adder;
            adder  = ADDER_INCREASE;
        }
        else
        {
            sieve[i] = false;
        }
    }
    return sieve;
}

template <std::size_t N, std::size_t Sieve>
constexpr bool belongs(long long n)
{
    constexpr auto sieve = make_sieve<N>(Sieve);

    return sieve[n];
}

constexpr std::size_t SIEVE_MAX = 10'000;

constexpr bool isTriangleNumber(long long int n) { return belongs<SIEVE_MAX, 1>(n); }
constexpr bool isSquareNumber(long long int n) { return belongs<SIEVE_MAX, 2>(n); }
constexpr bool isPentagonalNumber(long long int n) { return belongs<SIEVE_MAX, 3>(n); }
  

ДЕМОНСТРАЦИЯ

(Я бы предпочел std::bitset , но отсутствуют некоторые методы constexpr 🙁 )
(Если вы не можете использовать constexpr , static const auto sieve = make_sieve<N>(Sieve); это позволило бы вычислить его только один раз, без вашего флага инициализации).

 void doInit(boolamp; initialized, bool* sieve, int adderIncrease) {
  if (!initialized) {
    populateFigurateSieve(sieve, adderIncrease);
    initialized = true;
  }
}
  

Затем вы вызываете его с теми же параметрами, которые вызывали populateFigurateSieve раньше, за исключением того, что вы также передаете initialized переменную спереди.

Это экономит 2 строки в каждой функции, перенося проверку инициализации в функцию, а не повторяя 90% ее каждый раз.

Лучший способ следовать принципу DRY — попытаться увидеть, что общего у подобного кода. Здесь я заметил, что вы выполняли одинаковую проверку инициализации для каждой функции с основным отличием в том, как вы вызывали populateFigurateSieve функцию. Затем я создал функцию, параметризовав различия, сохранив при этом ту же общую структуру, что и при сходствах.

Редактировать: Еще лучше, вам не нужна инициализированная переменная. Вместо передачи указателя на функцию заполнения вы можете заставить ее создать и вернуть массив:

 #include <array>
// ...
std::array<bool, SIEVE_MAX> populateFigurateSieve(const int ADDER_INCREASE) {
  std::array<bool, SIEVE_MAX> sieve {};
  // ... (Your code should still work...,)
  return sieve;
}
// ...
// When making the sieve in the function:
static std::array<bool, SIEVE_MAX> sieve = populateFigurateSieve( /* Required value here */);
// No longer need initialized variable
// ....