8

読み込んで辞書を作成する必要がある大きなファイルがあります。私はこれをできるだけ速くしたいと思っています。しかし、Python での私のコードは遅すぎます。問題を示す最小限の例を次に示します。

最初にいくつかの偽のデータを作成します

paste <(seq 20000000) <(seq 2 20000001)  > largefile.txt

これは、それを読み込んで辞書を作成するための最小限の Python コードです。

import sys
from collections import defaultdict
fin = open(sys.argv[1])

dict = defaultdict(list)

for line in fin:
    parts = line.split()
    dict[parts[0]].append(parts[1])

タイミング:

time ./read.py largefile.txt
real    0m55.746s

ただし、次のように I/O バウンドではありません。

time cut -f1 largefile.txt > /dev/null    
real    0m1.702s

行をコメントアウトすると、数秒dictかかり9ます。ほぼすべての時間を に費やされているようdict[parts[0]].append(parts[1])です。

これをスピードアップする方法はありますか？それが大きな違いを生むのであれば、私は cython や C を使ってもかまいません。それともパンダがここで助けてくれますか?

サイズが 10000000 行のファイルのプロファイル出力を次に示します。

python -m cProfile read.py test.data         20000009 function calls in 42.494 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 bisect.py:1(<module>)
        1    0.000    0.000    0.001    0.001 collections.py:1(<module>)
        1    0.000    0.000    0.000    0.000 collections.py:25(OrderedDict)
        1    0.000    0.000    0.000    0.000 collections.py:386(Counter)
        1    0.000    0.000    0.000    0.000 heapq.py:31(<module>)
        1    0.000    0.000    0.000    0.000 keyword.py:11(<module>)
        1   30.727   30.727   42.494   42.494 read.py:2(<module>)
 10000000    4.855    0.000    4.855    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
 10000000    6.912    0.000    6.912    0.000 {method 'split of 'str' objects}
        1    0.000    0.000    0.000    0.000 {open}

アップデート。 parts[1] は整数で、parts[0] は短い固定長の文字列であると想定できます。

キーごとに 1 つの値しか取得できないため、私の偽のデータはあまり良くありません。これがより良いバージョンです。

perl -E 'say int rand 1e7, $", int rand 1e4 for 1 .. 1e7' > largefile.txt

ここで行う唯一の操作は、キーにクエリを実行して、それに関連付けられた値のリストを返すことです。

4

4 に答える 4

4

ここに私が得ることができたいくつかの簡単なパフォーマンスの改善があります:

dictの代わりにプレーンを使用しdefaultdict、 に変更d[parts[0]].append(parts[1])するとd[parts[0]] = d.get(parts[0], []) + [parts[1]]、時間が 10% 短縮されます。Python 関数へのこれらすべての呼び出しを排除しているのか__missing__、リストをその場で変更していないのか、それとも功績に値する何か他のものなのか、私にはわかりません。

代わりにsetdefaultプレーンで使用するだけで、時間が 8% 短縮されます。これは、インプレースの追加ではなく、追加の辞書作業であることを意味します。dictdefaultdict

一方、 を に置き換えるsplit()とsplit(None, 1)9% の効果があります。

CPython 2.7.2 の代わりに PyPy 1.9.0 で実行すると、時間が 52% 短縮されました。PyPy 2.0b は 55% です。

PyPy を使用できない場合、CPython 3.3.0 は時間を 9% 短縮します。

64 ビットではなく 32 ビット モードで実行すると、時間が 170% 増加しました。これは、32 ビットを使用している場合は切り替えた方がよいことを意味します。

dict が保存するのに 2GB を超える (32 ビットではわずかに少ない) という事実は、おそらく問題の大きな部分です。唯一の現実的な代替手段は、すべてをディスクに保存することです。(実際のアプリでは、おそらくメモリ内キャッシュを管理したいでしょうが、ここでは、データを生成して終了するだけなので、作業が簡単になります。) これが役立つかどうかは、いくつかの要因に依存します。SSD を搭載した RAM が少ないシステムでは速度が上がると思いますが、5400rpm のハード ドライブと 16GB の RAM (現在使用しているラップトップのような) を搭載したシステムでは速度が向上しません。ただし、システムのディスクキャッシュなどによっては、テストせずに知っている人もいます。

文字列のリストをディスクベースのストレージに保存するための簡単で汚い方法はありません (shelveおそらく、節約するよりも酸洗いと酸洗解除でより多くの時間を浪費するでしょう) gdbm。ほぼ同時に、データを複数回使用したい場合は、それらを永続的に保存するという良い副作用があります。残念ながら、dbmデフォルトのページ サイズはこれほど多くのエントリに対して小さすぎ、Python インターフェースにはデフォルトをオーバーライドする方法がないため、普通の方法では機能しません。

一意でない Key 列と Value 列だけを持つ単純な sqlite3 データベースに切り替えて実行すると、:memory:約 80% 長くかかりましたが、ディスクでは 85% 長くかかりました。各キーに複数の値を格納するために物事を非正規化しても役に立たず、実際には事態を悪化させるのではないかと思います。(それでも、多くの実際の使用では、これがより良い解決策になる可能性があります。)

cProfile その間、メインループをラップします：

         40000002 function calls in 31.222 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1   21.770   21.770   31.222   31.222 <string>:2(<module>)
 20000000    2.373    0.000    2.373    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
 20000000    7.079    0.000    7.079    0.000 {method 'split' of 'str' objects}

つまり、これは に費やされた時間の 3 分の 1、 に費やされた時間のstring.split10% でappendあり、残りは見えないコードに費やされています。これには、ファイルとメソッド呼び出しcProfileの両方が含まれます。defaultdict

通常の に切り替えるdictとsetdefault(少し速かったことを思い出してください)、 で 3.774 秒が費やされsetdefaultていることがわかります。これは、時間の約 15%、またはおそらくdefaultdictバージョンの約 20% です。おそらく、この方法は以前の方法よりも__setitem__悪くなることはありません。setdefaultdefaultdict.__getitem__

ただし、ここでは malloc 呼び出しによって請求される時間が表示されない可能性があり、それらがパフォーマンスの大きな部分を占めている可能性があります。それをテストするには、C レベルのプロファイラーが必要です。それでは話を戻しましょう。

一方、残りの時間の少なくとも一部は、おそらく行分割にも費やされます。これは、スペース分割と同じ順序でコストがかかるからですよね? しかし、それを大幅に改善する方法はわかりません。

最後に、ここでは C レベルのプロファイラーが役に立ちますが、私のシステムで 1 つ実行しても、あなたのシステムにはあまり役に立たないかもしれません。

私のシステムで最速のバージョンは、実行する Python によって異なりますが、次のいずれかです。

d = {}    
for line in fin:
    parts = line.split(None, 1)
    d[parts[0]] = d.get(parts[0], []) + [parts[1]]

またはこれ：

d = {}    
for line in fin:
    parts = line.split(None, 1)
    d.setdefault(parts[0], []).append(parts[1])

…そして、彼らはお互いにかなり近いです。

ほぼ同じ速度で、明らかな長所と短所がある gdbm ソリューションは、次のようになります。

d = gdbm.open(sys.argv[1] + '.db', 'c')
for line in fin:
    parts = line.split(None, 1)
    d[parts[0]] = d.get(parts[0], '') + ',' + parts[1]

(明らかに、これを繰り返し実行できるようにする場合は、既存のデータベースを削除する行を追加する必要があります。または、ユース ケースに適合する場合は、タイムスタンプを入力ファイルのタイムスタンプと照合してスキップする行を追加する必要があります。すでに最新の場合はループ全体。)

于 2013-08-06T17:55:51.217 に答える
3

これは、興味のある人のための簡単な C バージョンです。私のマシンのヘッドライン時間:

Python (>5Gb メモリ)

time ./read.py  largefile.txt

real    0m48.711s
user    0m46.911s
sys     0m1.783s

C (~1.9Gb メモリ)

gcc -O3 read.c -o read
time ./read largefile.txt

real    0m6.250s
user    0m5.676s
sys     0m0.573s

したがって、Cでは約7.8倍高速です:)

また、コマンドを次のように変更しないと、私のバージョンの seq では使用可能なリストが作成されないことを付け加えておきます。

paste <(seq -f "%.0f" 20000000) <(seq -f "%.0f" 2 20000001)  > largefile.txt

以下のコードは、C プログラミング言語のセクション 6.6 から dict の例を彼の例にコピーした Vijay Mathew の功績によるものです (私は以下の回答にコピーしました): C で辞書を実装する簡単な方法

====== 編集 ====== (13/08/2013)

私の回答のコメント #2 に続いて、コードをコード リスト 2 のコードに更新して、1 つのキーに複数の値を許可し、更新された perl コードを使用してテスト ファイルを生成し始めました (したがって、半分のサイズです)。約半分の実行時間)。

見出しの時間は次のとおりです。

Python (>5Gb メモリ)

time ./read.py  largefile.txt

real    0m25.925s
user    0m25.228s
sys     0m0.688s

C (~1.9Gb メモリ)

gcc -O3 read.c -o read
time ./read largefile.txt

real    0m3.497s (although sub 3 seconds is possible by reducing the hash size?!?!?)
user    0m3.183s
sys     0m0.315s

パンダはおそらく近いですが、Cでは約7.4倍高速です。

ただし、ハズサイズの点は重要です。ハッシュサイズを非常に小さな数に減らすことで「ごまかす」ことができました。これにより、多値辞書の場合、ルックアップを犠牲にして挿入速度が向上します。したがって、これらの実装のいずれかを実際にテストするには、ルックアップ速度もテストする必要があります。

コード 2 (多値辞書)

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

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

#define HASHSIZE 10000001
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
      hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

struct nlist * lookup_all(char *key)
{
    struct nlist *np, *np2, *ret;
    unsigned hashval = hash(key);

    ret = NULL;

    for (np = hashtab[hashval]; np != NULL; np = np->next) {
      if (strcmp(key, np->name) == 0) {
        np2 = malloc(sizeof(*np2));
        np2->name = np->name;
        np2->defn = np->defn;
        np2->next = ret;
        ret = np2;
      }
    }
    return ret; /* not found */
}

/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np, *np2;
    unsigned hashval = hash(name);;
    //if ((np = lookup(name, hashval)) == NULL) { /* not found */

    np = (struct nlist *) malloc(sizeof(*np));
    if (np == NULL || (np->name = strdup(name)) == NULL)
      return NULL;
    np->next = hashtab[hashval];
    hashtab[hashval] = np;

    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}
#ifdef STRDUP
char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for .\0. */
    if (p != NULL)
       strcpy(p, s);
    return p;
}
#endif /* STRDUP */

int main(int argc, char *argv[]) {

    FILE *fp;
    char str1[20];
    char str2[20];
    int size = 0;
    int progress = 0;
    struct nlist *result;

    fp = fopen(argv[1],"r");
    if(fp==NULL) {return 1;}

    fseek(fp, 0, SEEK_END);
    size = ftell(fp);
    rewind(fp);

   while(size != ftell(fp)) {
        if(0==fscanf(fp, "%s %s",str1,str2))
            break;
        (void)install(str1,str2);
    }
    printf("Done\n");
    fclose(fp);

    // Test a lookup to see if we get multiple items back.    
    result = lookup_all("1");
    while (result) {
        printf("Key = %s Value = %s\n",result->name,result->defn);
        result = result->next;
    }

    return 0;
}

コード 1 (単一値辞書)

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

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

#define HASHSIZE 10000001
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
      hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
          return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}
#ifdef STRDUP
char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for .\0. */
    if (p != NULL)
       strcpy(p, s);
    return p;
}
#endif /* STRDUP */

int main(int argc, char *argv[]) {

    FILE *fp;
    char str1[20];
    char str2[20];
    int size = 0;
    int progress = 0;

    fp = fopen(argv[1],"r");
    if(fp==NULL) {return 1;}

    fseek(fp, 0, SEEK_END);
    size = ftell(fp);
    rewind(fp);

   while(size != ftell(fp)) {
        if(0==fscanf(fp, "%s %s",str1,str2))
            break;
        //printf(">%s<>%s<\n",str1,str2);
        (void)install(str1,str2);
        ++progress;
        if((progress % 100000)==0)
            printf("Progress = %d\n",progress);
    }
    printf("Done\n");
    fclose(fp);

    return 0;
}
于 2013-08-09T13:43:13.703 に答える
0

他の最適化の上に追加の最適化を追加することもできます。

キーは「ほぼ」連続した整数の文字列であるため、辞書に要素を順番に挿入することにより、辞書の作成を高速化できます。辞書の衝突を減らします。Python dict の実装に関するコメントを参照してください

今後の主な微妙な点: ほとんどのハッシュ スキームは、ランダム性をシミュレートするという意味で、「優れた」ハッシュ関数を持つことに依存しています。Python はそうではありません: その最も重要なハッシュ関数 (文字列と int 用) は、一般的なケースでは非常に規則的です:

map(ハッシュ, (0, 1, 2, 3)) [0, 1, 2, 3] map(ハッシュ, ("namea", "nameb", "namec", "named")) [-1658398457, - 1658398460、-1658398459、-1658398462]

これは必ずしも悪いことではありません！反対に、サイズが 2**i のテーブルでは、下位 i ビットを最初のテーブル インデックスとして使用することは非常に高速であり、int の連続した範囲によってインデックス付けされた dict の衝突はまったくありません。キーが「連続した」文字列の場合もほぼ同じです。したがって、これにより、一般的なケースでランダムよりも優れた動作が得られます。これは非常に望ましいことです。

したがって、ファイルを前処理して並べ替えることができれば、Python の実行ははるかに高速になります。

于 2013-08-18T07:06:38.917 に答える