0

http://ideone.com/g7rGS7

如您所见，它超过了时间限制。

有人给了我一个想法，即拥有 10 个左右的空白空间静态变量并将它们连接起来形成更大的空间，所以我想尝试通过 2 的幂来实现。代码有效，但显然很慢。这样做的更快方法是什么？

std::string operator*(std::string const &s, size_t n)
{
    std::string r;
    r.reserve(n * s.size());
    for (size_t i=0; i<n; i++)
        r += s;
    return r;
}

std::string operator^(std::string const &s, size_t n)
{
    std::string r = s;
    for (size_t i = 1; i < n; i++)
    {
        r = s * r.size();
    }
    if (n == 0) return std::string(" ");
    return r;
}

int main()
{
    string blank = " ";
    string blank2 = blank * 2;
    string blank4 = blank2 ^ 2;
    string blank8 = blank2 ^ 3;
    string blank16 = blank2 ^ 4;

    for (int i = 0; i < 100; i++)
        assert((blank2 ^ i).size() == pow(2, i));

    return 0;
}
4

3 回答 3

1

如本评论中所述，您可以执行以下操作：

std::string str_double (std::string const & s)
{
    return s + s;
}

std::string operator*(std::string const &s, size_t n)
{
    return str_double(s * (n / 2)) + ((n % 2) ? s : std::string());
}

如果您的编译器和标准库支持右值引用和移动，我相信它会非常有效。

但是，我认为没有什么会比简单的版本快得多，如下所示：

std::string operator*(std::string const &s, size_t n)
{
    std::string r;
    r.resize (n * s.size()); // note resizing, not reserving
    for (size_t i = 0, j = 0; i < n; ++i, j += s.size())
        memcpy (&(r[j]), &(s[0]), s.size());
    return r;                
}
于 2013-08-15T18:45:11.603 回答
1

您的 operator^ 做了很多字符串分配。operator* 预先分配了字符串，这很好，但是您的 operator^ 每次调用 operator* 时都会创建一个中间字符串。相反，预先计算 r 的长度和所需的副本数。然后您可以预先分配 r 并执行连接，而无需创建一堆不需要的字符串。

于 2013-08-15T18:41:55.843 回答
0

如果您希望用 1 个字符（示例中的空格）填充它，那么使它们更快的方法是完全消除 for 循环：

int main()
{
    string blank2(2, ' ');
    string blank4(4, ' ');
    string blank8(8, ' ');
    string blank16(16, ' ');

    // etc

    return 0;
}

为了使其通用（因此您可以使用超过 1 个字符来执行此操作），您仍然需要限制循环：

std::string operator*(std::string const &s, size_t n)
{
    std::string r(n * s.size(), ' '); // initialize the string with the needed size
    for (size_t i=0; i<n; i++) // O(n)
        r += s;
    return r;
}

std::string operator^(std::string const &s, size_t n)
{
    size_t sn = std::pow(s.size(), n);
    std::string r(sn, ' ');
    for (size_t i = 1; i < sn; i++) // since this doesn't have an inner loop in the * operator, it is O(n) instead of O(n^2)
    {
        r += s;
    }
    return r;
}

int main()
{
    string blank = " ";
    string blank2 = blank * 2;
    string blank4 = blank2 ^ 2;
    string blank8 = blank2 ^ 3;
    string blank16 = blank2 ^ 4;

    for (int i = 0; i < 100; i++)
        assert((blank2 ^ i).size() == pow(2, i));

    return 0;
}
于 2013-08-15T19:05:57.563 回答