重複の可能性:
単純な文字列連結
昨日、私がこれを書いているとき、誰かがSOに尋ねました
Python
x='wow'で関数を適用する文字列がある場合:addx='wow' x.add(x) 'wowwow'どうすればC++でそれを行うことができますか?
(add存在しない) を__add__(標準的な方法) に修正すると、これは深くて興味深い質問であり、微妙な低レベルの詳細、高レベルのアルゴリズムの複雑さの考慮事項、さらにはスレッド化が含まれます!簡潔な方法。
元の質問が削除される前に正しい回答を提供する機会がなかったため、元の質問 を自分のものとして再投稿し、元の質問を復活させる努力をして、これらの問題の一般的な理解を深めることができました。 失敗した。
元のタイトル「select python or C++」を…に変更しました。
それにより、質問を少し絞り込みます。
指定されたコード スニペット
x = 'wow'
x.__add__( x )
Python 2.x と Python 3.x では意味が異なります。
Python 2.x では、文字列はデフォルトで、C++ベースの文字列に対応するエンコーディング単位あたり 1 バイトのナロー文字列です。char
Python 3.x では、文字列はワイド文字列であり、Unicode を表すことが保証され、C++
wchar_tベースの文字列の実際の使用法に対応し、同様にエンコード単位ごとに未指定の 2 または 4 バイトを使用します。
効率を無視すると、__add__メソッドは両方のメイン Python バージョンで同じように動作し、C+++演算子 for std::basic_string
(つまり、 forstd::stringおよび) に対応します。たとえば、 CPython 3k ドキュメントstd::wstringを引用します。
object.__add__(self, other)
…式を評価するために、 はメソッドを持つクラスのインスタンスであり、x + y呼び出されます。x__add__()x.__add__(y)
例として、CPython 2.7 コード
x = 'wow'
y = x.__add__( x )
print y
通常は次のように記述されます
x = 'wow'
y = x + x
print y
次の C++ コードに対応します。
#include <iostream>
#include <string>
using namespace std;
int main()
{
auto const x = string( "wow" );
auto const y = x + x;
cout << y << endl;
}
元の質問に対して与えられた多くの誤った回答との主な違いは 、C++ 対応が式であり、更新ではないことです。
__add__メソッド名が文字列オブジェクトの値の変更、更新を意味すると考えるのはおそらく自然ですが、観察可能な動作に関して、Python 文字列は不変の文字列です。Python コードで直接観察できる限り、それらの値は変更されません。これは Java や C# と同じですが、C++ の変更可能なstd::basic_string文字列とは大きく異なります。
CPython 2.4 では、狭い文字列のみに対して、次の 最適化が追加されました。
s = s + "abc"との形式のステートメントでの文字列連結はs += "abc"、特定の状況でより効率的に実行されるようになりました。この最適化は、Jython などの他の Python 実装には存在しないため、依存しないでください。join()多数の文字列を効率的に接着したい場合は、文字列の方法を使用することをお勧めします。(Armin Rigo による寄稿。)
あまり聞こえないかもしれませんが、適用可能な場合、この最適化は、最終結果の長さnで、二次時間O( n 2 ) から線形時間O( n ) への一連の連結を削減します。
まず第一に、最適化は連結を更新に置き換えます。
x = x + a
x = x + b
x = x + c
またはそれについて
x = x + a + b + c
に置き換えられました
x += a
x += b
x += c
一般に、参照先の文字列オブジェクトには多くの参照がx
あり、Python 文字列オブジェクトは不変に見える必要があるため、最初の update 割り当てでその文字列オブジェクトを変更することはできません。したがって、通常、まったく新しい文字列オブジェクトを作成し、その (参照) を に割り当てる必要がありxます。
この時点で、 はそのオブジェクトへの唯一の参照をx保持しています。これは、オブザーバーがないため、を追加する update 割り当てによってオブジェクトを更新できることを意味します。の追加についても同様です。bc
これは量子力学に少し似ています。この汚いことが進行していることを観察することはできません。誰かが陰謀を観察している可能性がある場合は決して行われませんが、パフォーマンスについて収集した統計から、それが進行していたに違いないと推測できます。 、線形時間は二次時間とはまったく異なります!
線形時間はどのように達成されますか? 更新では、C++ の場合と同じバッファー倍増の戦略をstd::basic_string実行できます。つまり、既存のバッファーの内容は、追加操作ごとではなく、バッファーの再割り当てごとにコピーするだけで済みます。つまり、コピーの
総コストは、最終的な文字列サイズで最悪でも線形であり、合計 (バッファーが 2 倍になるたびにコピーするコストを表す) と同じように、1 + 2 + 4 + 8 + … + N より小さいことを意味します。 2*N。
CPython コード スニペットを C++ で忠実に再現するために、
操作の最終結果と式の性質をキャプチャする必要があります。
また、そのパフォーマンス特性をキャプチャする必要があります。
__add__CPythonを C++ に直接変換するとstd::basic_string +、CPython の線形時間を確実に取得できません。C+++文字列の連結
は、CPython の最適化と同じ方法でコンパイラによって最適化される場合があります。かどうか – つまり、Python の線形時間操作に相当する C++ は二次時間を持つものであると初心者に伝えたことを意味します – ねえ、これはあなたが使うべきものです...
パフォーマンス特性については C+++=が基本的な答えですが、これは Python コードの表現の性質を捉えていません。
自然な答えは、連結式を一連の更新に変換する線形時間 C++文字列ビルダー+=クラスです。そのため、Python コードは
from __future__ import print_function
def foo( s ):
print( s )
a = 'alpha'
b = 'beta'
c = 'charlie'
foo( a + b + c ) # Expr-like linear time string building.
おおむね対応
#include <string>
#include <sstream>
namespace my {
using std::string;
using std::ostringstream;
template< class Type >
string stringFrom( Type const& v )
{
ostringstream stream;
stream << v;
return stream.str();
}
class StringBuilder
{
private:
string s_;
template< class Type >
static string fastStringFrom( Type const& v )
{
return stringFrom( v );
}
static string const& fastStringFrom( string const& s )
{ return s; }
static char const* fastStringFrom( char const* const s )
{ return s; }
public:
template< class Type >
StringBuilder& operator<<( Type const& v )
{
s_ += fastStringFrom( v );
return *this;
}
string const& str() const { return s_; }
char const* cStr() const { return s_.c_str(); }
operator string const& () const { return str(); }
operator char const* () const { return cStr(); }
};
} // namespace my
#include <iostream>
using namespace std;
typedef my::StringBuilder S;
void foo( string const& s )
{
cout << s << endl;
}
int main()
{
string const a = "alpha";
string const b = "beta";
string const c = "charlie";
foo( S() << a << b << c ); // Expr-like linear time string building.
}