Unix 連接命令複雜度

我想知道是否有人知道 Unixjoin命令的複雜性？我曾假設它可能是線性的，因為兩個文件都需要排序。

有人堅持對我說這是對數，我對此表示懷疑。或者它可能取決於文件​​，並且N*log(N)當其中一個文件很小時可以是對數（或）並且當兩個文件都很大時接近線性？

BSDjoin實現很容易遵循，並且似乎與文件中的行數呈線性關係。至少從 BSD 4.4 Lite2 開始，這在所有 BSD 系統中幾乎沒有變化。下面的程式碼片段來自目前的 OpenBSD 系統，作為比較，這是一個指向最初由 Keith Bostic 在 1991 年送出的 BSD 4.4 Lite2 程式碼的連結（替換了該實用程序的早期版本）：

/*
* 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);
       }
}

我查看了 GNU coreutils中的程式碼join，但 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))， 或N*log(N)對於較大的N值。即 JOIN 操作比排序快。

對於 JOIN 操作，你不能比線性做得更好，因為你不能跳過行（除非你有一些描述的預先計算的索引並且不包括時間複雜度中的索引）。最好的情況是沒有任何行加入，在這種情況下，您需要從兩個文件中的一個讀取所有行並將這些行與另一個文件的第一行進行比較。最壞的情況是所有行都連接，在這種情況下，您需要讀取兩個文件並在兩組行之間進行成對比較（對已排序文件的線性操作）。如果使用者請求查看未配對的行，那麼您將被迫完全閱讀這兩個文件。

如果您僅對 JOIN 做的比線性還差，那麼您做錯了什麼。

引用自：https://unix.stackexchange.com/questions/441369