“产业实力”C++结构

Question

我已经有一段时间没有使用C++了。我被要求参加面试以创建一个C++结构，用于下采样例程，它将满足以下界面：

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

-行为如下：

• 我们有一个该类的对象：deterministic_sample s;
• 我们称之为s() N倍，它返回true，M次。M/N大约等于这个速率
• 序列是确定性的，不是随机的，每次都应该是相同的。
• 这个班应该是“工业实力”，以便在繁忙的溪流上使用。

我的解决方案，第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代码“部分”解决了这些要求。v1没有构造函数(我的错误)，也没有处理int ivar的溢出。

，为了使这门课变得健壮/正确，我在这里错过了什么？，我认为这是我错过的“工业实力”的某些方面。

ps。对于任何道德类型，我已经提交了我的第二次尝试.我只想知道为什么这“部分”.

Answer 1

好的，看来在效率上有了一些改进(当然)，“工业实力”没有具体的含义(可能是问题.)，或者构造函数在问题中被错误地命名了(也可能)。

无论如何，没有人会对我对构造函数所做的明显遗漏(比如，我看到有两种方法来做C++构造函数；您应该做到这两种方法都是防弹的，等等)。

我想我只是祈祷我的手指，并希望我仍然前进的软技能面试！谢谢大家。

Answer 2

你所拥有的远比必要的复杂得多。您所需要做的就是跟踪当前位置，并在超过阈值时返回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

使用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在那里是个无名小卒.