唯一元素存储的数据结构
Data structure for unique element storage
我正在寻找一种数据结构,它应该最好执行相等的 O(1)?对于 adding/removing/retrieving 个元素时的任意数量的元素。
这里有一些额外的指南,
- 检索元素不应涉及缓慢
keys()
- 元素必须始终唯一且已定义
- 元素顺序不重要
- 元素的添加或删除不应涉及对其他元素的迭代
- 检索到的元素列表中的间隙是可以容忍的,可以用
undef
值 表示
请提出比
更好的解决方案
sub uniqArrayFactory {
my $members = [];
my $seen = {};
my $gaps = [];
return sub {
my (%arg) = @_;
return $members if $arg{members};
my $m;
if (defined ($m = $arg{del})) {
return if !$seen->{$m};
${ $seen->{$m} } = undef;
push @$gaps, delete($seen->{$m});
}
elsif (defined ($m = $arg{add})) {
return if $seen->{$m};
if (@$gaps) {
$seen->{$m} = pop @$gaps;
${ $seen->{$m} } = $m;
}
else {
push @$members, $m;
$seen->{$m} = \( $members->[-1] );
}
}
return $m;
};
}
更新(用法)
my $fa = uniqArrayFactory();
$fa->(add => 10);
$fa->(del => 10);
my $members = $fa->(mebers => 1);
具有讽刺意味的是,也许 Tie::IxHash
的动机是希望以指定的顺序检索散列的键,这与您想要获得的东西一样接近。
在the Tie::IxHash
implementation中,键和值存储在数组引用中。 keys
returns 一组密钥的副本,但是像 (tied %hash)->[1]
这样的东西会让你直接访问它。
删除 Tie::IxHash
中的元素是 O(n)。一个可能的解决方法是用 undef
替换值而不是删除它们。即偏爱
$ixhash{$obsolete_key} = undef;
到
delete $ixhash{$obsolete_key};
或者,如果您能够合并您的删除——如果您可以组织您的代码,以便您通常在几个键上同时调用 delete
,并且在哈希的其他操作之间——那么Tie::IxHash
.
有改进的机会
keys
和 each
确实出奇的慢。但是,如果您将每个元素存储为散列值并使用 values
,事情就会变得更快。有
use strict;
use warnings;
use Benchmark qw(:all);
my $i;
my $fa;
my %hash;
my %compare = (
uarray => sub {
$fa->(add => $i++);
my $memb = $fa->(members => 1);
for my $v (@$memb) { next if !defined $v; }
},
hash => sub {
$hash{ $i } = $i;
for my $v (values %hash) {}
$i++;
},
);
$i = 0; $fa = uniqArrayFactory(); %hash = ();
cmpthese(10000, \%compare);
sub uniqArrayFactory {
my $members = [];
my $seen = {};
my $gaps = [];
return sub {
my (%arg) = @_;
return $members if exists $arg{members};
my $m;
if (defined ($m = $arg{del})) {
return if !$seen->{$m};
${ $seen->{$m} } = undef;
push @$gaps, delete($seen->{$m});
}
elsif (defined ($m = $arg{add})) {
return if $seen->{$m};
if (@$gaps) {
$seen->{$m} = pop @$gaps;
${ $seen->{$m} } = $m;
}
else {
push @$members, $m;
$seen->{$m} = \( $members->[-1] );
}
}
return $m;
};
}
我得到:
Rate hash uarray
hash 3205/s -- -6%
uarray 3401/s 6% --
我正在寻找一种数据结构,它应该最好执行相等的 O(1)?对于 adding/removing/retrieving 个元素时的任意数量的元素。
这里有一些额外的指南,
- 检索元素不应涉及缓慢
keys()
- 元素必须始终唯一且已定义
- 元素顺序不重要
- 元素的添加或删除不应涉及对其他元素的迭代
- 检索到的元素列表中的间隙是可以容忍的,可以用
undef
值 表示
请提出比
更好的解决方案sub uniqArrayFactory {
my $members = [];
my $seen = {};
my $gaps = [];
return sub {
my (%arg) = @_;
return $members if $arg{members};
my $m;
if (defined ($m = $arg{del})) {
return if !$seen->{$m};
${ $seen->{$m} } = undef;
push @$gaps, delete($seen->{$m});
}
elsif (defined ($m = $arg{add})) {
return if $seen->{$m};
if (@$gaps) {
$seen->{$m} = pop @$gaps;
${ $seen->{$m} } = $m;
}
else {
push @$members, $m;
$seen->{$m} = \( $members->[-1] );
}
}
return $m;
};
}
更新(用法)
my $fa = uniqArrayFactory();
$fa->(add => 10);
$fa->(del => 10);
my $members = $fa->(mebers => 1);
具有讽刺意味的是,也许 Tie::IxHash
的动机是希望以指定的顺序检索散列的键,这与您想要获得的东西一样接近。
在the Tie::IxHash
implementation中,键和值存储在数组引用中。 keys
returns 一组密钥的副本,但是像 (tied %hash)->[1]
这样的东西会让你直接访问它。
删除 Tie::IxHash
中的元素是 O(n)。一个可能的解决方法是用 undef
替换值而不是删除它们。即偏爱
$ixhash{$obsolete_key} = undef;
到
delete $ixhash{$obsolete_key};
或者,如果您能够合并您的删除——如果您可以组织您的代码,以便您通常在几个键上同时调用 delete
,并且在哈希的其他操作之间——那么Tie::IxHash
.
keys
和 each
确实出奇的慢。但是,如果您将每个元素存储为散列值并使用 values
,事情就会变得更快。有
use strict;
use warnings;
use Benchmark qw(:all);
my $i;
my $fa;
my %hash;
my %compare = (
uarray => sub {
$fa->(add => $i++);
my $memb = $fa->(members => 1);
for my $v (@$memb) { next if !defined $v; }
},
hash => sub {
$hash{ $i } = $i;
for my $v (values %hash) {}
$i++;
},
);
$i = 0; $fa = uniqArrayFactory(); %hash = ();
cmpthese(10000, \%compare);
sub uniqArrayFactory {
my $members = [];
my $seen = {};
my $gaps = [];
return sub {
my (%arg) = @_;
return $members if exists $arg{members};
my $m;
if (defined ($m = $arg{del})) {
return if !$seen->{$m};
${ $seen->{$m} } = undef;
push @$gaps, delete($seen->{$m});
}
elsif (defined ($m = $arg{add})) {
return if $seen->{$m};
if (@$gaps) {
$seen->{$m} = pop @$gaps;
${ $seen->{$m} } = $m;
}
else {
push @$members, $m;
$seen->{$m} = \( $members->[-1] );
}
}
return $m;
};
}
我得到:
Rate hash uarray
hash 3205/s -- -6%
uarray 3401/s 6% --