☰

データセットの適用範囲を最大化

tag-icon • tag-icon perl database
データセットの適用範囲を最大化

次の形式のデータセットがあります。フィールド１には識別子がリストされ、フィールド３にはデータポイントがリストされ、フィールド２にはデータポイントが計算される。

id1      5        E1, E2, E3, E4, E5
id2    4        E3, E4, E5, E6
id3 2        E6, E7
id4    1        E8
id5    2        E1, E8

X識別子に制限されているときに常にid4を選択する方法を知らせるスクリプトが必要です。また、データポイント全体がどの程度含まれているのか、どの識別子が含まれているのかを知りたいです。

私はPerlソリューションを好みますが、これが他の方法でよりよく達成される場合、それに限定されません。

X = 3識別子を選択した場合の出力例は次のとおりです。

id1, id3, id5    8/8        E1, E2, E3, E4, E5, E6, E7, E8

またはX = 2識別子を使用する場合：

id1, id3    7/8        E1, E2, E3, E4, E5, E6, E7

id1 は、それ自体が最も多くのデータポイントを含むので選択されます。 2番目のエントリはid2に含まれていますが、これらのデータポイントの1つだけを除いて、すべてid1に含まれています。 id3は次に最も多くのデータポイントを重複しないように扱うので、2番目の選択になります。 id4とid5はどちらも重複しないデータポイントを1つ追加しますが、id5は冗長データポイントを追加するため、id4よりも選択が簡単です。

私のデータセットには、約1,200万の識別子と約350万の重複しないデータポイントが含まれているため、スクリプトをできるだけきちんと実行できるようにするのが最善です（一部の識別子は最大9000のデータポイントに関連付けられています）。 Xで使用される実際の値は、X = 12からX = 40の間になると予想されます。

これは私の最初の質問であり（少なくとも私にとっては）かなり複雑な質問なので、私の質問を理解できるようにすべての内容をフォーマットして説明したいと思います。助けてくれてありがとう！

ベストアンサー1

#!/usr/bin/perl

use strict;
use Set::Tiny;

my $max = shift;

# A set to hold all unique data_points:
my $all_dps = Set::Tiny->new();
# hash of sets. key is id, val is the set of data_points for that id:
my %ids = ();
# hash containing the number of data_points for each id:
my %counts = ();

# read the input file, parse into %ids
while(<>) {
  chomp;
  my ($id,$count,$dp) = split /\s+/,$_,3;            #/
  $ids{$id} = Set::Tiny->new(split /\s*,\s*/, $dp);  #/
  # The "#/" commentS exists solely to fix U&Ls perl syntax highlighting
  $counts{$id} = $count;

  $all_dps = $all_dps->union($ids{$id});
};

my $total_dps = keys %{ $all_dps };

# array to hold the list of output ids:
my @idlist=();
# set to hold the output data points:
my $data_points = Set::Tiny->new();
# count of output data points:
my $dpcount=0;

# stop when id list is = max. or when the count of output data points is equal
# to he total data points. or when there are no non-empty keys left.
while ((@idlist < $max) && ($dpcount < $total_dps) && (keys %ids > 0)) {

  # sort the counts hash by value.
  my @counts = ( sort { $counts{$b} <=> $counts{$a} } keys %counts );

  # add the sets from the id with the highest count to the output set.
  $data_points = $data_points->union($ids{$counts[0]});
  # and add that id to the output id list
  push @idlist, $counts[0];
  $dpcount = keys %{ $data_points };

  foreach (keys %ids) {
    my $diff = $ids{$_}->difference($data_points);

    if (keys %{$diff} == 0) {
      # delete ids with no difference from the current data_points set.
      delete $ids{$_};
      delete $counts{$_};
    } else {
      # add the intersection count as a decimal fraction so ids with more
      # dupes sort slightly higher.
      my $intersection = $ids{$_}->intersection2($data_points);
      $counts{$_} = (keys %{$diff}) . "." .  (keys %{$intersection});
    };
  };
};

print join(",",@idlist) .  "\t$dpcount/$total_dps\t" .
  join(",",(sort keys %{ $data_points })) .  "\n";

スクリプトは最初に入力ファイル全体を読み込み、perlを使用します。コレクション::小さい「セット」（たとえば Perl ハッシュ）と各 ID のセット要素数を含むハッシュを構築するためのモジュールです。 Set::Tiny上記のCPANリンクで利用可能であるか、デプロイ用にすでにパッケージ化されている可能性があります（例：Debian：）sudo apt-get install libset-tiny-perl。

次に、次のように設定された可能な最大出力を繰り返し試みます。

  • %counts現在のハッシュを値で並べ替える
  • 出力セットに最大のセットを追加します（つまり、和集合）。
  • すべてのコレクション（および関連数）を削除いいえまだ出力セットにないデータポイントがあります。
  • 削除されていないIDの数ハッシュを更新して、出力セットにないデータポイントの数に出力セットのデータポイントの数に等しい分数を加えた値と等しくします（IDはもっと重複したデータポイントは、データポイントが少ないまたはないデータポイントよりもランクが高くなります。

これは、本質的にあなたの意見で「愚かだ」と説明したアルゴリズムです。私はそれを「直接的」または「暴力的」と考えることを好みます:-)

いくつかの他の最適化を試しましたが、より効率的なものが見つかりませんでした。それは必ずしもないという意味ではありません。ただ私がそれを見つけることができないことを意味します。最大の難点は、より重複したデータポイントでIDの優先順位を指定する必要があることです。

とにかく何百万ものエントリを含む入力ファイルがないため、タイミングテストを実行できません。完全なデータセットを使用してどれだけ早く実行されるかを知りたいです。 MLDBMなどの製品を使用している場合、パフォーマンスはどうなりますか（以下の説明を参照）。

このスクリプトは多くのRAMを使用します。 1,200万個のIDがある場合、12 MB * (the average id string length + the average data points length per id)約32GBまたは64GB未満の使用可能なRAMがある場合は問題になる可能性があります。

スクリプトが使用可能なRAMを超えてスワップスラッシングが発生した場合は、次のものを使用できます。MLDBモデルTie::メモリの代わりにデータベースに％idsハッシュ（および可能であれば％countsハッシュ）を格納するためのモジュールまたはそのいずれか。例えば タイ::DBIsqlite、mysql、postgresqlなどのデータベースを使用してください。

MLDBMあるいは、モジュールを使用する方が高速ではTie::ないかもしれませんが（RAMを破壊してスワップしないため、より速くなるかもしれませんが）a）スクリプトが完了する前にメモリ不足で終了する可能性がはるかに少なく、b）他のプロセスに役立ちます。 。システムで実行される方がはるかに少なく有害です（そうしないと、メモリ不足のためにこれらのプロセスが終了する可能性があります）。

my %ids=()my %counts=()たとえば、％idsでBerkeley DBファイルを使用するには、行の直後に次を追加します。

       use MLDBM qw(DB_File Storable);
       use Fcntl;
       my $id_db = tie %ids, 'MLDBM', './ids.db', O_CREAT|O_RDWR, 0640 or die $!;

おそらく、これは％countsハッシュをDBデータベースにバインドすることができます。

       my $count_db = tie %counts, 'MLDBM', './counts.db', O_CREAT|O_RDWR, 0640 or die $!;

出力例：

このスクリプトを保存しryan.plて実行可能にした後、chmod +x ryan.pl次のように実行しました。

$ ./ryan.pl 1 input.txt
id1     5/8   E1,E2,E3,E4,E5

$ ./ryan.pl 2 input.txt
id1,id3 7/8   E1,E2,E3,E4,E5,E6,E7

$ ./ryan.pl 3 input.txt
id1,id3,id5     8/8   E1,E2,E3,E4,E5,E6,E7,E8

U&Lでは見にくいですが、出力はタブで区切られています。

いくつかの予備テスト（100万行を含む145MBの入力ファイルを使用し、各行に1〜20個のランダム辞書ワードがdata_pointとして含まれている）では、メモリ使用量の初期推測が完全に間違っていることがわかりました。

これらのデータセットをRAMにロードするには約23分かかります（これは処理せずにデータファイルのみをロードします）。

MLDBMを使用してデータファイルをロードするのに約21分かかります。ids.db323MBと78MBのファイルを作成しましたcounts.db。同時に、9.3MBのRAMを継続的に使用します。

だから私の考えでは、データファイルのサイズはそのサイズの少なくとも10〜20倍なので、RAMに収まらないようです。最高のパフォーマンスを得るには、NVME SSDでMLDBMを使用することをお勧めします。

あなたが要求したので、更新されたスクリプトバージョンはここにあります。おそらくあなたはそれからいくつかの有用なアイデアを抽出できます。

以前のバージョンより少なくとも2倍速くなりました。 145MBのテストファイルを読み、処理し、12個の識別子の結果を生成するのに15分しかかかりませんでした。他の最適化試みで得られる最高時間は約33分でした。

私の考えでは、あなたが言及した104GBファイルのような非常に大きなデータセットにはまだ完全に不適切だと思います。

しかし、それでもやりたい場合は、2つのスクリプトに分割することをお勧めします。 1つは.dbファイル（ループを含むすべてwhile (<>)）を埋め、2番目のスクリプト（while (<>)ループの前のすべて、もちろんunlinkステートメントは含まれていない、ループの後のほとんどすべて）を埋め、.dbファイルのコピーを処理します。

これは、ランタイムの半分以上がテキストファイルを読み取り、それを.dbファイルに保存するためです。複数回実行する場合たくさん.dbファイルのコピーとコピーの処理は、毎回実行するたびに最初から作成するよりも高速です。

（データを処理するとき、スクリプトは％idsと％countsハッシュのエントリを変更して削除するため、コピーが必要です。コピーを処理すると、.dbファイルを起動条件にすばやくリセットできます。）

#!/usr/bin/perl

use strict;
use Set::Tiny;

# The first arg is the maximum number of identifiers we want.
# Any remaining args (and stdin) are input.
my $max = shift;

# hash of sets. key is id, val is the set of data_points for that id:
my %ids = ();

# hash containing the number of data_points for each id:
my %counts = ();

# The following two arrays exist to minimise memory usage, so that datapoints
# which appear in multiple IDs are stored in %id by reference rather than
# value.
#
# Array containing each datapoint indexed numerically
my @dp=();
# Hash containing each datapoint indexed by value
my %seen=();

use BerkeleyDB ;
use MLDBM qw(BerkeleyDB::Btree Storable);

# delete the .db files
unlink './ids.db';
unlink './counts.db';
unlink './seen.db';
unlink './dp.db';

# use MLDBM for the %ids hash - we need to serialise the Set::Tiny
# data structures.
tie %ids,    'MLDBM', -Filename => 'ids.db',    -Flags => DB_CREATE or die "Cannot open database 'ids.db': $!\n";

# It's faster to use BerkeleyDB directly for the other arrays (they
# contain scalar values, so there is no need for serialisation)
tie %counts, 'BerkeleyDB::Btree', -Filename => 'counts.db', -Flags => DB_CREATE or die "Cannot open database 'counts.db': $!\n";
tie %seen,   'BerkeleyDB::Btree', -Filename => 'seen.db',   -Flags => DB_CREATE or die "Cannot open database 'seen.db': $!\n";
tie @dp,     'BerkeleyDB::Recno', -Filename => 'dp.db',     -Flags => DB_CREATE or die "Cannot open database 'dp.db': $!\n";

my $total_dps=0;
# read the input file, parse into %ids
while(<>) {
  chomp;
  # split input line on spaces with max of 3 fields.
  my ($id,$count,$data) = split(/\s+/,$_,3);   #/

  # split $data by commas
  my @data = split(/\s*,\s*/, $data);          #/
  my $data_count = @data;
  my @data_by_idx = ();

  # convert @data to  @data_by_idx
  for (0..$#data) {
    if (!defined($seen{$data[$_]})) {
      # We haven't seen this datapoint before, so add it to both @dp
      # and %seen.
      $dp[++$total_dps] = $data[$_];
      $seen{$data[$_]}=$total_dps;
    };
    # add the datapoint's index number to @data_by_idx
    push @data_by_idx, $seen{$data[$_]};
  };
  $ids{$id} = Set::Tiny->new(@data_by_idx);

  $counts{$id} = $count;
};

# array to hold the list of output ids:
my @idlist=();
# set to hold the output data points:
my $data_points = Set::Tiny->new();
# count of output data points:
my $dpcount=0;

my $biggest_id='unknown';
my $biggest_count=0;

# stop when id list is = max. or when the count of output data points
# is equal to he total data points. or when there are no non-empty
# keys left.
while ((@idlist < $max) && ($dpcount < $total_dps) && (keys %ids > 0)) {

  # find the id with the most data points without using sort().
  if ($biggest_id eq 'unknown') {
    foreach (keys %counts) {
      if ($counts{$_} > $biggest_count) {
        $biggest_count = $counts{$_};
        $biggest_id = $_;
      };
    };
  };

  # add the sets from the id with the highest count to the output set.
  $data_points = $data_points->union($ids{$biggest_id});
  # and add that id to the output id list
  push @idlist, $biggest_id;
  $dpcount = keys %{ $data_points };

  $biggest_count=0;

  foreach (keys %ids) {
    my $diff = $ids{$_}->difference($data_points);

    if (keys %{$diff} == 0) {
      # delete ids with no difference from the current data_points set.
      delete $ids{$_};
      delete $counts{$_};
    } else {
      # add the intersection count as a decimal fraction so ids with more
      # dupes sort slightly higher.
      my $intersection = $ids{$_}->intersection2($data_points);
      $counts{$_} = (keys %{$diff}) . "." .  (keys %{$intersection});
      # find the new id with the most data points.
      if ($counts{$_} > $biggest_count) {
        $biggest_count = $counts{$_};
        $biggest_id = $_;
      };
    };
  };
};

print join(",",@idlist) .  "\t$dpcount/$total_dps\t";
print join (",", (map $dp[$_], keys %{ $data_points })), "\n";

コメントの他の質問（クラスタでマルチコア処理のためにデータを分割する方法）についてはわかりません。

私はこれがデータをシャーディングし、シャードを並列に処理し、結果を結合するのに適した作業だとは思わない。 AFAICT これらのプロセスにはアクセスが必要なためです。みんな意味のある結果を生成するデータセット。

これはCPU集約的ではなくI / O集約的です。計算が難しい、または「コストがかからない」、巨大なデータセットを読み取って処理するのに多くの時間（およびメモリ）が必要になるだけです。

私の言葉をそのまま受け入れないで、私は思った。私はあなたのデータやあなたが何をしたいのかについてほとんど知りません。 a）データセットをよりよく理解し、b）データから取得したいものが何であるかを知っている人がいる場合は、データを効率的に分割しながら結果セットをマージできます。

おすすめ記事