"Industrial Strength" C++ 结构

Question

我已经有一段时间没有使用C++了。我被要求参加工作面试，为满足以下接口的下采样例程创建 C++ 结构：

struct  deterministic_sample
{
    deterministic_rate( double rate );
    bool operator()();
};

-- 具有以下行为：

我们有一个 class 的对象：deterministic_sample s;
我们调用s()N次，returnstrue,M次。 M/N大致等于率
顺序是确定的，不是随机的，每次都应该相同
class 应该是 "industrial strength"，以便在繁忙的流中使用。

我的解决方案，版本 2：

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

struct deterministic_sample
{
    double sampRate;
    int index;

    deterministic_sample() {
        sampRate = 0.1;
        index = 0;
    }

    void deterministic_rate( double rate ) {
        this->sampRate = rate;  // Set the ivar. Not so necessary to hide data, but just complying with the interface, as given...
        this->index = 0;  // Reset the incrementer
    };

    bool operator()() {

        if (this->index == INT_MAX) {
            this->index = 0;
        }

        double multiple = this->index * this->sampRate;

        this->index++;  // Increment the index

        if (fmod(multiple, 1) < this->sampRate) {
            return true;
        } else {
            return false;
        }

    };
};

int main()
{
    deterministic_sample s;  // Create a sampler
    s.deterministic_rate(0.253);  // Set the rate
    int tcnt = 0;  // Count of True
    int fcnt = 0;  // Count of False

    for (int i = 0; i < 10000; i++) {
        bool o = s();
        if (o) {
            tcnt++;
        } else {
            fcnt++;
        }
    }

    cout << "Trues: " << tcnt << endl;
    cout << "Falses: " << fcnt << endl;

    cout << "Ratio: " << ((float)tcnt / (float)(tcnt + fcnt)) << endl;  // Show M / N

    return 0;
}

面试官说这个 v2 代码 "partly" 解决了要求。 v1 没有构造函数（我的错误），也没有处理 int ivar 的溢出。

做这个 class robust/correct 我错过了什么？ 我认为这是 "industrial strength" 的某些方面错过了。

ps。对于任何道德类型，我已经提交了我的第二次机会尝试...只是让我很困扰知道为什么这是 "partly"...

Answer 1

使用unsigned，整数溢出是一个定义明确的环绕。这在正常 CPU 上非常快。

我看到的第二个问题是浮点数和整数数学的混合。那不是很有效。将 multiple 存储为成员并仅执行 multiple += rate 可能更有效。这为您节省了一个整数到双精度的转换。

不过，fmod还是挺贵的。您可以通过保留 int trueSoFar 来避免这种情况。现在到目前为止的速率是 double(trueSoFar)/double(index)，您可以检查 double(trueSoFar)/double(index) > rate 或更有效地 trueSoFar> int(index * rate)。正如我们已经看到的，rate*index 可以替换为 multiple += rate。

这意味着我们有一个双加法 (multiple +=)、一个 FP 到 int 的转换 int(multiple) 和一个整数比较。

[编辑] 您还可以通过保持 rate 的 32/32 有理近似值并将其与实现率（再次存储为 32/32 比率）进行比较来完全避免 FP 数学计算。因为 a/b > c/d 当 a*d > b*c 你可以在这里使用 64 位乘法。更好的是，对于目标比率，您可以选择 2^32 作为固定分母（即 unsigned long targetRate = rate*pow(2^32)，b=2^32 隐式），这样您现在就有了 unsigned long(unsigned long long(a)*index) >> 32) > trueSoFar。即使在 32 位 CPU 上，这也相当快。 >>32 是空操作。

Answer 2

你所拥有的比需要的要复杂得多。您需要做的就是跟踪当前位置，并在超过阈值时 return true。

struct deterministic_sample
{
    double sampRate;
    double position;

    deterministic_sample() : sampRate(0.1), position(0.0) {
    }

    void deterministic_rate( double rate ) {
        assert(rate <= 1.0); // Only one output is allowed per input
        sampRate = rate;  // Set the ivar. Not so necessary to hide data, but just complying with the interface, as given...
        // No need to reset the position, it will work with changing rates
    };

    bool operator()() {
        position += sampRate;
        if (position < 1.0)
            return false;
        position -= 1.0;
        return true;
    }
};

Answer 3

您的代码有几个问题：

准确度：在 10 000 次迭代中，您获得 0.2535。那是 10000 上的 5 的错误。我预计 10000 上的最大错误为 4。速率为 0.253。
不连续性：处理溢出时，您会用 0 突然重新启动索引。因此会有明显的不连续性。当然，总体来说，可以忽略不计
符合规范：您随意决定在更改采样率时从0重新开始。虽然这似乎可以接受，但并未明确要求此行为。可以想象（尤其是在工业环境中），如果您稍微修改速率，输出将尽快适应新速率，而不会失去与之前输出相比的连续性。
语法：两个成员函数定义后有一个不必要的;，你用不必要的this->来引用局部变量。当然没有错，但是...

这是一个替代方案：

struct deterministic_sample
{
    double sampRate;
    unsigned long rtt; // tottal number of true returned
    unsigned long rts; // total answers 

    deterministic_sample() : sampRate (0.1), rtt(0), rts(0) { }

    void deterministic_rate(double rate) {
        sampRate = rate;   // continue output but with a new performance rate. 
    }

    bool operator()() {
        if (rts == LONG_MAX) {  // in case of owerflow
            rtt = 1000.0*rtt/rts; rts = 1000;  // restart, but minimizing discontinuity
        }
        bool ret = rts==0 || (double)rtt / rts < sampRate;  // catch up algorithm
        if (ret)    // update counters
            rtt++;
        rts++;
        return ret;
    }
};

Answer 4

好的，所以似乎可以（当然）对效率进行一些改进，"industrial strength" 有一些影响，但没有具体的（可能是问题......），或者构造函数在问题中被错误地命名（也可能）。

无论如何，没有人跳出我对我的构造函数所做的一些明显遗漏（比如，我看到有两种方法可以做一个 C++ 构造函数；你应该两种都做才能真正防弹，等等.)

我想我会祈祷，希望我仍然能够参加软技能面试！谢谢大家

"Industrial Strength" C++ 结构

"Industrial Strength" C++ struct

c++

constructor

struct