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

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 に答える