perl - "fuse"不同指针指向的位置有什么好方法？

Question

我有许多指针指向内存中不同(或相同)的位置。我想实现一种机制，允许我们“融合”给定指针子集所指向的位置。

我现在使用的是 perl 5.6.1，但我愿意接受其他语言的实现。我在 perl 中想出了以下愚蠢的实现:

my $ref1 = \1;
my $ref2 = \2;
print "${$ref1} : ${$ref2}\n"; # <-- prints 1 : 2

fuse(\$ref1, \$ref2);          # <-- Make $ref2 point to same location as $ref1
print "${$ref1} : ${$ref2}\n"; # <-- prints 1 : 1 (which is correct)

sub fuse
{
    ${$_[1]} = ${$_[0]}; 
}

但是当我们必须多次融合时，这不会按预期工作:

my $ref1 = \1;
my $ref2 = \2;
my $ref3 = \3;
print "${$ref1} : ${$ref2} : ${$ref3}\n"; # <-- prints 1 : 2 : 3

fuse(\$ref1, \$ref2);                     # <-- Make $ref2 point to same location as $ref1
print "${$ref1} : ${$ref2} : ${$ref3}\n"; # <-- prints 1 : 1 : 3 (which is correct)

fuse(\$ref3, \$ref1);                     # <-- Make $ref1 point to same location as $ref3
print "${$ref1} : ${$ref2} : ${$ref3}\n"; # <-- prints 3 : 1 : 3 ($ref2 is useless now)

sub fuse
{
    ${$_[1]} = ${$_[0]}; 
}

在上面的示例中，我希望所有三个变量 $ref1、$ref2 和 $ref3 最终都指向一个位置其中包含 3。

有没有一种好方法可以完成这种“融合”，而无需手动重新分配我们想要更改其所指对象的每个指针？

上下文:
我正在尝试模拟一个电路(有电线)。当两个节点通过电线连接时，两个节点的属性之一(比如说电压)变得相同。当这些节点之一连接到第三个节点(用电线)时，所有三个节点上的电压都会变得相同，无论它们之前的值是什么，并且只要连接存在就继续保持相同。

我尝试在谷歌上搜索 HDL 如何实现连线，但失败了(我可能不知道该谷歌什么)。

Answer 1

我相信

• 您希望能够将一个融合集的任何部分与另一个融合集的任何部分融合。
• 您希望能够设置值，以便更新融合集的每个部分。

这意味着以下程序定义了预期的行为:

use strict;
use warnings qw( all );
use feature qw( say );
use FindBin qw( $RealBin );
use lib $RealBin;

use Wire qw( );

my $o1 = Wire->new( voltage => 1 );
my $o2 = Wire->new( voltage => 2 );
my $o3 = Wire->new( voltage => 3 );
my $o4 = Wire->new( voltage => 4 );
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4;  # 1 2 3 4

$o2->fuse($o1);
$o3->fuse($o4);
$o1->fuse($o3);
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4;  # 4 4 4 4

$o1->set_voltage(5);
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4;  # 5 5 5 5

$o3->set_voltage(6);
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4;  # 6 6 6 6

这个类实现了:

package Wire;

use strict;
use warnings qw( all );

sub new {
   my ($class, %args) = @_;
   my $voltage = $args{voltage} // 0;
   my $self = bless({}, $class);
   $self->{shared_voltage} = { value => $voltage, backrefs => [] };
   push @{ $self->{shared_voltage}{backrefs} }, \( $self->{shared_voltage} );
   return $self;
}

sub get_voltage { $_[0]{shared_voltage}{value} }
sub set_voltage { $_[0]{shared_voltage}{value} = $_[1]; }

sub fuse {
   my ($self, $new) = @_;
   my $old_sv = $self->{shared_voltage};  my $old_sv_br = $old_sv->{backrefs};
   my $new_sv = $new->{shared_voltage};   my $new_sv_br = $new_sv->{backrefs};
   for my $backref (@$old_sv_br) {
      $$backref = $new_sv;
      push @$new_sv_br, $backref;
   }
}

sub DESTROY {
   my ($self) = @_;
   @{ $self->{shared_voltage}{backrefs} } =
      grep { $_ != \( $self->{shared_voltage} ) }
         @{ $self->{shared_voltage}{backrefs} };
}

1;

结果是通过将融合节点的引用列表与共享值一起存储来实现的。这与 Perl 中的 Copy-on-Write 字符串使用的方法相同。融合的结构如下所示:

+-$o1--+             +-Wire----------------+
| Ref -------------->| +-shared_voltage--+ |               +-anon hash------+
+------+   +---------->| Reference      ------------------>| +-value------+ |
           |         | +-----------------+ |   / / /       | | 4          | |
           |         +---------------------+   | | |       | +-backrefs---+ |
           |                                   | | |       | | Reference -------+
           |                                   | | |       | +------------+ |   |
+-$o2--+   |         +-Wire----------------+   | | |       +----------------+   |
| Ref -----(-------->| +-shared_voltage--+ |   | | |                            |
+------+   | +-------->| Reference      -------+ | |   +------------------------+
           | |       | +-----------------+ |     | |   |
           | |       +---------------------+     | |   |   +-anon array-----+
           | |                                   | |   +-->| +-0----------+ |
           | |                                   | |       | | Reference -------------+
+-$o3--+   | |       +-Wire----------------+     | |       | +-1----------+ |         |
| Ref -----(-(------>| +-shared_voltage--+ |     | |       | | Reference -----------+ |
+------+   | | +------>| Reference      ---------+ |       | +-2----------+ |       | |
           | | |     | +-----------------+ |       |       | | Reference ---------+ | |
           | | |     +---------------------+       |       | +-3----------+ |     | | |
           | | |                                   |       | | Reference -------+ | | |
           | | |                                   |       | +------------+ |   | | | |
+-$o4--+   | | |     +-Wire----------------+       |       +----------------+   | | | |
| Ref -----(-(-(---->| +-shared_voltage--+ |       |                            | | | |
+------+   | | | +---->| Reference      -----------+                            | | | |
           | | | |   | +-----------------+ |                                    | | | |
           | | | |   +---------------------+                                    | | | |
           | | | |                                                              | | | |
           | | | |                                                              | | | |
           | | | +--------------------------------------------------------------+ | | |
           | | +------------------------------------------------------------------+ | |
           | +----------------------------------------------------------------------+ |
           +--------------------------------------------------------------------------+

(反向引用的顺序未准确表示。)

我想你会发现这在实践中比 your solution 快得多。就像你的一样，融合的复杂度是 O(N)。然而，获取和设置电压的时间复杂度为 O(1)，而不是 O(N)。虽然对象销毁是 O(N) 而不是我的 O(1)，但可以通过使用哈希而不是反向引用数组来使其变为 O(1)。就是这样说的。作为数组，它实际上可能更快。这就是 Perl 对 CoW 字符串所做的事情。 N 是熔断器的大小(在我们的测试用例中为 4)。