4

どちらも整数の 2 つの列を含む単純なテキスト ファイルがあります。

1 5
1 12
2 5
2 341
2 12

等々..

出力が次のようになるように、データセットを 2 番目の値でグループ化する必要があります。

5 1 2
12 1 2
341 2

問題は、ファイルのサイズが約 34 Gb と非常に大きいことです。値を整数の配列として辞書にグループ化する Python スクリプトを作成しようとしましたが、それでも時間がかかりすぎます。array('i')( の割り当てと拡張にはかなりの時間がかかると思いappendます。

現在、疑似分散 Hadoop マシン (Amazon EC3 High Memory Large インスタンス) で実行する予定の豚スクリプトを作成する予定です。

data = load 'Net.txt';
gdata = Group data by $1; // I know it will lead to 5 (1,5) (2,5) but thats okay for this snippet
store gdata into 'res.txt';

これを行う簡単な方法があれば知りたいと思いました。

更新: このような大きなファイルをメモリに保持することは問題外です。Python ソリューションの場合、最初の実行で 4 回の実行を計画しました。1 から 1000 万の 2 番目の col 値のみが次の実行で考慮されます。1000 万から 2000 万などが考慮されます。しかし、これは本当に遅いことが判明しました。

pig / hadoop ソリューションは、すべてをディスク上に保持するため興味深いものです [ほとんどの場合]。

理解を深めるために、このデータセットには約 4,500 万人の Twitter ユーザーの接続に関する情報が含まれており、ファイル内の形式は、2 番目の数値で指定されたユーザー ID が最初の数値の後に続くことを意味します。

私が使用したソリューション：

class AdjDict(dict):
    """
     A special Dictionary Class to hold adjecancy list
    """
    def __missing__(self, key):
        """
        Missing is changed such that when a key is not found an integer array is initialized
        """
        self.__setitem__(key,array.array('i'))
        return self[key]

Adj= AdjDict()

for line in file("net.txt"):
    entry =  line.strip().split('\t')
    node = int(entry[1])
    follower = int(entry[0])
    if node < 10 ** 6:
        Adj[node].append(follower)

# Code for writting Adj matrix to the file:
4

5 に答える 5

2

1 行あたり最大 17 文字 (計算を簡単にするためにランダムに選んだ数字) であると仮定すると、このファイルには約 20 億のレコードがあります。64 ビット システムで大量の物理メモリを使用して実行していない限り、これらすべてを 1 つの dict でメモリに保持しようとすると、ページファイルがスラッシングされます。そして、それをデータ構造として読み込むだけです。この構造が構築された後、実際に何かを行うことを計画していると思われます。

このような単純なデータ形式では、Python ではなく C で何かを行う方がよいと思います。このデータのクラックは難しくなく、値ごとのオーバーヘッドははるかに少なくなります。少なくとも、20 億個の 4 バイト整数を保持するだけでも 8 Gb になります (現在 1 および 2 としてリストされている値の可能な範囲についていくつかの単純化した仮定を行うことができない限り、それらが 1 バイトまたはショートに収まる場合、次に、より小さな int 変数を使用できます。これは、このサイズのデータ​​ セットには苦労する価値があります)。

于 2010-08-04T08:47:49.557 に答える
1

私にも同様の要件があり、5（1,5）（2,5）の冗長性を削除するには、もう1つの豚のステートメントが必要です。

a = LOAD 'edgelist' USING PigStorage('\t') AS (user:int,following:int);
b = GROUP a BY user;
x = FOREACH b GENERATE group.user, a.following;
store x INTO 'following-list';
于 2011-03-26T06:40:34.537 に答える
1

34 GB のファイルを扱っている場合、ストレージとアクセス時間の両方の観点から、ハード ドライブは問題にならないと思います。ペアを順番に読み取り、ペア (x,y) を見つけたら、ファイル "x" を開き、" y" を追加して、ファイル "x" を閉じますか? 最終的に、Twitter ユーザー ID ごとに 1 つのファイルが作成され、各ファイルにはこのユーザーが接続されているすべてのユーザーが含まれます。指定した出力形式で結果を取得したい場合は、これらすべてのファイルを連結できます。

そうは言っても、私は本当に次のように考えています：（a）そのような大規模なデータセットの場合、正確な解像度は適切ではなく、（b）おそらく接続性を測定するためのより良い方法があるので、おそらくあなたは私たちに教えてくださいあなたの最終目標。

実際、非常に大きなグラフがあり、巨大なグラフの形状と特性を調べるために多くの効率的な手法が考案されています。これらの手法のほとんどは、ストリーミングのオンライン アルゴリズムとして機能するように構築されています。

たとえば、トライアングル カウントと呼ばれる手法を確率論的カーディナリティ推定アルゴリズムと組み合わせると、グラフに含まれるクリークに関する情報が効率的かつ迅速に提供されます。三角形のカウントの側面と、それがグラフにどのように関連するかについてのより良いアイデアについては、たとえば、この (ランダムに選択された)記事を参照してください。

于 2010-08-04T14:26:28.783 に答える
1

現在のハードウェアでこれを解決する必要がある場合、おそらくいくつかの小さなプログラムを作成します。

1 つ目は、ファイルの 500 メガバイトのチャンクで動作し、列を交換して結果を新しいファイルに書き込みます。(70 以上を取得します。) (これは多くのメモリを必要としません。)

sort(1)次に、小さなファイルごとに OS が提供するものを呼び出します。(これには数ギガのメモリが必要になる場合があります。)

次に、70 個の奇数のサブファイルすべての行をマージするマージ ソート プログラムを作成します。(これは多くのメモリを必要としません。)

次に、並べ替えられた大きなリストを処理するプログラムを作成します。次のような行がたくさんあります。

5 1
5 2
12 1
12 2

そして、あなたは返す必要があります：

5 1 2
12 1 2

(これは多くのメモリを必要としません。)

それをより小さなチャンクに分割することで、RSS を適切なマシンに適合するものに抑えることができれば幸いです。より多くのディスク I/O が必要になります。大きなプログラム。

于 2010-08-04T09:00:18.673 に答える
1

おそらく、ファイルをマルチパスで実行できます。

たとえば、100 の範囲サイズを選択した場合、ファイルを通過するキーの範囲を実行します。

1 回目のパス - 0 ～ 99 の
すべてのキーを計算します。2回目のパス -
100 ～ 199 のすべてのキーを計算します。3
回目のパス - 200 ～ 299 のすべてのキーを計算し
ます。等々。

サンプルの場合、最初のパスは出力します

5 1 2
12 1 2

そして4回目のパスは出力します

341 2

作成しているdictがRAMに収まるように範囲サイズを選択してください

マルチプロセッシングを使用して複数のコアを使用して高速化しようとすることはありません.非常に高速なハードドライブを使用していない限り、これはIOバウンドであり、ディスクをスラッシングするだけです.

于 2010-08-04T09:56:20.447 に答える