时间戳

首页 > 解决方案 > 什么是“融合”不同指针指向的位置的好方法？

perl - 什么是“融合”不同指针指向的位置的好方法？

问题描述

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

我现在正在使用 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 如何实现电线的尝试失败了（我可能不知道用谷歌搜索什么）。

标签： perlpointersmemoryreferencehdl

解决方案

我几乎放弃了，然后偶然发现了这个奇妙的东西，称为不相交集数据结构，它似乎是为了解决这个确切的问题而发明的。以下是我使用的代码：

use Scalar::Util qw( weaken );

my $ref1 = {}; $ref1->{voltage} = 1; weaken( $ref1->{parent} = $ref1 );
my $ref2 = {}; $ref2->{voltage} = 2; weaken( $ref2->{parent} = $ref2 );
my $ref3 = {}; $ref3->{voltage} = 3; weaken( $ref3->{parent} = $ref3 );
my $ref4 = {}; $ref4->{voltage} = 4; weaken( $ref4->{parent} = $ref4 );

print "@{[map(get_vol($_), ($ref1, $ref2, $ref3, $ref4))]}\n";
# Above line print 1 2 3 4

fuse($ref1, $ref2); # <-- Second argument gets set to first
print "@{[map(get_vol($_), ($ref1, $ref2, $ref3, $ref4))]}\n";
# Above line print 1 1 3 4

fuse($ref4, $ref3);
set_vol($ref3, 5);
print "@{[map(get_vol($_), ($ref1, $ref2, $ref3, $ref4))]}\n";
# Above line print 1 1 5 5

fuse($ref2, $ref3);
set_vol($ref3, 7);
print "@{[map(get_vol($_), ($ref1, $ref2, $ref3, $ref4))]}\n";
# Above line print 7 7 7 7


sub fuse
{
    my ($node1, $node2) = ($_[0], $_[1]);
    $node2 = $node2->{parent} while ($node2->{parent} != $node2);
    $node2->{parent} = $node1;
}

sub get_vol
{
    my $node = shift;
    $node = $node->{parent} while ($node != $node->{parent});
    return $node->{voltage};
}

sub set_vol
{
    my $node = shift;
    $node = $node->{parent} while ($node != $node->{parent});
    $node->{voltage} = shift;
}

在此之后，设置任何$refs usingset_vol将反映在get_vol所有其他$refs 的输出中。

显然，我们可以在读取和设置电压方面添加其他优化，这样我们在读取或写入某些节点时就不必遍历整个树。

更新：以下使用上面的简单原理，但避免了不使用的内存泄漏weaken，并优化了电压查找（因此只有熔丝后的第一次查找“慢”）。

package Wire;

use strict;
use warnings qw( all );

sub new {
   my ($class, %args) = @_;
   my $voltage = $args{voltage} // 0;
   my $self = bless({}, $class);
   $self->{voltage_indirect_chain} = { next => undef, value => $voltage };
   return $self;
}

sub _tail {
   my ($self) = @_;
   $self->{voltage_indirect_chain} = $self->{voltage_indirect_chain}{next}
      while $self->{voltage_indirect_chain}{next};

   return $self->{voltage_indirect_chain};
}

sub get_voltage { $_[0]->_tail()->{value} }
sub set_voltage { $_[0]->_tail()->{value} = $_[1]; }

sub fuse {
   my ($self, $new) = @_;
   my $tail = $self->_tail();
   delete $tail->{value};
   $tail->{next} = $new->_tail();
}

1;

推荐阅读