番兵の価値

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータプログラミングでは番兵値(フラグ値トリップ値不正値信号値、またはダミーデータとも呼ばれます[1]は、その存在を条件として使用するアルゴリズムのコンテキストでは特別なです。通常、ループまたは再帰的アルゴリズムでの終了。

番兵値は、帯域外データ(明示的なサイズ表示など)が提供されていない場合にデータの終わりを検出できるようにする帯域内データの形式です。値は、すべての正当なデータ値とは異なることが保証されるように選択する必要があります。そうしないと、そのような値の存在がデータの終わりを時期尚早に示すためです(半述語の問題)。番兵の値は、物理的な番兵として使用されるジョークのため、「カイロの象」と呼ばれることもあります。安全な言語では、ほとんどの番兵の値をオプションタイプに置き換えることができます。これにより、例外的なケースの明示的な処理が強制されます。

一般的な番兵の値とその使用法の例:

バリアント

わずかに異なる状況で使用される関連する方法は、データの最後に特定の値を配置して、処理ループでの終了の明示的なテストの必要性を回避することです。これは、値がすでにテストによる終了をトリガーするためです。他の理由で存在します。上記の使用法とは異なり、これはデータが自然に保存または処理される方法ではなく、終了をチェックする単純なアルゴリズムと比較して最適化です。これは通常、検索で使用されます。[2] [3]

たとえば、並べ替えられていないリストで特定の値を検索すると、すべての要素がこの値と比較され、同等性が見つかるとループが終了します。ただし、値が存在しない場合に対処するには、各ステップの後で、検索が失敗したかどうかもテストする必要があります。検索された値をリストの最後に追加することにより、検索の失敗は不可能になり、内部ループで明示的な終了テストは必要ありませんその後も、真の一致が見つかったかどうかを判断する必要がありますが、このテストは、各反復ではなく1回だけ実行する必要があります。[4] クヌースは、データの最後に配置された値を、番兵ではなく ダミー値と呼びます。

配列

たとえば、Cの配列で値を検索する場合、簡単な実装は次のようになります。「結果なし」を返すという半述語の問題を解決するために負の数(無効なインデックス)を使用していることに注意してください。

int find int arr []、size_t len int val       
{{
    for int i = 0 ; i < len ; i ++         
        if arr [ i ] == val    
            私を返す; 
    -1を返します; //見つかりません}  

ただし、これはループの各反復で2つのテストを実行します。値が見つかったかどうか、および配列の最後に到達したかどうかです。この後者のテストは、番兵値を使用することによって回避されるものです。配列を1つの要素で拡張できると仮定すると(メモリの割り当てやクリーンアップなし。これは、以下のようにリンクリストの場合により現実的です)、次のように書き直すことができます。

int find int arr []、size_t len int val       
{{
    int i ; 

    arr [ len ] = val ; // i = 0 ;; i ++ )の番兵値を追加します   
        
        if arr [ i ] == val    
            休憩;
    if i < len    
            私を返す; 
    そうしないと
            -1を返します; //見つかりません}  

のテストi < lenはまだ存在しますが、ループの外に移動されました。ループの外には、(値の)テストが1つだけ含まれており、番兵の値のために終了することが保証されています。番兵の値がヒットした場合、終了時に1つのチェックがあり、これが各反復のテストに置き換わります。

配列の最後の要素 を一時的に番兵に置き換えて処理することもできます。特に、次の要素に到達した場合はそうです。

int find int arr []、size_t len int val       
{{
    int last ; 

    if len == 0    
        -1を返します; 
    last = arr [ len - 1 ];    
    arr [ len --1 ] = val ; _ // (int i = 0 ;; i ++ )の番兵値追加します     
         
        if arr [ i ] == val    
            休憩;
    arr [ len -- 1 ] =最後;    
    if arr [ i ] == val    
            私を返す; 
    そうしないと
            -1を返します; //見つかりません}  

も参照してください

参照

  1. ^ クヌース、ドナルド(1973)。The Art of Computer Programming、Volume 1:Fundamental Algorithms(second edition)アディソン-ウェスリーpp。213–214  、またp631. ISBN  0-201-03809-9
  2. ^ メールホルン、カート; サンダース、ピーター(2008)。アルゴリズムとデータ構造:配列とリンクリストによるシーケンスの表現に関する基本的なツールボックス3(PDF)スプリンガー。ISBN  978-3-540-77977-3p。63
  3. ^ McConnell、Steve(2004)。コードコンプリート(第2版)。レドモンド:マイクロソフトプレス。p。 621ISBN 0-7356-1967-0
  4. ^ クヌース、ドナルド(1973)。The Art of Computer Programming、第3巻:並べ替えと検索アディソン-ウェスリーp。395. ISBN  0-201-03803-X