反復定式化:
bool in_range(int input, int min, int max)
{
if (input <= 0)
return true; // FIXME handle negative and zero-prefixed numbers
int multiplier = 1;
while ((input + 1) * multiplier - 1 < min) // min <= [input]999
multiplier *= 10; // TODO consider overflow
return input * multiplier <= max; // [input]000 <= max
}
より単純な [編集: より効率的な; 以下を参照] メソッドは、切り捨て整数除算を使用することです。
bool in_range(int input, int min, int max)
{
if (input <= 0)
return true;
while (input < min) {
min /= 10;
max /= 10;
}
return input <= max;
}
テストとプロファイリング:
#include <iostream>
#include <chrono>
bool ecatmur_in_range_mul(int input, int min, int max)
{
int multiplier = 1;
while ((input + 1) * multiplier - 1 < min) // min <= [input]999
multiplier *= 10; // TODO consider overflow
return input * multiplier <= max; // [input]000 <= max
}
bool ecatmur_in_range_div(int input, int min, int max)
{
while (input < min) {
min /= 10;
max /= 10;
}
return input <= max;
}
bool t12_isInRange(int input, int min, int max)
{
int multiplier = 1;
while(input*multiplier <= max)
{
if(input >= min / multiplier) return true;
multiplier *= 10;
}
return false;
}
struct algo { bool (*fn)(int, int, int); const char *name; } algos[] = {
{ ecatmur_in_range_mul, "ecatmur_in_range_mul"},
{ ecatmur_in_range_div, "ecatmur_in_range_div"},
{ t12_isInRange, "t12_isInRange"},
};
struct test { int input, min, max; bool result; } tests[] = {
{ 1, 5, 9, false },
{ 6, 5, 9, true },
{ 1, 5, 11, true }, // as 10 and 11 are in the range
{ 1, 5, 200, true }, // as e.g. 12 and 135 are in the range
{ 11, 5, 12, true },
{ 13, 5, 12, false },
{ 13, 5, 22, true },
{ 13, 5, 200, true }, // as 130 is in the range
{ 2, 100, 300, true }, // as 200 is in the range
{ 13, 135, 140, true }, // Ben Voigt
{ 13, 136, 138, true }, // MSalters
};
int main() {
for (auto a: algos)
for (auto t: tests)
if (a.fn(t.input, t.min, t.max) != t.result)
std::cout << a.name << "(" << t.input << ", " << t.min << ", " << t.max << ") != "
<< t.result << "\n";
for (auto a: algos) {
std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
for (auto t: tests)
for (int i = 1; i < t.max * 2; ++i)
for (volatile int j = 0; j < 1000; ++j) {
volatile bool r = a.fn(i, t.min, t.max);
(void) r;
}
std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
std::cout << a.name << ": "
<< std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << '\n';
}
}
驚くべきことに (少なくとも私にとっては) 反復除算が最も速くなります:
ecatmur_in_range_mul: 17331000
ecatmur_in_range_div: 14711000
t12_isInRange: 15646000