Linux 排序与编程

Question

我想了解为什么我的软件 (golang) 比 linux sort 命令慢 350 倍？我正在对大约 13.000.000 行(4 - 20 字节长)的 UTF-8 文本文件进行排序。

我函数中的代码示例(如果 checkDupl false 附加到 newArray):

func checkDupl(in []byte) bool {
    for i := range newArray {
        if bytes.Equal(in, newArray[i]) {
            return true
        }
    }
    return false
}

此代码一夜之间完成了大约 25%。

此代码在 8 分钟内完成:

  497  export LC_ALL=C
  498  time sort -us -o file_unique.txt file.txt

Answer 1

sort -u 通过对输入进行排序，然后遍历并打印出每个唯一元素来工作。它只需记住它打印​​的最后一个东西，并在它发生变化时打印一个新项目，就可以做到这一点。

您的代码似乎是对输出数组的线性搜索，所以我假设它是更广泛的算法的一部分，如下所示:

for each X in input:
    if not checkDupl(X) then:
        append X to newArray

这意味着您的 checkDupl 函数对输入中的每个项目运行一次，然后 checkDupl 中的循环对输出中的每个项目运行一次。在最坏的情况下，整个列表是唯一的，所以 checkDupl 第一次查看一个项目，然后是两个，然后是三个，然后是四个，...。这个序列加起来为 n(n + 1)/2，或 0.5n^2 + 0.5n。 13,000,000 的平方支配了另一项的 650 万，因此我们称该算法为“二次时间”或 O(n^2)。这是最坏的情况，也是一般情况(但最好的情况，13,000,000 条相同的行，将相当快)。

有许多传统的排序算法可以在 O(n log n) 时间内运行。 POSIX does not require sort to use one of those ，但所有明智的实现都会这样做。 log(n) 项增长非常缓慢，因此这将比 n^2 小得多。打印是线性时间，O(n)，同上可以忽略。

---

除了最微不足道的情况，除了最愚蠢的 sort 之外，您的程序将比 sort 运行时间长得多。对于您的 1300 万件商品，差异可能是数十万倍(忽略与程序有关的所有其他内容)。

您可以实现排序算法并复制sort 的方法，或者使用库函数。您还可以使用更适合检查唯一性的数据结构，如哈希表，而不是需要线性搜索的数组。最有可能的是，使用库函数比尝试自己滚动所有内容更好。