35

次のコードを検討してください。

public String joinWords(String[] words) {
    String sentence = "";
    for(String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}

連結ごとに文字列の新しいコピーが作成されるため、全体的な複雑さはO(n^2). 幸いなことに、Java ではこれを で解決できます。StringBufferこれはO(1)追加ごとに複雑であり、全体の複雑さは になりますO(n)。

C++ では、のstd::string::append()複雑さがありますO(n)が、 の複雑さについては明確ではありませんstringstream。

C++ にはStringBuffer、同じ複雑さのメソッドがありますか?

4

3 に答える 3

33

C++ 文字列は変更可能であり、StringBuffer とほぼ同じように動的にサイズ変更できます。Java とは異なり、このコードは毎回新しい文字列を作成しません。現在のものに追加するだけです。

std::string joinWords(std::vector<std::string> const &words) {
    std::string result;
    for (auto &word : words) {
        result += word;
    }
    return result;
}

reserve事前に必要なサイズの場合、これは線形時間で実行されます。問題は、ベクトルをループしてサイズを取得する方が、文字列の自動サイズ変更よりも遅くなるかどうかです。それは、私はあなたに言うことができませんでした。時間を計る。:)

なんらかの理由でそれ自体を使用したくない場合std::string(そしてそれを考慮する必要があります。これは完全に立派なクラスです)、C++ には文字列ストリームもあります。

#include <sstream>
...

std::string joinWords(std::vector<std::string> const &words) {
    std::ostringstream oss;
    for (auto &word : words) {
        oss << word;
    }
    return oss.str();
}

おそらく、 を使用するよりも効率的ではありませんstd::stringが、他の場合にはもう少し柔軟です。それを使用すると、ほぼすべてのプリミティブ型と、operator <<(ostream&, its_type&)オーバーライドを指定した任意の型を文字列化できます。

于 2013-03-14T03:43:41.367 に答える
17

これはあなたの質問に多少接していますが、それでも関連しています。（そして、コメントするには大きすぎます!!）

連結ごとに文字列の新しいコピーが作成されるため、全体的な複雑さは O(n^2) になります。

s1.concat(s2)Java では、またはの複雑さはs1 + s2、O(M1 + M2)それぞれの文字列の長さです。それを一連の連結の複雑さに変えることは、一般的に困難です。ただし、長さの文字列の連結を想定すると、複雑さは実際に質問で言ったことと一致します。M1M2NMO(M * N * N)

幸いなことに、Java ではこれを で解決できます。StringBufferこれはO(1)追加ごとに複雑であり、全体の複雑さは になりますO(n)。

このStringBuilder場合、サイズの文字列に対する呼び出しの償却後の複雑さは です。ここでのキーワードはamortizedです。に文字を追加する場合、実装で内部配列を展開する必要がある場合があります。ただし、拡張戦略は、配列のサイズを 2 倍にすることです。計算すると、平均して、バッファ内の各文字は、呼び出しのシーケンス全体で 1 回余分にコピーされることがわかります。したがって、シーケンス全体は... として機能し、たまたま、文字列の合計の長さになります。Nsb.append(s)M O(M*N)StringBuilderappendO(M*N)M*N

したがって、最終結果は正しいですが、単一の呼び出しの複雑さに関する声明はappend正しくありません。（言いたいことはわかるが、言い方がおかしい。）

最後に、Java では、バッファーをスレッドセーフにする必要がない限り、StringBuilderではなくを使用する必要があることに注意してください。StringBuffer

于 2013-03-14T04:20:02.793 に答える
2

O(n)C ++ 11が複雑な、非常に単純な構造の例として、次のようになります。

template<typename TChar>
struct StringAppender {
  std::vector<std::basic_string<TChar>> buff;
  StringAppender& operator+=( std::basic_string<TChar> v ) {
    buff.push_back(std::move(v));
    return *this;
  }
  explicit operator std::basic_string<TChar>() {
    std::basic_string<TChar> retval;
    std::size_t total = 0;
    for( auto&& s:buff )
      total+=s.size();
    retval.reserve(total+1);
    for( auto&& s:buff )
      retval += std::move(s);
    return retval;
  }
};

使用する：

StringAppender<char> append;
append += s1;
append += s2;
std::string s3 = append;

これにはO（n）が必要です。ここで、nは文字数です。

最後に、すべての弦の長さがわかっている場合は、reserve十分なスペースを空けappendて行うだけ+=で、合計でO（n）時間がかかります。しかし、私はそれが厄介であることに同意します。

std::move上記StringAppender（つまり）で使用すると、sa += std::move(s1)短い文字列以外の文字列のパフォーマンスが大幅に向上します（またはxvaluesなどで使用します）

の複雑さはわかりませんが、std::ostringstreamフォーマットされたostringstream出力をきれいに印刷する場合や、高性能が重要でない場合に使用します。つまり、それらは悪くはなく、スクリプト化/解釈/バイトコード言語を実行することさえできるかもしれませんが、急いでいる場合は、何か他のものが必要です。

いつものように、一定の要因が重要であるため、プロファイルを作成する必要があります。

この演算子への右辺値参照+も良いものかもしれませんが、これへの右辺値参照を実装しているコンパイラはほとんどありません。

于 2013-03-14T03:32:14.953 に答える