9

そこで、私は小さなデータ処理タスクを処理するPythonプログラムを作成しました。

これが私が望む計算の構成言語での非常に簡単な仕様です:

parse "%s %lf %s" aa bb cc | group_by aa | quickselect --key=bb 0:5 | \
    flatten | format "%s %lf %s" aa bb cc

つまり、各行について、単語、浮動小数点数、および別の単語を解析します。それらをプレーヤーID、スコア、および日付と考えてください。各プレイヤーの上位5つのスコアと日付が必要です。データサイズは簡単ではありませんが、巨大ではありません。約630メガバイト。

同様に短く(以下のPythonのように)、はるかに高速にするために、実際に実行可能な言語をどのように記述すべきかを知りたいです。

#!/usr/bin/python
# -*- coding: utf-8; -*-
import sys

top_5 = {}

for line in sys.stdin:
    aa, bb, cc = line.split()

    # We want the top 5 for each distinct value of aa.  There are
    # hundreds of thousands of values of aa.
    bb = float(bb)
    if aa not in top_5: top_5[aa] = []
    current = top_5[aa]
    current.append((bb, cc))

    # Every once in a while, we drop the values that are not in
    # the top 5, to keep our memory footprint down, because some
    # values of aa have thousands of (bb, cc) pairs.
    if len(current) > 10:
        current.sort()
        current[:-5] = []

for aa in top_5:
    current = top_5[aa]
    current.sort()
    for bb, cc in current[-5:]:
        print aa, bb, cc

入力データの例を次に示します。

3 1.5 a
3 1.6 b
3 0.8 c
3 0.9 d
4 1.2 q
3 1.5 e
3 1.8 f
3 1.9 g

これが私がそれから得た出力です:

3 1.5 a
3 1.5 e
3 1.6 b
3 1.8 f
3 1.9 g
4 1.2 q

、には7つの値があり、値が上位5から外れるため、との値3を削除します。値が1つしかないため、その「上位5」はその1つの値のみで構成されます。cdbb4

これは、MySQLで同じクエリを実行するよりも高速に実行されます(少なくとも、クエリを実行する方法で)が、ほとんどの時間をPythonバイトコードインタープリターに費やしていると確信しています。別の言語では、おそらく1分あたりではなく1秒あたり数十万行を処理できると思います。ですから、より高速な実装の言語で書きたいと思います。

しかし、どの言語を選ぶべきかわかりません。

これをSQLで単一のクエリとして表現する方法を理解できていません。実際 select * from foo into outfile 'bar';、入力データだけでもMySQLの機能に感心していません。

Cは当然の選択ですが、line.split()2タプルのリストの並べ替え、ハッシュテーブルの作成などでは、標準ライブラリにないコードを記述する必要があるため、14行ではなく100行以上のコードになります。

C ++の方が良い選択のようですが(標準ライブラリに文字列、マップ、ペア、およびベクトルがあります)、コードはSTLでかなり乱雑になるようです。

OCamlは問題ありませんが、同等のものがありline.split()ますか?そのマップのパフォーマンスについては悲しいですか?

Common Lispは機能するかもしれませんか?

ループを高速コードにプッシュダウンできる、このようなデータベース計算用のMatlabに相当するものはありますか?誰かがを試しましたか?

(編集:サンプルの入力および出力データを提供することでdavethegr8のコメントに応答し、Pythonプログラムのバグを修正しました!)

(追加編集:うわー、このコメントスレッドはこれまでのところ本当に素晴らしいです。ありがとう、みんな!)

編集:

2007年にsbcl-develで不気味に似た質問がありました(ありがとう、Rainer!)。awkこれは、いくつかのテストデータを生成するためのWill Hartungのスクリプトです(実際のデータのジップの分布はありませんが)。

BEGIN {
 for (i = 0; i < 27000000; i++) {
  v = rand();
  k = int(rand() * 100);
  print k " " v " " i;
 }
 exit;
}
4

18 に答える 18

9

データに関する事前知識のないスクリプト (そのような情報がプリロードされている MySql とは異なります) が、SQL アプローチよりも高速であるとは信じがたいです。

入力の解析に費やされる時間とは別に、スクリプトは配列などによる順序のソートを「維持」する必要があります...

以下は、テーブルの aa、bb、cc 列のインデックス (*) がこの順序であると仮定して、SQL で適切に高速に動作する最初の推測です。(可能な代替手段は、「aa、bb DESC、cc」インデックスです。

(*) このインデックスはクラスター化されていてもいなくても、次のクエリには影響しません。クラスタリングするかどうか、および「aa、bb、cc」の個別のインデックスが必要かどうかの選択は、ユースケース、テーブル内の行のサイズなどによって異なります。

SELECT T1.aa, T1.bb, T1.cc , COUNT(*)
FROM tblAbc T1
LEFT OUTER JOIN tblAbc T2 ON T1.aa = T2.aa AND 
         (T1.bb < T2.bb OR(T1.bb = T2.bb AND T1.cc < T2.cc))
GROUP BY T1.aa, T1.bb, T1.cc
HAVING COUNT(*) < 5  -- trick, remember COUNT(*) goes 1,1,2,3,...
ORDER BY T1.aa, T1.bb, T1.cc, COUNT(*) DESC

アイデアは、特定の aa 値内で自分自身よりも小さいレコードの数を取得することです。ただし、小さなトリックがあります。最大の bb 値または最後のレコード (トップ 5 の 1 つである可能性があります) を持つレコードを破棄しないように、LEFT OUTER 結合を使用する必要があります。左結合の結果として、COUNT(*) 値は 1、1、2、3、4 などをカウントするため、HAVING テストは "<5" であり、上位 5 つを効果的に選択します。

OP のサンプル出力をエミュレートするために、ORDER BY は COUNT() で DESC を使用します。これを削除すると、より伝統的なトップ 5 タイプのリストを取得できます。また、選択リストの COUNT() は、必要に応じて削除できます。これは、クエリのロジックや適切な並べ替え機能に影響しません。

また、このクエリは、同点の処理に関して決定論的であることに注意してください。つまり、特定のレコード セットの bb が同じ値 (aa グループ内) の場合です。Python プログラムは、入力データの順序が変更されると、わずかに異なる出力を提供する可能性があると思います。これは、ソート辞書が時折切り捨てられるためです。

本当の解決策: SQL ベースの手続き型アプローチ

上記の自己結合アプローチは、宣言ステートメントを使用して OP の要件を表現する方法を示しています。ただし、このアプローチは、そのパフォーマンスが各「カテゴリ」内のレコード数の二乗和に大まかにバインドされるという意味で単純です。(O(n^2) ではなく、おおまかに O((n/a)^2) (ここで、a は aa 列の異なる値の数)) つまり、平均して関連付けられたレコード数が与えられた aa 値は数十を超えません。aa 列が選択的でないようなデータの場合は、次のアプローチの方がはるかに適しています。SQL の効率的な並べ替えフレームワークを活用しながら、宣言的な方法では表現しにくい単純なアルゴリズムを実装します。このアプローチは、次の aa 値の単純なバイナリ検索を導入することにより、カーソル内で前方 (および場合によっては後方...) を検索することにより、それぞれ/ほとんどの aa 'カテゴリ' の特に膨大な数のレコードを含むデータセットに対してさらに改善できます。tblAbc の全体的な行数に対する aa 'categories' の数が少ない場合は、この次の方法の後に別の方法を参照してください。

DECLARE @aa AS VARCHAR(10), @bb AS INT, @cc AS VARCHAR(10)
DECLARE @curAa AS VARCHAR(10)
DECLARE @Ctr AS INT

DROP TABLE  tblResults;
CREATE TABLE tblResults
(  aa VARCHAR(10),
   bb INT,
   cc VARCHAR(10)
);

DECLARE abcCursor CURSOR 
  FOR SELECT aa, bb, cc
  FROM tblABC
  ORDER BY aa, bb DESC, cc
  FOR READ ONLY;

OPEN abcCursor;

SET @curAa = ''

FETCH NEXT FROM abcCursor INTO @aa, @bb, @cc;
WHILE @@FETCH_STATUS = 0
BEGIN
    IF @curAa <> @aa
    BEGIN
       SET @Ctr = 0
       SET @curAa = @aa
    END
    IF @Ctr < 5
    BEGIN
       SET @Ctr = @Ctr + 1;
       INSERT tblResults VALUES(@aa, @bb, @cc);
    END
    FETCH NEXT FROM AbcCursor INTO @aa, @bb, @cc;
END;

CLOSE abcCursor;
DEALLOCATE abcCursor;

SELECT * from tblResults
ORDER BY aa, bb, cc    -- OR .. bb DESC ... for a more traditional order.

aa が非常に非選択的な場合の上記の代替。言い換えれば、「カテゴリ」が比較的少ない場合です。アイデアは、個別のカテゴリのリストを調べて、これらの値のそれぞれに対して "LIMIT" (MySql) "TOP" (MSSQL) クエリを実行することです。参考までに、以下は、MSSQL 8.0 で、比較的古い/弱いホスト上で、45 の aa 値に分割された 6100 万レコードの tblAbc に対して 63 秒で実行されました。

DECLARE @aa AS VARCHAR(10)
DECLARE @aaCount INT

DROP TABLE  tblResults;
CREATE TABLE tblResults
(  aa VARCHAR(10),
   bb INT,
   cc VARCHAR(10)
);

DECLARE aaCountCursor CURSOR 
  FOR SELECT aa, COUNT(*)
  FROM tblABC
  GROUP BY aa
  ORDER BY aa
  FOR READ ONLY;
OPEN aaCountCursor;


FETCH NEXT FROM aaCountCursor INTO @aa, @aaCount
WHILE @@FETCH_STATUS = 0
BEGIN
    INSERT tblResults 
       SELECT TOP 5 aa, bb, cc
       FROM tblproh
       WHERE aa = @aa
       ORDER BY aa, bb DESC, cc

    FETCH NEXT FROM aaCountCursor INTO @aa, @aaCount;
END;

CLOSE aaCountCursor
DEALLOCATE aaCountCursor

SELECT * from tblResults
ORDER BY aa, bb, cc    -- OR .. bb DESC ... for a more traditional order.

索引が必要かどうかの問題について. (OPの発言を参照)「SELECT * FROM myTable」を実行するだけの場合、テーブルスキャンが事実上最速のアプローチであり、インデックスを気にする必要はありません。ただし、SQL が通常この種のことに適している主な理由は (外部ソリューションは関連データをエクスポートする時間を考慮する必要があるのに対し、最初にデータが蓄積されているリポジトリであることは別として)、インデックスに依存してスキャンを回避できるということです。多くの汎用言語は生の処理を処理するのにはるかに適していますが、SQL がデータ収集/インポート段階で収集したデータの事前知識を再構築する必要があるため、SQL との不公平な戦いを戦っています。並べ替えは通常、時間とスペースを消費するタスクであるため、

また、事前に作成されたインデックスがなくても、最新のクエリ オプティマイザーは、一時的なインデックスの作成を含む計画を決定する場合があります。また、並べ替えは DDMS の本質的な部分であるため、SQL サーバーは一般にその領域で効率的です。

それで... SQLの方が優れていますか?

これは、純粋な ETL ジョブ、つまり、さまざまな変換とフィルタリングを実行するための入力としてヒープ(インデックスのないテーブル) を処理するために SQL と他の言語を比較しようとしている場合、マルチスレッド対応のユーティリティで書かれている可能性がありますC、および効率的な並べ替えライブラリを活用すると、おそらく高速になります。SQL アプローチと非 SQL アプローチのどちらを使用するかを決定する決定的な問題は、データがどこにあり、最終的にどこに存在する必要があるかです。「チェーン」に沿って提供されるようにファイルを変換するだけの場合は、外部プログラムの方が適しています。SQL サーバーにデータがある、または必要な場合、外部にエクスポートして処理する価値があるのはまれなケースだけです。

于 2009-09-23T18:50:07.520 に答える
6

よりスマートなデータ構造を使用しても、引き続き Python を使用できます。私はあなたの参照実装と私のpython実装を私のマシンで実行し、出力を比較して結果を確認しました。

これはあなたの物です:

$ time python ./ref.py  < data-large.txt  > ref-large.txt

real 1m57.689s
user 1m56.104s
sys 0m0.573s

これは私のものです:

$ time python ./my.py  < data-large.txt  > my-large.txt

real 1m35.132s
user 1m34.649s
sys 0m0.261s
$ diff my-large.txt ref-large.txt 
$ echo $?
0

そして、これがソースです:

#!/usr/bin/python
# -*- coding: utf-8; -*-
import sys
import heapq

top_5 = {}

for line in sys.stdin:
    aa, bb, cc = line.split()

    # We want the top 5 for each distinct value of aa.  There are
    # hundreds of thousands of values of aa.
    bb = float(bb)
    if aa not in top_5: top_5[aa] = []
    current = top_5[aa]
    if len(current) < 5:
        heapq.heappush(current, (bb, cc))
    else:
        if current[0] < (bb, cc):
            heapq.heapreplace(current, (bb, cc))

for aa in top_5:
    current = top_5[aa]
    while len(current) > 0:
        bb, cc = heapq.heappop(current)
        print aa, bb, cc

更新:自分の限界を知りましょう。また、元のコードに似たコードを使用して最速の python ソリューションを知るために、noop コードの時間を計りました。

$ time python noop.py < data-large.txt  > noop-large.txt

real    1m20.143s
user    1m19.846s
sys 0m0.267s

そして、noop.py 自体:

#!/usr/bin/python
# -*- coding: utf-8; -*-
import sys
import heapq

top_5 = {}

for line in sys.stdin:
    aa, bb, cc = line.split()

    bb = float(bb)
    if aa not in top_5: top_5[aa] = []
    current = top_5[aa]
    if len(current) < 5:
        current.append((bb, cc))

for aa in top_5:
    current = top_5[aa]
    current.sort()
    for bb, cc in current[-5:]:
        print aa, bb, cc
于 2009-09-24T06:08:23.267 に答える
3

これはCommon Lispでのスケッチです

長いファイルの場合、READ-LINE を使用するとペナルティが発生することに注意してください。これは、行ごとに新しい文字列が作成されるためです。次に、ライン バッファを使用している、あちこちに出回っている READ-LINE の派生物の 1 つを使用します。また、ハッシュ テーブルで大文字と小文字を区別するかどうかを確認することもできます。

2 番目のバージョン

ここで行うため、文字列を分割する必要はなくなりました。これは低レベルのコードであり、速度が向上することを期待しています。フィールド区切り記号として 1 つ以上のスペースとタブもチェックします。

(defun read-a-line (stream)
  (let ((line (read-line stream nil nil)))
    (flet ((delimiter-p (c)
             (or (char= c #\space) (char= c #\tab))))
      (when line
        (let* ((s0 (position-if     #'delimiter-p line))
               (s1 (position-if-not #'delimiter-p line :start s0))
               (s2 (position-if     #'delimiter-p line :start (1+ s1)))
               (s3 (position-if     #'delimiter-p line :from-end t)))
          (values (subseq line 0 s0)
                  (list (read-from-string line nil nil :start s1 :end s2)
                        (subseq line (1+ s3)))))))))

上記の関数は、キーと残りのリストの 2 つの値を返します。

(defun dbscan (top-5-table stream)
   "get triples from each line and put them in the hash table"
  (loop with aa = nil and bbcc = nil do
    (multiple-value-setq (aa bbcc) (read-a-line stream))
    while aa do
    (setf (gethash aa top-5-table)
          (let ((l (merge 'list (gethash aa top-5-table) (list bbcc)
                          #'> :key #'first)))
             (or (and (nth 5 l) (subseq l 0 5)) l)))))


(defun dbprint (table output)
  "print the hashtable contents"
  (maphash (lambda (aa value)
              (loop for (bb cc) in value
                    do (format output "~a ~a ~a~%" aa bb cc)))
           table))

(defun dbsum (input &optional (output *standard-output*))
  "scan and sum from a stream"
  (let ((top-5-table (make-hash-table :test #'equal)))
    (dbscan top-5-table input)
    (dbprint top-5-table output)))


(defun fsum (infile outfile)
   "scan and sum a file"
   (with-open-file (input infile :direction :input)
     (with-open-file (output outfile
                      :direction :output :if-exists :supersede)
       (dbsum input output))))

いくつかのテストデータ

(defun create-test-data (&key (file "/tmp/test.data") (n-lines 100000))
  (with-open-file (stream file :direction :output :if-exists :supersede)
    (loop repeat n-lines
          do (format stream "~a ~a ~a~%"
                     (random 1000) (random 100.0) (random 10000)))))

; (テストデータ作成)

(defun test ()
  (time (fsum "/tmp/test.data" "/tmp/result.data")))

3 番目のバージョン、LispWorks

一部の SPLIT-STRING および PARSE-FLOAT 関数を使用しますが、それ以外は汎用 CL を使用します。

(defun fsum (infile outfile)
  (let ((top-5-table (make-hash-table :size 50000000 :test #'equal)))
    (with-open-file (input infile :direction :input)
      (loop for line = (read-line input nil nil)
            while line do
            (destructuring-bind (aa bb cc) (split-string '(#\space #\tab) line)
              (setf bb (parse-float bb))
              (let ((v (gethash aa top-5-table)))
                (unless v
                  (setf (gethash aa top-5-table)
                        (setf v (make-array 6 :fill-pointer 0))))
                (vector-push (cons bb cc) v)
                (when (> (length v) 5)
                  (setf (fill-pointer (sort v #'> :key #'car)) 5))))))
    (with-open-file (output outfile :direction :output :if-exists :supersede)
      (maphash (lambda (aa value)
                 (loop for (bb . cc) across value do
                       (format output "~a ~f ~a~%" aa bb cc)))
               top-5-table))))    
于 2009-09-23T19:12:02.453 に答える
3

これには、次のような 27M 行のデータがある私のマシンで 45.7 秒かかりました。

42 0.49357 0
96 0.48075 1
27 0.640761 2
8 0.389128 3
75 0.395476 4
24 0.212069 5
80 0.121367 6
81 0.271959 7
91 0.18581 8
69 0.258922 9

あなたのスクリプトはこのデータに 1m42 かかり、c++ の例も 1m46 かかりました (g++ t.cpp -ot をコンパイルして、c++ については何も知りません)。

Java 6、それは本当に重要ではありません。出力は完璧ではありませんが、簡単に修正できます。

package top5;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) throws Exception {
        long start  = System.currentTimeMillis();
        Map<String, Pair[]> top5map = new TreeMap<String, Pair[]>();
        BufferedReader br = new BufferedReader(new FileReader("/tmp/file.dat"));

        String line = br.readLine();
        while(line != null) {
            String parts[] = line.split(" ");

            String key = parts[0];
            double score = Double.valueOf(parts[1]);
            String value = parts[2];
            Pair[] pairs = top5map.get(key);

            boolean insert = false;
            Pair p = null;
            if (pairs != null) {
                insert = (score > pairs[pairs.length - 1].score) || pairs.length < 5;
            } else {
                insert = true;
            }
            if (insert) {
                p = new Pair(score, value);
                if (pairs == null) {
                    pairs = new Pair[1];
                    pairs[0] = new Pair(score, value);
                } else {
                    if (pairs.length < 5) {
                        Pair[] newpairs = new Pair[pairs.length + 1];
                        System.arraycopy(pairs, 0, newpairs, 0, pairs.length);
                        pairs = newpairs;
                    }
                    int k = 0;
                    for(int i = pairs.length - 2; i >= 0; i--) {
                        if (pairs[i].score <= p.score) {
                            pairs[i + 1] = pairs[i];
                        } else {
                            k = i + 1;
                            break;
                        }
                    }
                    pairs[k] = p;
                }
                top5map.put(key, pairs);
            }
            line = br.readLine();
        }
        for(Map.Entry<String, Pair[]> e : top5map.entrySet()) {
            System.out.print(e.getKey());
            System.out.print(" ");
            System.out.println(Arrays.toString(e.getValue()));
        }
        System.out.println(System.currentTimeMillis() - start);
    }

    static class Pair {
        double score;
        String value;

        public Pair(double score, String value) {
            this.score = score;
            this.value = value;
        }

        public int compareTo(Object o) {
            Pair p = (Pair) o;
            return (int)Math.signum(score - p.score);
        }

        public String toString() {
            return String.valueOf(score) + ", " + value;
        }
    }
}

データを偽装する AWK スクリプト:

BEGIN {
 for (i = 0; i < 27000000; i++) {
  v = rand();
  k = int(rand() * 100);
  print k " " v " " i;
 }
 exit;
}
于 2009-09-23T22:19:09.237 に答える
3

これは、Streams のカスタムパーサーを備えた、スピードをターゲットにしたもう 1 つの OCaml バージョンです。長すぎますが、パーサーの一部は再利用可能です。競争を引き起こしてくれたpefeuに感謝します:)

スピード :

  • シンプルな ocaml - 27 秒
  • ストリーム パーサーを使用した ocaml - 15 秒
  • 手動パーサーを使用した c - 5 秒

でコンパイル:

ocamlopt -pp camlp4o code.ml -o caml

コード :

open Printf

let cmp x y = compare (fst x : float) (fst y)
let digit c = Char.code c - Char.code '0'

let rec parse f = parser
  | [< a=int; _=spaces; b=float; _=spaces; 
       c=rest (Buffer.create 100); t >] -> f a b c; parse f t
  | [< >] -> ()
and int = parser
  | [< ''0'..'9' as c; t >] -> int_ (digit c) t
  | [< ''-'; ''0'..'9' as c; t >] -> - (int_ (digit c) t)
and int_ n = parser
  | [< ''0'..'9' as c; t >] -> int_ (n * 10 + digit c) t
  | [< >] -> n
and float = parser
  | [< n=int; t=frem; e=fexp >] -> (float_of_int n +. t) *. (10. ** e)
and frem = parser
  | [< ''.'; r=frem_ 0.0 10. >] -> r
  | [< >] -> 0.0
and frem_ f base = parser
  | [< ''0'..'9' as c; t >] -> 
      frem_ (float_of_int (digit c) /. base +. f) (base *. 10.) t
  | [< >] -> f
and fexp = parser
  | [< ''e'; e=int >] -> float_of_int e
  | [< >] -> 0.0
and spaces = parser
  | [< '' '; t >] -> spaces t
  | [< ''\t'; t >] -> spaces t
  | [< >] -> ()
and crlf = parser
  | [< ''\r'; t >] -> crlf t
  | [< ''\n'; t >] -> crlf t
  | [< >] -> ()
and rest b = parser
  | [< ''\r'; _=crlf >] -> Buffer.contents b
  | [< ''\n'; _=crlf >] -> Buffer.contents b
  | [< 'c; t >] -> Buffer.add_char b c; rest b t
  | [< >] -> Buffer.contents b

let () =
  let all = Array.make 200 [] in
  let each a b c =
    assert (a >= 0 && a < 200);
    match all.(a) with
    | [] -> all.(a) <- [b,c]
    | (bmin,_) as prev::tl -> if b > bmin then
      begin
        let m = List.sort cmp ((b,c)::tl) in
        all.(a) <- if List.length tl < 4 then prev::m else m
      end
  in
  parse each (Stream.of_channel stdin);
  Array.iteri 
    (fun a -> List.iter (fun (b,c) -> printf "%i %f %s\n" a b c))
    all
于 2009-10-01T09:40:44.797 に答える
2

非常に単純な Caml (27 * 10^6 行 -- 27 秒、hrnt による C++ -- 29 秒)

open Printf
open ExtLib

let (>>) x f = f x
let cmp x y = compare (fst x : float) (fst y)
let wsp = Str.regexp "[ \t]+"

let () =
  let all = Hashtbl.create 1024 in
  Std.input_lines stdin >> Enum.iter (fun line ->
    let [a;b;c] = Str.split wsp line in
    let b = float_of_string b in
    try
      match Hashtbl.find all a with
      | [] -> assert false
      | (bmin,_) as prev::tl -> if b > bmin then
        begin
          let m = List.sort ~cmp ((b,c)::tl) in
          Hashtbl.replace all a (if List.length tl < 4 then prev::m else m)
        end
    with Not_found -> Hashtbl.add all a [b,c]
  );
  all >> Hashtbl.iter (fun a -> List.iter (fun (b,c) -> printf "%s %f %s\n" a b c))
于 2009-09-25T13:12:46.753 に答える
2

これまでにテストしたこのスレッドのすべてのプログラムの中で、OCamlバージョンは最速であり、最短でもあります。(コード行ベースの測定値は少しあいまいですが、Python バージョンや C または C++ バージョンよりも明らかに長くなく、明らかに高速です。)

注: 以前のランタイムが非決定的だった理由がわかりました! CPU ヒートシンクがほこりで詰まっていて、結果として CPU が過熱していました。今、私は素晴らしい決定論的なベンチマーク時間を取得しています. このスレッドのすべてのタイミング測定をやり直したので、信頼できるタイミングを計ることができたと思います。

2,700 万行、630 メガバイトの入力データ ファイルで実行された、これまでのさまざまなバージョンのタイミングを次に示します。私は、デュアルコア 1.6GHz Celeron で Ubuntu Intrepid Ibex を使用しており、OS の 32 ビット バージョンを実行しています (64 ビット バージョンではイーサネット ドライバーが壊れていました)。各プログラムを 5 回実行し、その 5 回の試行にかかった時間の範囲を報告します。Python 2.5.2、OpenJDK 1.6.0.0、OCaml 3.10.2、GCC 4.3.2、SBCL 1.0.8.debian、および Octave 3.0.1 を使用しています。

  • SquareCog の Pig バージョン: まだテストされていません (テストできないためapt-get install pig)、コードは7行です。
  • mjv の純粋な SQL バージョン: まだテストされていませんが、数日間の実行時間を予測しています。7行のコード。
  • ygrek の OCaml バージョン: 15行のコードで68.7 秒±0.9 。
  • 私の Python バージョン: 169 秒±4 または86 秒±2 (Psyco を使用)、16行のコード。
  • abbot のヒープベースの Python バージョン: 18行のコードで177 秒±5 、またはPsyco で83 秒±5。
  • 以下の私の C バージョンは、GNU で構成されていますsort -n: 90 + 5.5 秒(±3、±0.1) ですが、GNU の欠陥によりsort22行のコード (シェルの 1 行を含む) で間違った答えが返されます。
  • hrnt の C++ バージョン: 25行のコードで217 秒±3 。
  • mjv の代替 SQL ベースの手続き型アプローチ: まだテストされていない、26行のコード。
  • mjv の最初の SQL ベースの手続き型アプローチ: まだテストされていない、29行のコード。
  • Psyco を使用したpeufeu のPython バージョン: 181 秒±4、約30行のコード。
  • Rainer Joswig の Common Lisp バージョン: 42行のコードで478 秒(1 回だけ実行) 。
  • abbot's noop.py、下限を確立するために意図的に誤った結果を与える: まだテストされていない、15行のコード。
  • Will Hartung の Java バージョン: 96 秒± 10 インチ、David A. Wheeler の SLOCCount、74行のコードによると。
  • Greg の Matlab バージョン: 動作しません。
  • Python バージョンの 1 つで Pyrex を使用するという Schuyler Erle の提案: まだ試していません。

アボットのバージョンは、実際のデータセットの分布が非常に不均一であるため、私にとっては彼らよりも比較的悪い結果になると思います。前述したように、一部のaa値 (「プレーヤー」) には数千の行があり、他の値には 1 つしかありません。

Psyco について: Psyco を元のコード (および修道院長のバージョン) に適用するために、それをmain関数に入れ、それ自体で時間を約 140 秒に短縮し、 を呼び出すpsyco.full()前に を呼び出しmain()ました。これにより、約 4 行のコードが追加されました。

次のように、 GNU を使用して問題をほぼ解決できます。sort

kragen@inexorable:~/devel$ time LANG=C sort -nr infile -o sorted

real    1m27.476s
user    0m59.472s
sys 0m8.549s
kragen@inexorable:~/devel$ time ./top5_sorted_c < sorted > outfile

real    0m5.515s
user    0m4.868s
sys 0m0.452s

このtop5_sorted_c短い C プログラムは次のとおりです。

#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

enum { linesize = 1024 };

char buf[linesize];
char key[linesize];             /* last key seen */

int main() {
  int n = 0;
  char *p;

  while (fgets(buf, linesize, stdin)) {
    for (p = buf; *p && !isspace(*p); p++) /* find end of key on this line */
      ;
    if (p - buf != strlen(key) || 0 != memcmp(buf, key, p - buf)) 
      n = 0;                    /* this is a new key */
    n++;

    if (n <= 5)               /* copy up to five lines for each key */
      if (fputs(buf, stdout) == EOF) abort();

    if (n == 1) {               /* save new key in `key` */
      memcpy(key, buf, p - buf);
      key[p-buf] = '\0';
    }
  }
  return 0;
}

最初にそのプログラムを C++ で次のように書いてみましたが、実行時間が大幅に遅くなり、5.5±0.1 秒ではなく 33.6±2.3 秒になりました。

#include <map>
#include <iostream>
#include <string>

int main() {
  using namespace std;
  int n = 0;
  string prev, aa, bb, cc;

  while (cin >> aa >> bb >> cc) {
    if (aa != prev) n = 0;
    ++n;
    if (n <= 5) cout << aa << " " << bb << " " << cc << endl;
    prev = aa;
  }
  return 0;
}

私はほぼ言った。問題はsort -n、ほとんどのデータでは問題ないのに、 と比較しようとすると失敗すること0.33です3.78168e-05。したがって、この種のパフォーマンスを実現して実際に問題を解決するには、より優れたソートが必要です。

とにかく、私は泣き言を言っているように感じますが、並べ替えとフィルターのアプローチは Python プログラムよりも約 5 倍高速ですが、hrnt のエレガントな STL プログラムは実際には少し遅くなります。の総非効率<iostream>std::mapランタイムの残りの 83% がフィルターの小さな C++ バージョンでどこに行くのかはわかりませんが、どこにも役に立たないので、hrnt のバージョンでもどこに行くのかわからないのではないかと疑っています。そのバージョンも 5 倍高速化できますか? それはかなりクールだからです。そのワーキング セットは私の L2 キャッシュよりも大きいかもしれませんが、そうではない可能性があります。

callgrind を使用した調査によると、私の C++ のフィルター プログラムは、 内でその命令の 97% を実行していoperator >>ます。入力バイトごとに少なくとも 10 個の関数呼び出しを識別できますが、cin.sync_with_stdio(false);役に立ちません。これはおそらく、入力行をより効率的に解析することで、hrnt の C プログラムを大幅に高速に実行できることを意味します。

編集: kcachegrind は、hrnt のプログラムが (157000 行の小さな入力ファイルで) 命令の 62% を実行し、doubleから s を抽出すると主張していますistream。これのかなりの部分は、istreams ライブラリがdouble. 非常識。kcachegrind の出力を誤解している可能性はありますか?

とにかく、他の提案はありますか?

于 2009-09-24T02:39:38.133 に答える
1

誰かがawkだけでこの問題を実行しようとしたことがありますか。具体的には「mawk」?このブログ投稿によると、JavaやC ++よりも高速であるはずです:http://anyall.org/blog/2009/09/dont-mawk-awk-the-fastest-and-most-elegant-big-data- munging-language /

編集:そのブログ投稿で行われている唯一の主張は、awkスタイルの処理に特に適した特定のクラスの問題について、mawk仮想マシンがJavaおよびC++の「バニラ」実装を打ち負かすことができるということです。

于 2009-09-24T04:34:01.560 に答える
1

興味深いことに、元の Python ソリューションは、見た目が最もクリーンです(ただし、C++ の例はそれに近いものです)。

オリジナルのコードで Pyrex や Psyco を使用するのはどうですか?

于 2009-09-24T00:37:18.707 に答える
1

あなたがMatlabについて尋ねたので、あなたが求めているようなことをした方法は次のとおりです。for ループを使わずに実行しようとしましたが、長い時間をかけたくないので、for ループを使用しています。メモリが心配な場合は、バッファ全体を読み取るのではなく、fscanf を使用してストリームからチャンクでデータを取得できます。

fid = fopen('fakedata.txt','r');
tic
A=fscanf(fid,'%d %d %d\n');
A=reshape(A,3,length(A)/3)';  %Matlab reads the data into one long column'
Names = unique(A(:,1));
for i=1:length(Names)
    indices = find(A(:,1)==Names(i));   %Grab all instances of key i
    [Y,I] = sort(A(indices,2),1,'descend'); %sort in descending order of 2nd record
    A(indices(I(1:min([5,length(indices(I))]))),:) %Print the top five
end
toc
fclose(fid)
于 2009-09-24T23:14:46.963 に答える
1

これがC++ソリューションです。ただし、テストするためのデータがあまりなかったので、実際の速度はわかりません。

[編集] このスレッドの awk スクリプトによって提供されたテスト データのおかげで、コードをクリーンアップして少し高速化することができました。私は可能な限り最速のバージョンを見つけようとしているわけではありません - その意図は、STL ソリューションが可能であると人々が考えるほど醜くはない、適度に高速なバージョンを提供することです。

このバージョンは、最初のバージョンの約 2 倍の速度になるはずです (約 35 秒で 2,700 万行を処理します)。Gcc ユーザーは、これを -O2 でコンパイルすることを忘れないでください。

#include <map>
#include <iostream>
#include <functional>
#include <utility>
#include <string>
int main() {
  using namespace std;
  typedef std::map<string, std::multimap<double, string> > Map;
  Map m;
  string aa, cc;
  double bb;
  std::cin.sync_with_stdio(false); // Dunno if this has any effect, but anyways.

  while (std::cin >> aa >> bb >> cc)
    {
      if (m[aa].size() == 5)
        {
          Map::mapped_type::iterator iter = m[aa].begin();
          if (bb < iter->first)
            continue;
          m[aa].erase(iter);
        }
      m[aa].insert(make_pair(bb, cc));
    }
  for (Map::const_iterator iter = m.begin(); iter != m.end(); ++iter)
    for (Map::mapped_type::const_iterator iter2 = iter->second.begin();
         iter2 != iter->second.end();
         ++iter2)
      std::cout << iter->first << " " << iter2->first << " " << iter2->second <<
 std::endl;

}
于 2009-09-23T21:32:51.003 に答える
1

計算時間の下限といえば:

上記の私のアルゴを分析しましょう:

for each row (key,score,id) :
    create or fetch a list of top scores for the row's key
    if len( this list ) < N
        append current
    else if current score > minimum score in list
        replace minimum of list with current row
        update minimum of all lists if needed

N を上位 N の N とする R をデータ セット内の行数とする K を個別のキーの数とする

どのような仮定を立てることができますか?

R * sizeof( row ) > RAM または、少なくともすべてをロードしたくないほど十分に大きく、ハッシュを使用してキーでグループ化し、各ビンをソートします。同じ理由で、すべてのものを並べ替えるわけではありません。

Kragen はハッシュテーブルが好きなので、K * sizeof(per-key state) << RAM、おそらく L2/3 キャッシュに収まります

Kragen はソートしていないため、K*N << R つまり、各キーには N よりもはるかに多くのエントリがあります。

(注: A << B は、A が B に対して小さいことを意味します)

データがランダムに分布している場合、

少数の行の後、行の大部分はキーごとの最小条件によって拒否されます。コストは行ごとに 1 つの比較です。

したがって、1 行あたりのコストは、1 回のハッシュ ルックアップ + 1 回の比較 + イプシロン * (リストの挿入 + (N+1) 回の最小比較) です。

スコアがランダムな分布 (たとえば 0 から 1 の間) で、上記の条件が当てはまる場合、両方のイプシロンは非常に小さくなります。

実験的証明:

上記の 2,700 万行のデータセットでは、上位 N リストに 5,933 の挿入が生成されます。他のすべての行は、単純なキーの検索と比較によって拒否されます。イプシロン = 0.0001

大まかに言えば、コストは 1 行あたり 1 回のルックアップ + 比較であり、数ナノ秒かかります。

現在のハードウェアでは、これが IO コスト、特に解析コストに対して無視できないものになることはありません。

于 2009-09-30T12:58:14.117 に答える
0

それは素晴らしい昼休みの挑戦でした、彼、彼。

Top-Nは有名なデータベースキラーです。上記の投稿で示されているように、一般的なSQLで効率的に表現する方法はありません。

さまざまな実装に関しては、これの遅い部分は並べ替えやトップNではなく、テキストの解析であることに注意する必要があります。最近、glibcのstrtod()のソースコードを見ましたか?

たとえば、Pythonを使用すると次のようになります。

Read data : 80.5  s
My TopN   : 34.41 s
HeapTopN  : 30.34 s

データがテキストよりもはるかに高速に解析される形式でない限り、使用する言語に関係なく、非常に速いタイミングが得られない可能性が非常に高くなります。たとえば、テストデータをpostgresにロードするには70秒かかり、その大部分はテキストの解析でもあります。

topNのNが5のように小さい場合は、以下の私のアルゴリズムのC実装がおそらく最速です。Nを大きくできる場合は、ヒープの方がはるかに優れたオプションです。

したがって、データはおそらくデータベースにあり、問題は実際の処理ではなくデータを取得することであるため、超高速のTopNエンジンが本当に必要な場合は、Cモジュールを作成する必要があります。選択したデータベース。postgresはほとんどすべての点で高速なので、postgresを使用することをお勧めします。さらに、postgres用のCモジュールを作成することは難しくありません。

これが私のPythonコードです:

import random, sys, time, heapq

ROWS = 27000000

def make_data( fname ):
    f = open( fname, "w" )
    r = random.Random()
    for i in xrange( 0, ROWS, 10000 ):
        for j in xrange( i,i+10000 ):
            f.write( "%d    %f    %d\n" % (r.randint(0,100), r.uniform(0,1000), j))
        print ("write: %d\r" % i),
        sys.stdout.flush()
    print

def read_data( fname ):
    for n, line in enumerate( open( fname ) ):
        r = line.strip().split()
        yield int(r[0]),float(r[1]),r[2]
        if not (n % 10000 ):
            print ("read: %d\r" % n),
            sys.stdout.flush()
    print

def topn( ntop, data ):
    ntop -= 1
    assert ntop > 0
    min_by_key = {}
    top_by_key = {}
    for key,value,label in data:
        tup = (value,label)
        if key not in top_by_key:
            # initialize
            top_by_key[key] = [ tup ]
        else:
            top = top_by_key[ key ]
            l    = len( top )
            if l > ntop:
                # replace minimum value in top if it is lower than current value
                idx = min_by_key[ key ]
                if top[idx] < tup:
                    top[idx] = tup
                    min_by_key[ key ] = top.index( min( top ) )
            elif l < ntop:
                # fill until we have ntop entries
                top.append( tup )
            else:
                # we have ntop entries in list, we'll have ntop+1
                top.append( tup )
                # initialize minimum to keep
                min_by_key[ key ] = top.index( min( top ) )

    # finalize:
    return dict( (key, sorted( values, reverse=True )) for key,values in top_by_key.iteritems() )

def grouptopn( ntop, data ):
    top_by_key = {}
    for key,value,label in data:
        if key in top_by_key:
            top_by_key[ key ].append( (value,label) )
        else:
            top_by_key[ key ] = [ (value,label) ]

    return dict( (key, sorted( values, reverse=True )[:ntop]) for key,values in top_by_key.iteritems() )

def heaptopn( ntop, data ):
    top_by_key = {}
    for key,value,label in data:
        tup = (value,label)
        if key not in top_by_key:
            top_by_key[ key ] = [ tup ]
        else:
            top = top_by_key[ key ]
            if len(top) < ntop:
                heapq.heappush(top, tup)
            else:
                if top[0] < tup:
                    heapq.heapreplace(top, tup)

    return dict( (key, sorted( values, reverse=True )) for key,values in top_by_key.iteritems() )

def dummy( data ):
    for row in data:
        pass

make_data( "data.txt" )

t = time.clock()
dummy( read_data( "data.txt" ) )
t_read = time.clock() - t

t = time.clock()
top_result = topn( 5, read_data( "data.txt" ) )
t_topn = time.clock() - t

t = time.clock()
htop_result = heaptopn( 5, read_data( "data.txt" ) )
t_htopn = time.clock() - t

# correctness checking :
for key in top_result:
    print key, " : ", "        ".join (("%f:%s"%(value,label)) for (value,label) in    top_result[key])
    print key, " : ", "        ".join (("%f:%s"%(value,label)) for (value,label) in htop_result[key])

print
print "Read data :", t_read
print "TopN :     ", t_topn - t_read
print "HeapTopN : ", t_htopn - t_read

for key in top_result:
    assert top_result[key] == htop_result[key]
于 2009-09-26T13:19:37.470 に答える
0

私は昼休みの課題が大好きです。これは1時間の実装です。

OK、足し算のような非常に風変わりながらくたをしたくない場合は、実装されている演算子が比較だけであるカスタム base-10 浮動小数点形式を使用することを止めるものは何もありませんよね? 笑。

以前のプロジェクトからいくつかの fast-atoi コードが転がっていたので、それをインポートしました。

http://www.copypastecode.com/11541/

この C ソース コードは、580 MB の入力テキスト (2700 万行) を解析するのに約 6.6 秒かかります。その時間の半分は fgets です (笑)。次に、トップ n を計算するのに約 0.05 秒かかりますが、トップ n にかかる時間はタイマー ノイズよりも短いため、正確にはわかりません。

あなたはそれが正しいかどうかをテストする人になりますが、XDDDDDDDDDDDD

面白いでしょ?

于 2009-09-28T12:58:42.437 に答える
0

Pig バージョンは次のようになります (未テスト):

 Data = LOAD '/my/data' using PigStorage() as (aa:int, bb:float, cc:chararray);
 grp = GROUP Data by aa;
 topK = FOREACH grp (
     sorted = ORDER Data by bb DESC;
     lim = LIMIT sorted 5;
     GENERATE group as aa, lim;
)
STORE topK INTO '/my/output' using PigStorage();

Pig はパフォーマンスのために最適化されていません。その目標は、並列実行フレームワークを使用して数テラバイトのデータセットを処理できるようにすることです。ローカルモードがあるので試してみることはできますが、あなたのスクリプトに勝るとは思えません。

于 2009-09-24T05:50:46.233 に答える
0

「トップ 5」を選ぶと、次のようになります。並べ替えがないことに注意してください。また、top_5 ディクショナリのリストが 5 要素を超えることはありません。

from collections import defaultdict
import sys

def keep_5( aList, aPair ):
    minbb= min( bb for bb,cc in aList )
    bb, cc = aPair
    if bb < minbb: return aList
    aList.append( aPair )
    min_i= 0
    for i in xrange(1,6):
        if aList[i][0] < aList[min_i][0]
            min_i= i
    aList.pop(min_i)
    return aList


top_5= defaultdict(list)
for row in sys.stdin:
    aa, bb, cc = row.split()
    bb = float(bb)
    if len(top_5[aa]) < 5:
        top_5[aa].append( (bb,cc) )
    else:
        top_5[aa]= keep_5( top_5[aa], (bb,cc) )
于 2009-09-23T19:23:02.703 に答える
0

これは単純なことではありませんか

 SELECT DISTINCT aa, bb, cc FROM tablename ORDER BY bb DESC LIMIT 5

?

もちろん、データに対してテストしないと何が最速かを判断するのは困難です。これが非常に高速に実行する必要がある場合は、クエリを最適化するのではなく、データベースを最適化してクエリを高速化する方が理にかなっています。

もちろん、とにかくフラット ファイルが必要な場合は、それを使用することもできます。

于 2009-09-23T19:09:24.650 に答える
0

さて、コーヒーを飲んで strtod のソース コードを読んでください。気が遠くなるような内容ですが、float -> text -> float を使用して、最初に使用したのと同じ float を返す場合は必要です....本当に...

整数の解析ははるかに高速です (ただし、Python ではそうではありませんが、C ではそうです)。

とにかく、データをPostgresテーブルに入れます:

SELECT count( key ) FROM the dataset in the above program

=> 7 秒 (したがって、27M レコードを読み取るのに 7 秒かかります)

CREATE INDEX topn_key_value ON topn( key, value );

191秒

CREATE TEMPORARY TABLE topkeys AS SELECT key FROM topn GROUP BY key;

12秒

(インデックスを使用して「キー」の個別の値をより速く取得することもできますが、軽い plpgsql ハッキングが必要です)

CREATE TEMPORARY TABLE top AS SELECT (r).* FROM (SELECT (SELECT b AS r FROM topn b WHERE b.key=a.key ORDER BY value DESC LIMIT 1) AS r FROM topkeys a) foo;

温度: 15,310 ミリ秒

INSERT INTO top SELECT (r).* FROM (SELECT (SELECT b AS r FROM topn b WHERE b.key=a.key ORDER BY value DESC LIMIT 1 OFFSET 1) AS r FROM topkeys a) foo;

温度: 17,853 ミリ秒

INSERT INTO top SELECT (r).* FROM (SELECT (SELECT b AS r FROM topn b WHERE b.key=a.key ORDER BY value DESC LIMIT 1 OFFSET 2) AS r FROM topkeys a) foo;

温度: 13,983 ミリ秒

INSERT INTO top SELECT (r).* FROM (SELECT (SELECT b AS r FROM topn b WHERE b.key=a.key ORDER BY value DESC LIMIT 1 OFFSET 3) AS r FROM topkeys a) foo;

温度: 16,860 ミリ秒

INSERT INTO top SELECT (r).* FROM (SELECT (SELECT b AS r FROM topn b WHERE b.key=a.key ORDER BY value DESC LIMIT 1 OFFSET 4) AS r FROM topkeys a) foo;

温度: 17,651 ミリ秒

INSERT INTO top SELECT (r).* FROM (SELECT (SELECT b AS r FROM topn b WHERE b.key=a.key ORDER BY value DESC LIMIT 1 OFFSET 5) AS r FROM topkeys a) foo;

温度: 19,216 ミリ秒

SELECT * FROM top ORDER BY key,value;

ご覧のとおり、トップ n の計算は非常に高速ですが (n が小さい場合)、(必須の) インデックスの作成は完全な並べ替えを伴うため、非常に遅くなります。

あなたの最善の策は、解析が高速な形式を使用することです(バイナリ、またはデータベース用のカスタムC集計を作成します。これがIMHOの最良の選択です)。Pythonが1秒で実行できる場合、Cプログラムの実行時間は1秒を超えてはなりません。

于 2009-09-27T23:21:10.247 に答える