More Effective C++17:怠惰計算法を考える

18615 ワード

効率の観点から見ると、最適な計算は計算しないことだ.怠惰計算法は各種の応用分野に広く適用され,4つの部分から述べた.
参照数

class String { ... };
String s1 = "Hello";
String s2 = s1; //    string

通常stringコピーコンストラクション関数は、s 2をs 1によって初期化した後、s 1とs 2に独自の「Hello」コピーがある.このコピーコンストラクション関数は、s 1値のコピーを作成し、s 2に値を割り当てるため、newオペレータでスタックメモリを割り当てる必要があるため、コストがかかります.
strcpy関数を呼び出してs 1内のデータをs 2にコピーする必要があるが、この場合のs 2は、s 2が使用されていないため、この値のコピーを必要としない.
怠け者は仕事を少なくすることだ.s 2にs 1のコピーを割り当てるのではなく、s 2とs 1に値を共有させるべきである.誰が何を共有しているかを知るために記録するだけで、newとコピー文字を呼び出すコストを節約できます.実際にs 1とs 2はデータ構造を共有しており、これはclientにとって透明であり、以下の例ではデータを読むだけなので、これは差はありません.

cout << s1; //   s1    
cout << s1 + s2; //   s1   s2

これまたはそのstringの値が変更された場合にのみ、同じ値を共有する方法が異なります.2つとも修正されるのではなく、stringの値を1つだけ修正することが重要です.たとえば、この文は次のようになります.

s2.convertToUpperCase();

このように文を実行するために、stringのconvertToUpperCase関数はs 2値のコピーを作成し、修正前にこのプライベートな値をs 2に割り当てるべきである.convertToUpperCaseの内部では、s 2(共有)値のコピーを作成してs 2を自分で使用する必要があります.一方,s 2を修正しなければ,独自の値のコピーを作成する必要はない.プログラムが終了するまで共有値を維持します.もし私たちが幸運であれば、s 2は修正されません.この場合、私たちは永遠に独立した値を与えるのに苦労しません.
まとめ:本当に必要でない限り、何のコピーも作成しません.私たちは怠け者であるべきで、可能な限り他の値を共有して使用します.いくつかの応用分野では、よくそうすることができます.
読み取りと書き込みの区別
このようなコードを考慮します.

String s = "Homer's Iliad";//         string
cout << s[3]; //    operator[]    s[3] 
s[3] = 'x'; //    operator[]    s[3]

まずoperator[]を呼び出してstringの一部の値を読み出すが、この関数を2回目に呼び出すのは書き込み操作を完了するためである.読み出し参照カウントstringは容易であるが、このstringを書き込むには書き込み前にstring値に新しいコピーを作成する必要があるため、読み出し呼び出しと書き込み呼び出しを区別することができる.
私たちは困難に陥った.このようにするためには、operator[]において異なる措置をとる必要がある.呼び出しoperator[]が読み出し操作か書き込み操作かを判断すれば?残酷な事実は私たちが判断できないことだ.
怠惰計算法と条項30のproxy classを使用することで、正しい答えが判断できるまで、読み取り操作か書き込み操作かの決定を遅らせることができます.
怠惰抽出
プログラムが多くのフィールドを含む大規模なオブジェクトを使用しているとします.これらのオブジェクトの生存期間はプログラムの実行期間を超えているため、データベースに格納する必要があります.各ペアには、データベースからオブジェクトを再取得するための一意のオブジェクト識別子があります.

class LargeObject  //       
{
public: 
	LargeObject(ObjectID id); //          
	const string& field1() const; // field 1    
	int field2() const; // field 2    
	double field3() const; // ... 
	const string& field4() const; 
	const string& field5() const;
	...
};

次に、ディスクからLargeObjectをリカバリするコストを考えてみましょう.

void restoreAndProcessObject(ObjectID id) 
{ 
	LargeObject object(id); //      
	... 
}

LargeObjectオブジェクトインスタンスが大きいため、このようなオブジェクトのためにすべてのデータを取得すると、特にリモート・データベースからデータを取得し、ネットワークを介してデータを送信する場合、データベースの操作のオーバーヘッドが非常に大きくなります.この場合、すべてのデータを読む必要はありません.例:

void restoreAndProcessObject(ObjectID id) 
{ 
	LargeObject object(id); 
	if (object.field2() == 0) 
	{ 
		cout << "Object " << id << ": null field2.
"; 
	} 
}

ここではfiled2の値しか必要ないので、他のフィールドを取得するための努力は無駄です.LargeObjectオブジェクトが確立されると、ディスクからすべてのデータが読み込まれず、怠惰法がこの問題を解決します.ただし、この場合に作成されるのは1つのオブジェクト「シェル」だけで、データが必要な場合、このデータはデータベースから取り戻されます.この「demand-paged」オブジェクトの初期化の実現方法は、次のとおりです.

class LargeObject 
{ 
public: 
	LargeObject(ObjectID id); 
	const string& field1() const; 
	int field2() const; 
	double field3() const; 
	const string& field4() const; 
	... 
private: 
	ObjectID oid; 
	mutable string *field1Value; //       
	mutable int *field2Value; // "mutable"    
	mutable double *field3Value; 
	mutable string *field4Value; 
	... 
};
LargeObject::LargeObject(ObjectID id) : oid(id), field1Value(0), field2Value(0), field3Value(0), ... 
{}
const string& LargeObject::field1() const 
{ 
	if (field1Value == 0) 
	{ 
		       filed 1     ，  
		field1Value      ; 
	} 
	return *field1Value; 
}

オブジェクト内の各フィールドは、データを指すポインタで表され、LargeObjectコンストラクタは各ポインタを空に初期化します.これらの空のポインタは、フィールドがデータベースから数値を読み込んでいないことを示します.各LargeObjectメンバー関数は、フィールドポインタが指すデータにアクセスする前に、フィールドポインタのステータスをチェックする必要があります.ポインタが空の場合は、データを操作する前にデータベースから対応するデータを読み込む必要があります.
怠惰な抽出を実現する場合、constメンバー関数、例えばfield1などの実際のデータを指すために、任意のメンバー関数に空のポインタを初期化する必要があるという問題に直面します.しかし、constメンバー関数でデータを変更しようとすると、コンパイラに問題が発生します.最良の方法は、フィールドポインタがmutableであることを宣言することであり、これは、constメンバー関数でさえ、任意の関数で変更できることを示しています.
さらにLargeObjectのポインタを見ると、これらのポインタを空に初期化し、使用するたびにテストしなければなりません.これはうんざりし、エラーが発生しやすいです.幸いなことに、スマートポインタを使うと、このような苦差を自動的に達成することができます.
怠惰な式の計算
このようなコードを考慮します.

template<class T> 
class Matrix { ... }; 
Matrix<int> m1(1000, 1000); //    1000 ＊ 1000     
Matrix<int> m2(1000, 1000);
...
Matrix<int> m3 = m1 + m2; // m1＋m2

通常operatorのそれはm 1とm 2の和を計算して返します.この計算量はかなり大きく(1000000回の加算)、もちろんメモリも割り当てられてこれらの値を格納します.
このように仕事をするのは多すぎるので、やはりやらないでください.m3の値がm1とm2の和であり、それらの間が加算動作であることを示すデータ構造を確立すべきである.このデータ構造の構築は、enumとm1の加算よりもずっと速く、メモリを大幅に節約できることは明らかです.プログラムの後の部分を考慮して、m 3を使用する前に、コードは以下のように実行されます.

Matrix<int> m4(1000, 1000);
... //    m4     
m3 = m4 * m1;

m 3はm 1とm 2の和(したがって計算のコストを節約)であることを忘れることができ、ここではm 3はm 4とm 1の演算の結果であることを覚えなければならない.
良いプログラマは不要な計算を行わないが,メンテナンス中にプログラマがプログラムの経路を変更し,以前は有用な計算が機能しなくなったことがよくある.使用前に計算されたオブジェクトを定義することで、このような状況が発生する可能性を減らすことができます(Effective C++条項32を参照).しかし、この問題はたまに発生します.......より一般的な応用分野は、計算結果の一部だけが必要な場合です.例えば、m2の値がm3およびm1の和であることを初期化し、m2をこのように使用すると仮定する.

cout << m3[4]; //    m3

明らかに、私たちはこれ以上怠けてはいけない.m 3の4行目の値を計算しなければならない.しかし、m 3の4行目以外の結果を計算する必要はありません.m 3の残りの部分は、それらの値が確実に必要になるまで計算されていない状態を維持します.......公正に言えば、怠け者は失敗することもある.このようにm 3を使用すると、

cout << m3; //    m3

すべてが終わったので、m 3のすべての数値を計算しなければなりません.同様に、m 3に依存するマトリクスのいずれかを変更する場合は、すぐに計算する必要があります.

m3 = m1 + m2; //    m3   m1   m2   
m1 = m4; //    m3   m2   m1      ！

ここでは、m 1に値を付与した後、m 3が変更されないようにする措置を取らなければならない.m3賦値オペレータでは、m 1を変更する前にm 3の値をキャプチャすることができ、またはm 1の古い値にm 3をこのコピー計算に依存させるコピーを作成することができ、m 1が賦値された後もm 3の値が変わらないようにする措置を取らなければならない.マトリクスを変更する可能性のある他の関数は、同じ方法で処理する必要があります.
まとめ
怠惰な計算は、不要なオブジェクトのコピーを回避し、operator[]を使用して読み取り操作を区別することで、不要なデータベースの読み取り操作を回避し、不要なデジタル操作を回避するために、さまざまな分野で役立ちます.
しかし、それはいつも役に立つわけではありません.もしあなたの両親がいつもあなたの部屋をチェックしに来たら、部屋の整理を遅らせても仕事の量を減らすことはできません.
実際には、計算が重要であれば、怠惰な計算は速度を遅くし、メモリの使用を増やす可能性があります.すべての計算を行う以外に、データ構造を維持して、怠惰な計算をできるだけ最初の時間に実行する必要があります.

ショッピングカートの実現(三)

djangoはなぜuwsgiとnginxの協力が必要なのか