代码片段的一般含义。
给定的代码片段
x = 'wow'
x.__add__( x )
在 Python 2.x 和 Python 3.x 中具有不同的含义。
在 Python 2.x 中,字符串是默认的窄弦,每个编码单元一个字节,
对应于C++char
基于字符串。
在 Python 3.x 中,字符串是宽弦,保证代表 Unicode,
对应于C++的实际使用wchar_t
基于字符串,同样具有未指定的 2 或 4 字节
每个编码单元。
不考虑效率__add__
方法在两个 main 中的行为相同
Python版本,对应C+++
运算符为std::basic_string
(即,对于std::string
and std::wstring
),例如引用CPython 3k
文档:
object.__add__(self, other)
... 评估表达式x + y
, where 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++对应的是表达,而不是一个update.
也许很自然地认为方法名称__add__
意味着改变
字符串对象的值的更新,但相对于可观察的
Python 字符串的行为是不可变字符串。他们的价值观永远不会改变,因为
在Python代码中可以直接观察到。这与 Java 中的相同
C#,但与 C++ 的可变特性非常不同std::basic_string
字符串。
CPython 中的二次到线性时间优化。
添加了 CPython 2.4下列优化,对于窄弦 only:
形式语句中的字符串连接s = s + "abc"
and s += "abc"
现在在某些情况下执行效率更高。本次优化
不会出现在其他 Python 实现中,例如 Jython,因此您不应该
依靠它;使用join()
当您
想要有效地将大量字符串粘合在一起。 (阿明·里戈供稿。)
It may not sound like much, but where it’s applicable this optimization
reduces a sequence of concatenations from quadratic time O(n2)
to linear time O(n), in the length n of the final result.
首先,优化用更新代替串联,例如仿佛
x = x + a
x = x + b
x = x + c
或者就此而言
x = x + a + b + c
被替换为
x += a
x += b
x += c
在一般情况下,会有很多对字符串对象的引用x
指的是,并且由于Python字符串对象必须看起来是不可变的,所以第一个
更新赋值无法更改该字符串对象。因此,一般来说,它具有
创建一个全新的字符串对象,并将其(引用)分配给x
.
在此刻x
holds the only对该对象的引用。这意味着
对象可以是updated通过附加的更新分配b
,因为有
没有观察员。同样对于附加c
.
这有点像量子力学:你无法观察这个肮脏的东西
继续进行,并且当有可能有人观察时它永远不会完成
阴谋,但你可以infer从统计数据来看,这一定是在发生
您收集有关性能的信息,因为线性时间与二次时间有很大不同!
线性时间是如何实现的?嗯,跟更新buffer的策略一样
与 C++ 中一样加倍std::basic_string
可以做到,这意味着
现有的缓冲区内容只需要在每次缓冲区重新分配时复制,
而不是针对每个追加操作。这意味着总成本复制的最坏情况是最终字符串大小呈线性,
与总和相同(表示每次缓冲区加倍时的复制成本)
1 + 2 + 4 + 8 + … + N 小于 2*N。
C++ 中的线性时间字符串连接表达式。
为了在 C++ 中忠实地重现 CPython 代码片段,
应捕获操作的最终结果和表达式性质,
还应该捕捉其性能特征!
CPython 的直接翻译__add__
to C++ std::basic_string
+
失败
可靠地捕获 CPython 线性时间。 C+++
字符串连接may由编译器以与 CPython 相同的方式进行优化
优化。或者不是——这意味着有人告诉初学者
C++ 相当于 Python 线性时间运算,是二次函数
时间 – 嘿,这就是你应该使用的......
对于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.
}