arrays - 在 Perl 中检查一行中重复列的最快方法

Question

我有一个像这样有 100 万行的文件

aaa,111
bbb,222
...
...
a3z,222 (line# 500,000)
...
...
bz1,444 (last line# 1 million)

我需要检查的是逗号后的第二个值是否唯一。如果没有，则打印出行号。在上面的示例中，它应该打印出来

Duplicate: line: 500000 value: a3z,222

为此，我使用 perl 并将第二列的值存储在数组中。如果我在数组中找不到值，我会将其添加到其中。如果该值已经存在，那么我将其打印为副本。

问题是我使用的逻辑非常慢。完成任何地方都需要 2-3 小时。有什么办法可以加快速度吗？如果不需要，我不想创建数组。我只想检查文件第 2 列中的重复值。

如果有一种更快的方法可以在批处理文件中完成此操作，我愿意接受。

这是我的工作代码。

# header
use warnings;
use DateTime;
use strict;
use POSIX qw(strftime);
use File::Find;
use File::Slurp;
use File::Spec;
use List::MoreUtils qw(uniq);

print "Perl Starting ... \n\n"; 

# Open the file for read access:
open my $filehandle, '<', 'my_huge_input_file.txt';

my $counter = 0;
my @uniqueArray;
# Loop through each line:
while (defined(my $recordLine = <$filehandle>))
{

  # Keep track of line numbers
  $counter++;


  # Strip the linebreak character at the end.
  chomp $recordLine;

  my @fields = split(/,/, $recordLine);
  my $val1=$fields[0]; 
  my $val2=$fields[1]; 

  if ( !($val2 ~~ @uniqueArray) && ($val2 ne "") )
  {
        push(@uniqueArray, $val2);
  }
  else
  {
    print ("DUP line: $counter - val1: $val1 - val2: $val2 \n");
  }

}

print "\nPerl End ... \n\n"; 

Answer 1

这就是哈希的用途之一

use feature qw(say);

...

my %second_field_value;

while (defined(my $recordLine = <$filehandle>))
{
    chomp $recordLine; 
    my @fields = split /,/, $recordLine;

    if (exists $second_field_value{$fields[1]}) {
        say "DUP line: $. -- @fields[0,1]";
    }
    ++$second_field_value{$fields[1]};
}

这将累积该字段的所有可能值，这是必须的。我们还可以在发现受骗者时存储有关受骗者的适当信息，具体取决于需要报告的内容。

(最后读取的文件句柄的)行号可在 $. variable 中找到。 ;不需要$counter。

请注意，检查和标志/计数器设置可以在一个表达式中完成，例如

if ($second_field_values{$fields[1]}++) { say ... }  # already seen before

这是检查重复项时的惯用语。感谢池上提出来。这是通过 post-increment 来实现的在条件中(因此检查是使用旧值完成的，并且计数在 block 中是最新的)。

我还必须评论智能匹配运算符 (~~)。人们普遍认为，它目前的形式存在很大问题，而且几乎可以肯定它会遭受重大变化，甚至更糟。因此，简单地说，我会说:不要使用它。带有它的代码很有可能在未来某个未指定的时刻被破坏，可能没有警告，也可能悄无声息。

<小时/>

评论中提出的有关性能和“计算复杂性”的说明。

在每一行搜索数组的复杂度为 O(n m)(n 行，m 值)，这里实际上是 O(n²)，因为数组在每一行都会获取一个新值(所以m = n-1)；此外，(实际上)每一行都会搜索整个数组，因为通常不会出现重复。对于哈希，复杂性为 O(n)，因为我们对每行进行恒定时间查找。

最重要的是，所有这些都与输入的大小有关。对于几百行的文件，我们无法区分。对于一百万行，报告的运行时间对于数组来说是“2-3 小时”，对于散列来说是“5 秒以下”。

“复杂性”评估涉及输入大小这一事实具有实际意义。

首先，使用粗心构建的“运行良好”算法的代码可能会因意外的大输入而严重崩溃，或者更确切地说，一旦进入生产运行，就会因实际数据而严重崩溃。

另一方面，当我们了解其用例时，使用更干净、更简单的代码运行通常会非常令人满意，即使它的“复杂性”更差。

通常，复杂性告诉我们运行时如何依赖于大小，而不是它到底是什么。因此，O(n²) 算法可能比 O(n) 算法运行得更快em> log n) 一个用于足够小的输入。这具有重要的实际意义，在算法选择中得到广泛应用。