Set/hash 在 Perl 6 中使用自定义散列函数
Set/hash with custom hashing function in Perl 6
我的问题与有关,但我想我可以切入问题的核心:
如何选择特定的哈希函数?例如,如果我想做基于值的匹配而不是引用匹配,我想看看某个元组是否存在(或者干脆删除它):
my %data := SetHash.new: (1, 2), (3, 4);
%data{$(1, 2)}:delete; # False
在 C++ 或 C# 中,我可以为构造函数提供自定义 hashing/comparison 函数。在 C# 中,如果我的数据类型是 struct
(值类型而不是引用类型),则按值散列将自动发生。 Perl 6 在某种程度上对 Pair
(如果 Pair 不包含任何容器)进行值类型散列,但我不知道如何使其适用于任何其他复杂类型。
一方面,我明白为什么这不是最安全的操作——很容易定义其哈希码在插入后可以更改的对象。但这并没有阻止 .NET 和 C++ STL 允许自定义散列。
可能的 API 用法(受 this 启发的链式哈希逻辑,最初来自 Boost)是:
class MyHasher does Hasher of Array[Int] {
method get-hash-value(Int @array) {
reduce
-> $a, $b {$a +^ ($b + 0x9e3779b97f4a7c16 + ($a +< 6) + ($a +> 2))},
0,
|@array;
}
method equals(Int @a, Int @b) { @a eqv @b; }
}
my %data := SetHash.new(
my Int @=[1, 2], my Int @=[3, 4],
:hasher(MyHasher.new)
);
say %data{$[1, 2]}; # should be True
这将是 hasher 角色,它应该由 Perl 6 的核心库提供,如果它还不存在的话:
role Hasher[::T=Any] { method equals(T $a, T $b --> Bool) { ... }; method get-hash-value(T $obj) { ... } }
解决方法:目前最合理的解决方法是重写一个class的.WHICH
方法,作为hash值,是用于相等性测试。我举了一个哈希键 class 的例子,它模拟了一个值类型 。它几乎与每个散列对象的自定义散列函数一样通用,因为可以在创建散列时声明键类型。 (这不能为 Set
完成,因为 Set
没有参数化。)
哈希的工作方式是使用一个键存储一个值,然后使用完全相同的键检索该值。
对于像 Str 和 Int 这样的值类型,您可以有多个实例,它们的行为就好像它们是完全相同的值一样。所以 42
和 40 + 2
表现得好像它们是完全相同的实例,即使它们不是。
所以这可行:
my %h{Any}; # defaults to Str keys
%h{'abc'} = 42;
my ($a,$b,$c) = 'a', 'b', 'c';
say %h{"$a $b $c"}; # 42
%h{42} = 'The answer';
say %h{"42"}; # (Any)
say %h{42}; # The answer
实际上并没有一种工具可以让几个不同的值假装只是一个哈希值相同。
'abc' === 'cba'; # False
'abc'.WHICH eq 'cba'.WHICH; # basically how the above works
我认为你要求的是一个不应该添加的功能。
有一个 WHICH
方法,它应该只用于在整个语言中使两个值在任何地方都相同。
say 42.WHICH.perl; # ValueObjAt.new("Int|42")
say (40 + 2).WHICH.perl; # ValueObjAt.new("Int|42")
42 === (40 + 2); # True
say Hash.new.WHICH.perl; # ObjAt.new("Hash|94014087733456")
say Hash.new.WHICH.perl; # ObjAt.new("Hash|94014087735232")
请注意,对于 Hash.new
它们不匹配,因为它们是不同的实例,可能会随时间变化。
举个例子,这是一件好事。假设您有两名名为 'Bob'.
的员工
my $a = Employee.new( name => 'Bob' );
my $b = Employee.new( name => 'Bob' );
my %salary{Employee};
%salary{$a} = 1200; # arbitrary number for an example
%salary{$b} = 2000;
请注意,通过覆盖 WHICH
方法,您最终可能会不小心给 Bob $a
加薪。
基本上,乱用 .WHICH
可能不是一个好主意,除非您确切地知道自己在做什么,并且您有充分的理由这么做。
所以你不能't/shouldn那样做。至少不是您尝试的方式。
而是创建一个新的 Associative class,它可以按照您想要的方式工作。
role Custom-Str-Hasher {
method hashed ( --> Str:D ){…}
}
class Custom-SetHash is SetHash {
multi method AT-KEY ( Custom-Str-Hasher:D $key ) is rw {
self.AT-KEY( $key.hashed() ); # call base class's method
}
}
class Foo does Custom-Str-Hasher {
has Str:D $.Str is required;
# required by the Custom-Str-Hasher role
method hashed ( --> Str:D ){
$!Str.comb(/\w/).unique.sort.join;
# 'b cb a' → 'abc' and 'aaababcccba' → 'abc'
}
}
my $a = Foo.new(:Str('b cb a'));
my $b = Foo.new(:Str('aaababcccba'));
my %h is Custom-SetHash; # use a different class than the default
%h{$a} = True;
say %h{$b}; # True;
put $a; # b cb a
put $b; # aaababcccba
请注意,上面只是一个简单的例子,对于一个真实的例子,我会改变很多东西。一方面,%h{'abc'}
也会 return True
因为我实现 AT-KEY
方法的方式。它还缺少一些方法,例如 ASSIGN-KEY
和 DELETE-KEY
.
我的问题与
如何选择特定的哈希函数?例如,如果我想做基于值的匹配而不是引用匹配,我想看看某个元组是否存在(或者干脆删除它):
my %data := SetHash.new: (1, 2), (3, 4);
%data{$(1, 2)}:delete; # False
在 C++ 或 C# 中,我可以为构造函数提供自定义 hashing/comparison 函数。在 C# 中,如果我的数据类型是 struct
(值类型而不是引用类型),则按值散列将自动发生。 Perl 6 在某种程度上对 Pair
(如果 Pair 不包含任何容器)进行值类型散列,但我不知道如何使其适用于任何其他复杂类型。
一方面,我明白为什么这不是最安全的操作——很容易定义其哈希码在插入后可以更改的对象。但这并没有阻止 .NET 和 C++ STL 允许自定义散列。
可能的 API 用法(受 this 启发的链式哈希逻辑,最初来自 Boost)是:
class MyHasher does Hasher of Array[Int] {
method get-hash-value(Int @array) {
reduce
-> $a, $b {$a +^ ($b + 0x9e3779b97f4a7c16 + ($a +< 6) + ($a +> 2))},
0,
|@array;
}
method equals(Int @a, Int @b) { @a eqv @b; }
}
my %data := SetHash.new(
my Int @=[1, 2], my Int @=[3, 4],
:hasher(MyHasher.new)
);
say %data{$[1, 2]}; # should be True
这将是 hasher 角色,它应该由 Perl 6 的核心库提供,如果它还不存在的话:
role Hasher[::T=Any] { method equals(T $a, T $b --> Bool) { ... }; method get-hash-value(T $obj) { ... } }
解决方法:目前最合理的解决方法是重写一个class的.WHICH
方法,作为hash值,是用于相等性测试。我举了一个哈希键 class 的例子,它模拟了一个值类型 Set
完成,因为 Set
没有参数化。)
哈希的工作方式是使用一个键存储一个值,然后使用完全相同的键检索该值。
对于像 Str 和 Int 这样的值类型,您可以有多个实例,它们的行为就好像它们是完全相同的值一样。所以 42
和 40 + 2
表现得好像它们是完全相同的实例,即使它们不是。
所以这可行:
my %h{Any}; # defaults to Str keys
%h{'abc'} = 42;
my ($a,$b,$c) = 'a', 'b', 'c';
say %h{"$a $b $c"}; # 42
%h{42} = 'The answer';
say %h{"42"}; # (Any)
say %h{42}; # The answer
实际上并没有一种工具可以让几个不同的值假装只是一个哈希值相同。
'abc' === 'cba'; # False
'abc'.WHICH eq 'cba'.WHICH; # basically how the above works
我认为你要求的是一个不应该添加的功能。
有一个 WHICH
方法,它应该只用于在整个语言中使两个值在任何地方都相同。
say 42.WHICH.perl; # ValueObjAt.new("Int|42")
say (40 + 2).WHICH.perl; # ValueObjAt.new("Int|42")
42 === (40 + 2); # True
say Hash.new.WHICH.perl; # ObjAt.new("Hash|94014087733456")
say Hash.new.WHICH.perl; # ObjAt.new("Hash|94014087735232")
请注意,对于 Hash.new
它们不匹配,因为它们是不同的实例,可能会随时间变化。
举个例子,这是一件好事。假设您有两名名为 'Bob'.
的员工my $a = Employee.new( name => 'Bob' );
my $b = Employee.new( name => 'Bob' );
my %salary{Employee};
%salary{$a} = 1200; # arbitrary number for an example
%salary{$b} = 2000;
请注意,通过覆盖 WHICH
方法,您最终可能会不小心给 Bob $a
加薪。
基本上,乱用 .WHICH
可能不是一个好主意,除非您确切地知道自己在做什么,并且您有充分的理由这么做。
所以你不能't/shouldn那样做。至少不是您尝试的方式。
而是创建一个新的 Associative class,它可以按照您想要的方式工作。
role Custom-Str-Hasher {
method hashed ( --> Str:D ){…}
}
class Custom-SetHash is SetHash {
multi method AT-KEY ( Custom-Str-Hasher:D $key ) is rw {
self.AT-KEY( $key.hashed() ); # call base class's method
}
}
class Foo does Custom-Str-Hasher {
has Str:D $.Str is required;
# required by the Custom-Str-Hasher role
method hashed ( --> Str:D ){
$!Str.comb(/\w/).unique.sort.join;
# 'b cb a' → 'abc' and 'aaababcccba' → 'abc'
}
}
my $a = Foo.new(:Str('b cb a'));
my $b = Foo.new(:Str('aaababcccba'));
my %h is Custom-SetHash; # use a different class than the default
%h{$a} = True;
say %h{$b}; # True;
put $a; # b cb a
put $b; # aaababcccba
请注意,上面只是一个简单的例子,对于一个真实的例子,我会改变很多东西。一方面,%h{'abc'}
也会 return True
因为我实现 AT-KEY
方法的方式。它还缺少一些方法,例如 ASSIGN-KEY
和 DELETE-KEY
.