6

我基本上想要相当于

... | sort -arg1 -arg2 -... | head -n $k

但是，我的理解是排序将在整个输入上进行 O( n log n )。就我而言，我正在处理大量数据，因此运行时间对我来说很重要——而且我有一个习惯，就是用排序的临时文件来溢出我的 tmp/ 文件夹。

我宁愿让它使用例如堆来运行 O( n log k )，这可能会更快，并且也将工作集内存减少到k。

是否有一些标准命令行工具的组合可以有效地做到这一点，而无需我自己编写代码？理想情况下，它将支持 sort 命令的完整表达排序功能。排序（至少在 ubuntu 上）似乎没有手册页记录的开关来关闭它......

4

3 回答 3

2

基于上述内容，以及更多的戳，我会说我的问题的官方答案是“没有解决方案”。您可以使用专门的工具，也可以使用现有的工具以它们当前的性能，或者您可以编写自己的工具。

我正在讨论跟踪排序源代码并提供补丁。同时，如果这个快速的 hack 代码可以帮助任何人做类似于我正在做的事情，这就是我为自己写的。不是最好的 python，而且是一个非常阴暗的基准：我将它提供给任何关心提供更严格的人：

  • 256 个文件，总大小约为 1.6 Gig，全部位于 ssd 上，行由 \n 分隔，行格式为 [^\t]*\t[0-9]+
  • Ubuntu 10.4、6 核、8 gigs 内存、ssd 上的 /tmp。
  • $ time sort -t^v<tab> -k2,2n foo* | tail -10000
    • 真正的 7m26.444s
    • 用户 7m19.790s
    • 系统 0m17.530s
  • $ time python test.py 10000 foo*
    • 真正的 1m29.935s
    • 用户 1m28.640s
    • 系统 0m1.220s
  • 使用diff分析，两种方法在平局上有所不同，但排序顺序相同。

测试.py：

#!/usr/bin/env python
# test.py

from sys import argv
import heapq
from itertools import chain

# parse N - the size of the heap, and confirm we can open all input files
N = int(argv[1])
streams = [open(f, "r") for f in argv[2:]]

def line_iterator_to_tuple_iterator(line_i):
    for line in line_i:
        s,c = line.split("\t")
        c = int(c)
        yield (c, s)

# use heap to process inputs
rez = heapq.nlargest(N,
               line_iterator_to_tuple_iterator(chain(*streams)),
               key=lambda x: x[0])

for r in rez:
    print "%s\t%s" % (r[1], r[0])

for s in streams:
    s.close()
于 2013-02-19T02:56:44.410 回答
1

UNIX/Linux 提供通才工具集。对于大型数据集，它会加载大量 I/O。它会做你想做的一切，但速度很慢。如果我们对输入数据有所了解，那将有很大帮助。

IMO，你有一些选择，没有一个你会真正喜欢。

  1. 进行多部分“基数”预排序 - 例如让 awk 将键以“A”开头的所有行写入一个文件“B”到另一个文件，等等。或者如果你只有“P”、“D”和“Q” '，让 awk 吸出你想要的东西。然后对一个小子集进行完整排序。这将创建 26 个名为 A、B ...Z 的文件

    awk '{打印 $0 > substr($0,1,1)} 大文件；排序 [此处的选项] PDQ > 结果

  2. 花费 $$：（示例）从iri.com 任何其他排序软件购买 CoSort。这些类型使用各种优化，但它们不像 bash 那样免费。您还可以购买 SSD，它将磁盘上的排序速度提高几个数量级。5000iops现在到75000iops. 使用该TMPDIR变量将您的 tmp 文件放在 SSD 上，只对 SSD 进行读写。但是使用您现有的 UNIX 工具集。

  3. 使用一些软件，如 R 或 strata，或者最好是数据库；所有这些都适用于大型数据集。

  4. 做你现在正在做的事情，但是在 UNIX 排序运行时观看 youtube。

IMO，当您想要快速结果时，您对大型数据集使用了错误的工具。

于 2013-02-15T00:53:31.937 回答
0

这是一个粗略的部分解决方案：

#!/usr/bin/perl

use strict;
use warnings;

my @lines = ();

while (<>) {
    push @lines, $_;
    @lines = sort @lines;
    if (scalar @lines > 10) {
        pop @lines;
    }
}
print @lines;

它只读取一次输入数据，持续维护前 10 行的排序数组。

当然，每次对整个数组进行排序是低效的，但我猜对于千兆字节的输入，它仍然会比sort huge-file | head.

添加一个选项来改变打印的行数会很容易。添加选项来控制如何完成排序会有点困难，但如果CPAN中有一些东西可以帮助我，我不会感到惊讶。

更抽象地说，从大数组中仅获取前 N 个已排序元素的一种方法是使用部分快速排序，除非需要，否则您不必费心对正确的分区进行排序。这需要将整个数组保存在内存中，这在您的情况下可能是不切实际的。

您可以将输入分成中等大小的块，应用一些巧妙的算法来获取每个块的前 N ​​行，将这些块连接在一起，然后将相同的算法应用于结果。根据块的大小，sort ... | head可能足够聪明。split -l ...将用于执行此操作的 shell 脚本组合在一起应该不难。

（根据需要插入更多的挥手。）

免责声明：我只是在一个比你正在使用的文件（大约 170 万行）小得多的文件上尝试了这个，而且我的方法比sort ... | head.

于 2013-02-15T01:30:55.863 回答