☰

Unix 排序键导致性能问题

tag-icon • tag-icon unix sorting
Unix 排序键导致性能问题

我的数据：

  • 这是一个 71 MB 的文件，包含 150 万行。
  • 它有 6 个字段
  • 所有六个字段组合起来形成一个唯一的键 - 所以这就是我需要进行排序的。

排序语句：

sort -t ',' -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 -k6,6 -o output.csv input.csv

问题：

  • 如果我不用键进行排序，则需要 30 秒。
  • 如果我按键排序，则需要 660 秒。
  • 我需要使用键进行排序，以保持通用性，并使其对其他具有非键字段的文件同样有用。30 秒的时间还行，但 660 秒太长了。

使用 unix 时间的更多详细信息：

  • 排序输入.csv -o 输出.csv = 28 秒
  • sort -t'，'-k1 输入.csv -o 输出.csv = 28 秒
  • sort -t'，'-k1,1输入.csv -o输出.csv = 64 秒
  • sort -t'，'-k1,1 -k2,2输入.csv -o输出.csv = 194 秒
  • sort -t'，'-k1,1 -k2,2 -k3,3 输入.csv -o 输出.csv = 328 秒
  • sort -t'，'-k1,1 -k2,2 -k3,3 -k4,4 输入.csv -o 输出.csv = 483 秒
  • sort -t'，'-k1,1 -k2,2 -k3,3 -k4,4 -k5,5输入.csv -o输出.csv = 561 秒
  • sort -t'，'-k1,1 -k2,2 -k3,3 -k4,4 -k5,5 -k6,6输入.csv -o输出.csv = 660 秒

理论上我可以将临时目录移动到 SSD，和/或将文件分成 4 个部分，分别对它们进行排序（并行），然后合并结果等。但我希望得到更简单的东西，因为看起来排序只是选择了一个糟糕的算法。

有什么建议么？

使用缓冲区大小测试改进：

  • 使用 2 个密钥后，我在 8、20、24 MB 时获得了 5% 的提升，在 16MB 时获得了 8% 的最佳性能提升，但在 128MB 时性能下降了 6%
  • 使用 6 个密钥时，我获得了 8、20、24 MB 5% 的提升，而使用 16MB 时最佳性能获得了 9% 的提升。

使用字典顺序测试改进（每次仅运行 1 次）：

  • sort -d --buffer-size=8M -t ',' -k1,1 -k2,2 input.csv -o output.csv = 235 秒（差 21%）
  • sort -d --buffer-size=8M -t ',' -k1,1 -k2,2 input.csv -o ouput.csv = 232 秒（差 21%）
  • 结论：这会减慢进程，这是有道理的，但没用

使用 SSD 上的不同文件系统进行测试 - 我现在无法在此服务器上执行此操作。

使用代码测试合并相邻的键：

def consolidate_keys(key_fields, key_types):
""" Inputs:
         - key_fields - a list of numbers in quotes: ['1','2','3']
         - key_types - a list of types of the key_fields: ['integer','string','integer']
    Outputs:
         - key_fields - a consolidated list:  ['1,2','3']
         - key_types - a list of types of the consolidated list: ['string','integer']
"""
assert(len(key_fields) == len(key_types))

def get_min(val):
    vals = val.split(',')
    assert(len(vals) <= 2)
    return vals[0]

def get_max(val):
    vals = val.split(',')
    assert(len(vals) <= 2)
    return vals[len(vals)-1]

i = 0
while True:
    try:
        if ( (int(get_max(key_fields[i])) + 1) == int(key_fields[i+1])
        and  key_types[i] == key_types[i+1]):
                key_fields[i] = '%s,%s' % (get_min(key_fields[i]), key_fields[i+1])
                key_types[i]  = key_types[i]
                key_fields.pop(i+1)
                key_types.pop(i+1)
                continue
        i = i+1
    except IndexError:
        break  # last entry

return key_fields, key_types

虽然这段代码只是一种解决方法，仅适用于我有一组连续的键的情况 - 但在我最坏的情况下，它可以将代码速度提高 95％。

答案1

我不知道它的sort内部工作原理，也没有 71 MB 的.csv文件可以测试它，但您可以尝试以下几件事：

  • --buffer-size将（ ）设置-S为足够大的值以避免多次从硬盘读取。

    从...开始-S=1G，然后逐步向下。

  • 逐个排除键以查看是否有特定的键导致问题（例如整数）。

    例子：

    • -k1,1 -k2,2 -k3,3 -k4,4 -k5,5

    • -k1,1 -k2,2 -k3,3 -k4,4 -k6,6

  • 除非这对于整数来说是不可接受的，否则设置--dictionary-order（-d）开关。

答案2

指定多个键需要先按第一个键对数据进行排序，然后按第二个键对具有相同第一个键的项目进行排序，依此类推。这会在 RAM 中移动大量数据。如果任何数据被分页，算法将从受内存访问时间（以纳秒为单位）限制变为受磁盘访问时间（以毫秒为单位）限制。

答案3

我正好遇到了这个问题，在快速浏览了 sort.c 源代码后，我注意到，如果键不是连续地位于字符串的开头，则在字符串中搜索键的部分是纯字符串搜索（直到分隔符）。考虑到排序是一个 (log n) 操作，在比较两行时，这种在一行中搜索键的方式可能会重复多次，每次将一行与另一行进行比较。

因此，我结合使用了 awk（连续添加键）、sort（在前 x 个字段上）和 cut（删除添加的键）来连续添加排序键，并在作业完成后删除它们。对于我的用例来说，效率提高了 3 倍。

相关内容