다음 형식의 데이터 세트가 있습니다. 필드 1에는 식별자가 나열되고, 필드 3에는 데이터 포인트가 나열되며, 필드 2에는 데이터 포인트가 계산됩니다.
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은 그 자체로 가장 많은 데이터 포인트를 포함하므로 선택됩니다. 두 번째 항목은 id2에 포함되지만 이러한 데이터 포인트 중 하나만 제외하고 모두 id1에 포함됩니다. id3은 다음으로 가장 많은 데이터 포인트를 중복되지 않게 다루므로 두 번째 선택이 됩니다. 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분이 소요되며(이는 처리하지 않고 데이터 파일만 로드함) 내 Phenom II 1090T에서 1GB의 RAM을 소비합니다(32GB의 RAM이 설치되었지만 약 8GB만 사용 가능).
MLDBM을 사용하여 데이터 파일을 로드하는 데 약 21분이 소요됩니다. ids.db323MB와 78MB의 파일을 생성했습니다 counts.db. 동시에 9.3MB의 RAM을 지속적으로 사용합니다.
그래서 제 생각에는 데이터 파일의 크기가 그 크기의 최소 10-20배이므로 RAM에 맞지 않을 것 같습니다. 최상의 성능을 위해서는 NVME SSD에서 MLDBM을 사용하는 것이 좋습니다.
귀하가 요청했기 때문에 업데이트된 스크립트 버전이 여기에 있습니다. 아마도 당신은 그것으로부터 몇 가지 유용한 아이디어를 추출할 수 있을 것입니다.
이전 버전보다 최소 2배 이상 빨라졌습니다. 145MB 테스트 파일을 읽고, 처리하고, 12개의 식별자에 대한 결과를 생성하는 데 15분 밖에 걸리지 않았습니다. 다른 최적화 시도에서 얻을 수 있는 최고 시간은 약 33분이었습니다.
제 생각에는 당신이 언급한 104GB 파일과 같은 매우 큰 데이터 세트에는 여전히 완전히 부적합하다고 생각합니다.
하지만 그래도 해보고 싶다면 두 개의 스크립트로 분할하는 것이 좋습니다. 하나는 .db 파일(루프를 포함한 모든 것 while (<>))을 채우고 두 번째 스크립트( 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) 데이터에서 얻고자 하는 것이 무엇인지 아는 사람이 있다면 데이터를 효율적으로 분할하면서도 결과 세트를 병합할 수 있습니다.