6

私は基本的に同等のものが欲しい

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

しかし、私の理解では、ソートは入力全体でO（ n log n ）になります。私の場合、大量のデータを処理しているので、ランタイムが重要です。また、一時ファイルの並べ替えでtmp/フォルダーをオーバーフローさせる習慣があります。

ヒープなどを使用してO（n log k）に移行したいのですが、これはおそらく高速になり、ワーキングセットのメモリもkに削減されます。

自分で何かをコーディングしなくても、これを効率的に実行できる標準のコマンドラインツールの組み合わせはありますか？理想的には、sortコマンドの表現力豊かなソート機能を完全にサポートします。sort（少なくともubuntuでは）には、それを実行するためのマニュアルページに記載されたスイッチがないようです...

4

3 に答える 3

2

上記に基づいて、そしてもう少し突っついていると、私の質問に対する公式の答えは「解決策はありません」だと思います。専用のツールを使用することも、現在のパフォーマンスで使用できるツールを使用することも、独自のツールを作成することもできます。

ソートソースコードを追跡し、パッチを提供することについて議論しています。それまでの間、この簡単なハックコードが、私が行っていたのと同じようなことをしている人に役立つ場合に備えて、これが私が自分で書いたものです。最高のPythonではなく、非常に怪しげなベンチマークです。より厳密なものを提供したいと思っている他の人に提供します。

  • 合計サイズが約1.6ギガの256個のファイル、すべてssd上にあり、行は\ nで区切られ、形式は[^ \ t] * \ t[0-9]+です。
  • Ubuntu 10.4、6コア、8ギガのRAM、ssd上の/tmpも同様です。
  • $ time sort -t^v<tab> -k2,2n foo* | tail -10000
    • 実際の7分26秒444
    • ユーザー7m19.790s
    • sys 0m17.530s
  • $ time python test.py 10000 foo*
    • 実際の1分29.935秒
    • ユーザー1分28秒640秒
    • sys 0m1.220s
  • 分析にdiffを使用すると、2つの方法はタイブレークで異なりますが、それ以外の場合、ソート順は同じです。

test.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. マルチパートの「基数」の事前ソートを実行します。たとえば、キーが「A」で始まるすべての行を1つのファイル「B」に別のファイルに書き込みます。 '、awkにあなたが欲しいものを吸い出させてください。次に、小さなサブセットでフルソートを実行します。これにより、A、B...Zという名前の26個のファイルが作成されます

    awk'{print $ 0> substr（$ 0,1,1）} bigfile; 並べ替え[ここのオプション]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;

入力データを 1 回だけ読み取り、上位 10 行の並べ替えられた配列を継続的に維持します。

もちろん、毎回配列全体をソートするのは非効率的ですが、ギガバイトの入力の場合でも、 よりも大幅に高速になると思いますsort huge-file | head。

印刷される行数を変更するオプションを追加するのは簡単です。並べ替えの方法を制御するオプションを追加するのは少し難しくなりますが、CPANにそれを助ける何かがあっても驚かないでしょう。

より抽象的に言えば、大きな配列から最初の N 個の並べ替えられた要素だけを取得する 1 つの方法は、部分的なクイック並べ替えを使用することです。この場合、必要でない限り、正しいパーティションを並べ替える必要はありません。これには、配列全体をメモリに保持する必要がありますが、これはおそらくあなたのケースでは実用的ではありません。

入力を中サイズのチャンクに分割し、巧妙なアルゴリズムを適用して各チャンクの上位 N 行を取得し、チャンクを連結してから、同じアルゴリズムを結果に適用できます。チャンクのサイズによっては、sort ... | head十分に賢いかもしれません。これを行うために使用するシェル スクリプトをまとめるのは難しくありませんsplit -l ...。

(必要に応じて手を振ってください。)

免責事項：私はあなたが作業しているものよりもはるかに小さいファイル（約170万行）でこれを試しましたが、私の方法はsort ... | head.

于 2013-02-15T01:30:55.863 に答える