☰

Unix 結合コマンドの複雑さ

tag-icon • tag-icon performance join
Unix 結合コマンドの複雑さ

joinUnixコマンドの複雑さを知っている人がいるかどうか疑問に思います。両方のファイルを並べ替える必要があるため、線形である可能性があるとします。

一部の人々はそれが代数的であると主張していますが、私はそれが疑わしいです。それともファイルによって異なり、N*log(N)ファイルの1つが小さい場合はログ（または）になり、両方のファイルが大きい場合は線形に近づくことができますか？

答え1

BSDjoinの実装は従うのがとても簡単で、ファイルの行数に応じて線形に拡張されるようです。これは、少なくともBSD 4.4 Lite2以降、すべてのBSDシステムで本質的に変更されていません。次のスニペットは現在のOpenBSDシステム、比較しようと、以下はBSD 4.4 Lite2コードへのリンクです。もともと1991年にKeith Bosticが提出したものです（このユーティリティの以前のバージョンを置き換えます）。

/*
 * We try to let the files have the same field value, advancing
 * whoever falls behind and always advancing the file(s) we output
 * from.
*/
while (F1->setcnt && F2->setcnt) {
        cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
        if (cval == 0) {
                /* Oh joy, oh rapture, oh beauty divine! */
                if (joinout)
                        joinlines(F1, F2);
                slurp(F1);
                slurp(F2);
        }
        else {
                if (F1->unpair
                && (cval < 0 || F2->set->cfieldc == F2->setusedc -1)) {
                        joinlines(F1, NULL);
                        slurp(F1);
                }
                else if (cval < 0)
                        /* File 1 takes the lead... */
                        slurp(F1);
                if (F2->unpair
                && (cval > 0 || F1->set->cfieldc == F1->setusedc -1)) {
                        joinlines(F2, NULL);
                        slurp(F2);
                }
                else if (cval > 0)
                        /* File 2 takes the lead... */
                        slurp(F2);
        }
}

私が探していますjoinGNU coreutilsのコードしかし、GNUコードには私ができることが多すぎます。推測する、コードのコメントによると、ほぼ同じタイプのアルゴリズムを実装しています。

/* Keep reading lines from file1 as long as they continue to
   match the current line from file2.  */

[...]

/* Keep reading lines from file2 as long as they continue to
   match the current line from file1.  */

[...]

ソートを考慮してソートアルゴリズムを想定すると、値が大きいほど、N*log(N)全体の時間複雑度はN*(1 + log(N))orになります。つまり、JOIN 操作がソートよりも高速です。N*log(N)N

JOIN操作を使用すると、行をスキップできないため、線形操作よりも優れた操作を実行することはできません（一部の説明には事前計算された索引があり、時間の複雑さに索引を含めない場合）。最良のケースは、接続された行がないことです。この場合、両方のファイルのいずれかからすべての行を読み、他のファイルの最初の行と比較する必要があります。最悪の場合は、すべての行が接続されることです。この場合、両方のファイルを読み取り、2つの行セット間でペアごとの比較を実行する必要があります（ソートされたファイルの線形演算）。ユーザーがペアのない行を表示するように要求した場合は、両方のファイルを完全に読み取る必要があります。

線形JOINだけを使用するよりも悪いことをしたい場合は、間違ったことをします。

関連情報