を算術ソリューション
一つは、あなたの関数が返すべきかを定義した場合「f(a, b)
は、a
の除算結果の最も近い整数を返します。これはです。は実際の除数の環にあります。
このように、問題は次のようにまとめることができます。この最も近い整数を整数除算だけで定義できますか?私たちはできると思います。
に最も近い整数は:a/b
と(a/b) + 1
(1)という2つの候補があります。 a % b
が0
に近い場合はb
になるので、a/b
の結果が簡単です。そうでない場合は、(a/b) + 1
です。この定義は、ニーズを満たしながら、1が使用してb
によってa
の2回の分裂を計算しないことによって、それを最適化することができ
int divide(int a, int b)
{
const int quot = a/b;
const int rem = a % b;
int result;
if (rem < b - rem) {
result = quot;
} else {
result = quot + 1;
}
return result;
}
:
一つは、最適化し、優れた慣行を無視して、に似た書き込み何かをできましたstd::div()
の:
int divide(int a, int b)
{
const std::div_t dv = std::div(a, b);
int result = dv.quot;
if (dv.rem >= b - dv.rem) {
++result;
}
return result;
}
我々は以前の私たちの実装のよく定義された行動を私たちに保証した問題の分析。
(1)最後にチェックするのは1つだけです:a
またはb
が負の場合、どのように動作しますか?これは読者に任されている;)。
ベンチマーク
#include <iostream>
#include <iomanip>
#include <string>
// solutions
#include <cmath>
#include <cstdlib>
// benchmak
#include <limits>
#include <random>
#include <chrono>
#include <algorithm>
#include <functional>
//
// Solutions
//
namespace
{
int round_divide_by_float_casting(int a, int b) {
return (int)roundf(a/(float)b);
}
int round_divide_by_modulo(int a, int b) {
return a/b + a % b * 2/b;
}
int divide_by_quotient_comparison(int a, int b)
{
const std::div_t dv = std::div(a, b);
int result = dv.quot;
if (dv.rem >= b - dv.rem)
{
++result;
}
return result;
}
}
//
// benchmark
//
class Randomizer
{
std::mt19937 _rng_engine;
std::uniform_int_distribution<int> _distri;
public:
Randomizer() : _rng_engine(std::time(0)), _distri(std::numeric_limits<int>::min(), std::numeric_limits<int>::max())
{
}
template<class ForwardIt>
void operator()(ForwardIt begin, ForwardIt end)
{
std::generate(begin, end, std::bind(_distri, _rng_engine));
}
};
class Clock
{
std::chrono::time_point<std::chrono::steady_clock> _start;
public:
static inline std::chrono::time_point<std::chrono::steady_clock> now() { return std::chrono::steady_clock::now(); }
Clock() : _start(now())
{
}
template<class DurationUnit>
std::size_t end()
{
return std::chrono::duration_cast<DurationUnit>(now() - _start).count();
}
};
//
// Entry point
//
int main()
{
Randomizer randomizer;
std::array<int, 1000> dividends; // SCALE THIS UP (1'000'000 would be great)
std::array<int, dividends.size()> divisors;
std::array<int, dividends.size()> results;
randomizer(std::begin(dividends), std::end(dividends));
randomizer(std::begin(divisors), std::end(divisors));
{
Clock clock;
auto dividend = std::begin(dividends);
auto divisor = std::begin(divisors);
auto result = std::begin(results);
for (; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result)
{
*result = round_divide_by_float_casting(*dividend, *divisor);
}
const float unit_time = clock.end<std::chrono::nanoseconds>()/static_cast<float>(results.size());
std::cout << std::setw(40) << "round_divide_by_float_casting(): " << std::setprecision(3) << unit_time << " ns\n";
}
{
Clock clock;
auto dividend = std::begin(dividends);
auto divisor = std::begin(divisors);
auto result = std::begin(results);
for (; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result)
{
*result = round_divide_by_modulo(*dividend, *divisor);
}
const float unit_time = clock.end<std::chrono::nanoseconds>()/static_cast<float>(results.size());
std::cout << std::setw(40) << "round_divide_by_modulo(): " << std::setprecision(3) << unit_time << " ns\n";
}
{
Clock clock;
auto dividend = std::begin(dividends);
auto divisor = std::begin(divisors);
auto result = std::begin(results);
for (; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result)
{
*result = divide_by_quotient_comparison(*dividend, *divisor);
}
const float unit_time = clock.end<std::chrono::nanoseconds>()/static_cast<float>(results.size());
std::cout << std::setw(40) << "divide_by_quotient_comparison(): " << std::setprecision(3) << unit_time << " ns\n";
}
}
出力:
Demo
2つの算術ソリューション公演
g++ -std=c++11 -O2 -Wall -Wextra -Werror main.cpp && ./a.out
round_divide_by_float_casting(): 54.7 ns
round_divide_by_modulo(): 24 ns
divide_by_quotient_comparison(): 25.5 ns
ありません区別できる(あなたがベンチサイズをスケールアップしたときに、そのベンチマークが収束)。
私の場合は、最初の方がはるかに明確です。私はそれが何をしようとしているのか知っています。私はそれをどうしようとしているのか分かっています。私は紙でそれを実行することなく、私は2番目のものが何をしているのか分かりません。私はまた、2番目の算術演算を行うので、最初の方が速くなると指摘しています – John3136
私は透明度が重要であることに同意します。しかし、操作の複雑さ(と速度)については、わかりません。 –