プログラミング珠玉------第五章練習問題ノート

この章では、プログラムの基本的な構築方法の足場について説明します.最高の足場は通常最も容易な足場である.いくつかのタスクでは、最も簡単な足場は、Visual Basic、Java、Tclなどの言語を使用して実装されるグラフィックユーザインタフェースから構成されます.上記の各言語について、私は30分以内にクリックコントロールと良好なグラフィック出力を持つ小さなプログラムを実現したことがあります.しかし、多くのアルゴリズムタスクにとって、より簡単な方法は、これらの強力なツールを捨て、本章で見たより簡単なコマンドライン技術を使用することであることを発見しました.コード化書きにくい関数について、最も簡単な方法は、便利な高度な擬似コードを使用してプログラムフレームワークを構築し、擬似コードを実現する言語に翻訳することであることを発見しました.テスト.足場でコンポーネントをテストするのは、大きなシステムよりも容易で徹底的です.を選択して設定できます.足場から隔離されたプログラムのデバッグは困難ですが、実際の実行環境に埋め込むと、デバッグ作業がさらに困難になります.時間を計る.実行時間が重要でない場合、線形検索は二分検索よりずっと簡単です.多くのプログラマーは、最初に実装されたときに正しいコードを得ることができます.実行時間が非常に重要であるため,より複雑な二分探索を導入したので,プログラムが予想される性能を達成できるように実験を行うべきである.
5.1
私はC/C++のプログラミングに対して悟りが多くなくて、jsの比較的に多くて、大体変数の命名、インデントなどで、実際の開発環境の中で、チームのコードの風格の統一を保証して生産性を高めることに利益があって、code reviewも便利です
5.2
js、nodeのreplもbrowerのconsoleも使いやすいですね....動的言語はやはり好きではいけません.lispのIDEも使いやすい(Racket)考え方なら再帰的です
5.3
Mutation Testing(変異試験)変異試験は、変異演算子のセットを選択し、適用される各ソースコードフラグメントに対して、それらを一度に1つずつソースプログラムに適用することによって行われる.プログラムに突然変異演算子を適用した結果を突然変異と呼ぶ.テストキットが変化を検出できる(すなわち、テストの1つが失敗した)場合、変異体は殺されたと称される.
たとえば、次のC++コードフラグメントを考慮します.
(a&&b){c=1;}else{c=0;}条件の突然変異事業者が置換&&&と|と以下の突然変異を生じる場合:
(a||b){c=1;}else{c=0;}現在、この変異体を殺すためのテストは、以下の3つの条件を満たすべきである.
テストは変異陳述に達しなければならない.テスト入力データは、変異体と元のプログラムに異なるプログラム状態を生成することによってプログラム状態に感染しなければならない.たとえば、1つのテストでは、a=1およびb=0になります.不正なプログラム状態(’c’の値)は、プログラムの出力に伝播し、テストによって検査しなければならない.これらの条件を総称してRIPモデルと呼ぶ.[3]
弱い変異検出(または弱い変異被覆)は、第1および第2の条件のみを満たすことが要求される.強い突然変異試験はすべての3つの条件を満たすことを要求した.強力な突然変異は、テストキットが本当に問題を発見できることを保証するため、より強力です.弱い変異はコードオーバーライド法と密接に関連している.試験キットが強い変異試験ではなく弱い変異試験を満たすことを保証するために、より少ない計算能力が必要である.
しかし、この変異体を殺す試験例が見つからない場合がある.結果プログラムは動作的に元のプログラムと同じである.この変異体を等価変異体と呼ぶ.
等価変異体検出は実際に変異検出を用いる最大の障害の一つである.小型プログラムでも,変異体が等価かどうかを調べるには高い努力が必要である.[13]等価な突然変異問題を克服するための多様な方法の系統的文献の総括([14]から提案された)は17種類の関連技術(22編の文章の中で)と3種類の技術を確定した:検出(DEM);提案(SEM);等価変異体生成(AEMG)を回避する.実験は一般的な高次変異とJudyDiffOp戦略が等価変異問題に有望な方法を提供することを示した.
5.4
ここではコードを呼び出すときに防御的な断言をします.のはっきり言ってユーザー入力を信じず、モジュールを書いた皆さんもやったに違いありません.
5.5
バブル比較シーケンスとインデックスが逆であればすぐに異常を放出し,この平均オーバーヘッドはn/2であった.
5.6
どのようなテストを見るには、フロントエンドのテストで私があまり熟知していない技術を応用するには、いくつかのdemoテストを行い、あまり問題がないことを確認してから引用します.テスト駆動開発はプロジェクト開発の過程で比較的妥当な方法であるべきです.
5.7
私が考えることができるのは空間の局所性ですか?プリフェッチ?違うkernelを見ましょう....この問題は少し深く掘って、しばらく穴を占めます.
5.8
前端を书く时足場が本当に多すぎます....webpack,gulp,そして最近のpercel....メカニズムを见ていないで、私は前端のGUIテストに対してとても烦わして、今までやはり手动でテスト用例を书いて肉眼でテストして、後端はまだテストのフレームワークを走ることができて、また良い方法の友达に教えてもらいます~
5.9
ソースコード

#include  
#include   
#include   

#define MAXN 1000000  

typedef int DataType;  

DataType x[MAXN];  
int n;  

/* Scaffolding */  

int i = -999999;  
#define assert(v) { if ((v) == 0) printf("  binarysearch bug %d %d
", i, n); }  

/* Alg 1: From Programming Pearls, Column 4: raw transliteration */  

int binarysearch1(DataType t)  
{   int l, u, m;  
    l = 0;  
    u = n-1;  
    for (;;) {  
        if (l > u)  
            return -1;  
        m = (l + u) / 2;  
        if (x[m] < t)  
            l = m+1;  
        else if (x[m] == t)  
            return m;  
        else /* x[m] > t */  
            u = m-1;  
    }  
}  

/* Alg 2: Make binarysearch1 more c-ish */  

int binarysearch2(DataType t)  
{   int l, u, m;  
    l = 0;  
    u = n-1;  
    while (l <= u) {  
        m = (l + u) / 2;  
        if (x[m] < t)  
            l = m+1;  
        else if (x[m] == t)  
            return m;  
        else /* x[m] > t */  
            u = m-1;  
    }  
    return -1;  
}  

/* Alg 3: From PP, Col 8 */  

int binarysearch3(DataType t)  
{   int l, u, m;  
    l = -1;  
    u = n;  
    while (l+1 != u) {  
        m = (l + u) / 2;  
        if (x[m] < t)  
            l = m;  
        else  
            u = m;  
    }  
    if (u >= n || x[u] != t)  
        return -1;  
    return u;  
}  

/* Alg 4: From PP, Col 9 */  

int binarysearch4(DataType t)  
{   int l, p;  
    if (n != 1000)  
        return binarysearch3(t);  
    l = -1;  
    if (x[511]   < t) l = 1000 - 512;  
    if (x[l+256] < t) l += 256;  
    if (x[l+128] < t) l += 128;  
    if (x[l+64 ] < t) l += 64;  
    if (x[l+32 ] < t) l += 32;  
    if (x[l+16 ] < t) l += 16;  
    if (x[l+8  ] < t) l += 8;  
    if (x[l+4  ] < t) l += 4;  
    if (x[l+2  ] < t) l += 2;  
    if (x[l+1  ] < t) l += 1;  
    p = l+1;  
    if (p >= n || x[p] != t)  
        return -1;  
    return p;  
}  

/* Alg 9: Buggy, from Programming Pearls, Column 5 */  

int sorted()  
{   int i;  
    for (i = 0; i < n-1; i++)  
        if (x[i] > x[i+1])  
            return 0;  
    return 1;  
}  

int binarysearch9(DataType t)  
{   int l, u, m;  
/* int oldsize, size = n+1; */  
    l = 0;  
    u = n-1;  
    while (l <= u) {  
/* oldsize = size;  
size = u - l +1;  
assert(size < oldsize); */  
        m = (l + u) / 2;  
/* printf("  %d %d %d
", l, m, u); */  
        if (x[m] < t)  
            l = m;  
        else if (x[m] > t)  
            u = m;  
        else {  
            /* assert(x[m] == t); */  
            return m;  
        }  
    }  
    /* assert(x[l] > t && x[u] < t); */  
    return -1;  
}  

/* Alg 21: Simple sequential search */  

int seqsearch1(DataType t)  
{   int i;  
    for (i = 0; i < n; i++)  
        if (x[i] == t)  
            return i;  
    return -1;  
}  

/* Alg 22: Faster sequential search: Sentinel */  

int seqsearch2(DataType t)  
{   int i;  
    DataType hold = x[n];  
    x[n] = t;  
    for (i = 0; ; i++)  
        if (x[i] == t)  
            break;  
    x[n] = hold;  
    if (i == n)  
        return -1;  
    else  
        return i;  
}  

/* Alg 23: Faster sequential search: loop unrolling */  

int seqsearch3(DataType t)  
{   int i;  
    DataType hold = x[n];  
    x[n] = t;  
    for (i = 0; ; i+=8) {  
        if (x[i] == t)   {          break; }  
        if (x[i+1] == t) { i += 1; break; }  
        if (x[i+2] == t) { i += 2; break; }  
        if (x[i+3] == t) { i += 3; break; }  
        if (x[i+4] == t) { i += 4; break; }  
        if (x[i+5] == t) { i += 5; break; }  
        if (x[i+6] == t) { i += 6; break; }  
        if (x[i+7] == t) { i += 7; break; }  
    }  
    x[n] = hold;  
    if (i == n)  
        return -1;  
    else  
        return i;  
}  


/* Scaffolding to probe one algorithm */  

void probe1()  
{   int i;  
    DataType t;  
    while (scanf("%d %d", &n, &t) != EOF) {  
        for (i = 0; i < n; i++)  
            x[i] = 10*i;  
        printf(" %d
", binarysearch9(t));  
    }  
}  


/* Torture test one algorithm */  

\#define s seqsearch3  
void test(int maxn)  
{   int i;  
    for (n = 0; n <= maxn; n++) {  
        printf("n=%d
", n);  
        /* distinct elements (plus one at top) */  
        for (i = 0; i <= n; i++)  
            x[i] = 10*i;  
        for (i = 0; i < n; i++) {  
            assert(s(10*i)     ==  i);  
            assert(s(10*i - 5) == -1);  
        }  
        assert(s(10*n - 5) == -1);  
        assert(s(10*n)     == -1);  
        /* equal elements */  
        for (i = 0; i < n; i++)  
            x[i] = 10;  
        if (n == 0) {  
            assert(s(10) == -1);  
        } else {  
            assert(0 <= s(10) && s(10) < n);  
        }  
        assert(s(5) == -1);  
        assert(s(15) == -1);  
    }  
}  

/* Timing */  

int p[MAXN];  

void scramble(int n)  
{   int i, j;  
    DataType t;  
    for (i = n-1; i > 0; i--) {  
        j = (RAND_MAX*rand() + rand()) % (i + 1);  
        t = p[i]; p[i] = p[j]; p[j] = t;  
    }  
}  

void timedriver()  
{   int i, algnum, numtests, test, start, clicks;  
    while (scanf("%d %d %d", &algnum, &n, &numtests) != EOF) {  
        for (i = 0; i < n; i++)  
            x[i] = i;  
        for (i = 0; i < n; i++)  
            p[i] = i;  
        scramble(n);  
        start = clock();  
        for (test = 0; test < numtests; test++) {  
            for (i = 0; i < n; i++) {  
                switch (algnum) {  
                case 1:  assert(binarysearch1(p[i]) == p[i]); break;  
                case 2:  assert(binarysearch2(p[i]) == p[i]); break;  
                case 3:  assert(binarysearch3(p[i]) == p[i]); break;  
                case 4:  assert(binarysearch4(p[i]) == p[i]); break;  
                case 9:  assert(binarysearch9(p[i]) == p[i]); break;  
                case 21: assert(seqsearch1(p[i]) == p[i]); break;  
                case 22: assert(seqsearch2(p[i]) == p[i]); break;  
                case 23: assert(seqsearch3(p[i]) == p[i]); break;  
                }  
            }  
        }  
        clicks = clock() - start;  
        printf("%d\t%d\t%d\t%d\t%g
",  
            algnum, n, numtests, clicks,  
            1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests));   
    }  
}  

/* Main */  

int main()  
{   /* probe1(); */  
    /* test(25); */  
    timedriver();  
    return 0;  
}  

分析:binarysearch 1と2は先に値を割り当てた後に値を与える違いにほかならない.3は次第に上界に近づいてから検索成功判定を反復に抽出する.4は主に最初のif 1000,9境界でエラーが発生し、6 Sentinelによる制御フローの減少、7 loop unrolling(これは命令レベルの最適化を指す)