☰

Unix join 命令复杂性

tag-icon • tag-icon performance join
Unix join 命令复杂性

我想知道是否有人知道 Unixjoin命令的复杂性？我假设它可能是线性的，因为两个文件都需要排序。

有人坚持认为它是对数，我对此表示怀疑。或者也许它取决于文件，并且N*log(N)当其中一个文件较小时可以是对数（或 ），而当两个文件都很大时可以接近线性？

答案1

BSDjoin实现非常容易遵循，并且似乎与文件中的行数呈线性关系。至少从 BSD 4.4 Lite2 开始，这在所有 BSD 系统中基本没有变化。下面的片段来自当前的 OpenBSD 系统，为了比较，这是 BSD 4.4 Lite2 代码的链接最初由 Keith Bostic 于 1991 年提交（替换该实用程序的早期版本）：

/*
 * 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))或。也就是说，JOIN 操作比排序更快。N*log(N)N

对于 JOIN 操作，您无法比线性操作做得更好，因为您无法跳过行（除非您有某种描述的预先计算的索引并且不包括时间复杂度中的索引）。最好的情况是没有任何行连接，在这种情况下，您需要从两个文件之一读取所有行并将它们与另一个文件的第一行进行比较。最坏的情况是所有行都连接，在这种情况下，您需要读取两个文件并在两组行之间进行成对比较（对排序文件的线性操作）。如果用户请求查看未配对的行，则您将被迫完全读取这两个文件。

如果您设法比单独的 JOIN 线性做得更差，那么您就做错了。

相关内容