☰

最大化数据集的覆盖范围

tag-icon • tag-icon perl database
最大化数据集的覆盖范围

我有以下格式的数据集。字段 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 个标识符时，它能够告诉我哪些 X 标识符将非冗余地覆盖最大数量的数据点（但在可能的情况下优先考虑冗余覆盖，例如 id5 将无论如何，始终选择 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 更容易被选择。

我的数据集包括约 1200 万个标识符和约 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 的计数哈希更新为等于不在输出集中的数据点的数量加上等于输出集中的数据点的数量的小数部分（以便 ids更多的冗余数据点的排序高于那些较少或没有数据点的数据点）。

这本质上是您在评论中描述为“笨拙”的算法。我更喜欢将其视为“直接”或“暴力”:-)

我尝试了几种不同的优化方法，但无法找到更有效的方法。这并不一定意味着没有。这只是意味着我找不到它。主要困难是需要对具有更多冗余数据点的 ids 进行优先级排序。

无论如何，我没有包含数百万条目的输入文件，所以我无法进行任何计时测试。我有兴趣知道它在完整数据集下运行的速度有多快。以及如果您使用 MLDBM 或类似的产品（如下所述）它的性能如何。

该脚本将使用大量 RAM。如果您有 1200 万个 ID，它将使用大约12 MB * (the average id string length + the average data points length per id).如果您的可用 RAM 少于 32GB 甚至 64GB，这可能会成为问题。

如果脚本确实超出了您的可用 RAM 并导致交换抖动，您可以使用MLDB模型模块或其中之一Tie::，用于将 %ids 哈希（也可能是 %counts 哈希）存储在数据库而不是内存中。例如 领带::DBI使用 sqlite 或 mysql 或 postgresql 等数据库。

使用MLDBM或Tie::模块可能不会更快（尽管可能会更快，因为它不会破坏 RAM 和交换），但是 a) 脚本在完成之前由于内存不足而死亡的可能性要小得多，并且 b)它对系统上运行的其他进程的危害要小得多（否则这些进程可能会因内存不足而被终止）。

my %ids=()例如，在和行之后立即添加以下内容，my %counts=()以将 Berkeley DB 文件用于 %ids：

       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_points）表明我最初对内存使用情况的猜测是完全错误的。

将这些数据集加载到 RAM 中大约需要 23 分钟（这只是加载数据文件而不对其进行处理），并且在我的 Phenom II 1090T 上消耗了 1GB RAM（安装了 32GB RAM，但只有大约 8GB 可用空间）。

使用MLDBM 加载数据文件大约需要21 分钟。它创建了一个ids.db323MB 和counts.db78MB 的文件。这样做时它使用了恒定的 9.3MB RAM。

因此，我猜测您的数据文件至少是该大小的 10-20 倍，因此不太可能适合 RAM。使用 MLDBM，最好在 NVME SSD 上使用，以获得最佳性能。

既然您请求了，这里是脚本的更新版本。也许你可以从中提取一些有用的想法。

它的速度至少是以前版本的两倍。只需 15 分钟即可读取 145MB 的测试文件，还可以对其进行处理并生成 12 个标识符的结果 - 我通过其他优化尝试所能得到的最佳时间约为 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 任何此类过程都需要访问全部的数据集以产生任何有意义的输出。

这个任务是 I/O 密集型的，而不是 CPU 密集型的——它在计算上并不困难或“昂贵”，只是需要大量的时间（和内存）来读取和处理巨大的数据集。

别相信我的话，心想。我对你的数据或你想要做什么几乎一无所知。如果某人 a) 更好地理解您的数据集并且 b) 知道您想从中获取什么，则可能能够有效地分割您的数据，并且仍然能够合并结果集。

相关内容