主页 / unix / 问题 / 441369
Accepted
Ben
Asked: 2018-05-03 09:52:45 +0800 CST

Unix 连接命令复杂度

  • 772

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

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

performance join

1 个回答

  1. Best Answer

    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 做的比线性还差，那么您做错了什么。

    • 8

相关问题