6

我正在寻找一个最好执行等于 O(1) 的数据结构？在添加/删除/检索元素时适用于任意数量的元素。

这里有一些额外的指导方针，

  • 检索元素不应涉及缓慢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);
4

2 回答 2

2

keys并且each确实非常慢。但是，如果您将每个元素存储为 hash 的值并使用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%     --
于 2016-05-19T23:28:03.367 回答
1

具有讽刺意味的是，可能Tie::IxHash是出于以指定顺序检索哈希键的愿望，它与您将要获得的结果一样接近。

在实现中Tie::IxHash，键和值存储在数组引用中。keys返回一组键的副本，但类似的东西(tied %hash)->[1]可以让您直接访问它。

删除 a 中的元素Tie::IxHash是 O(n)。一种可能的解决方法是将值替换为undef而不是删除它们。也就是说，更喜欢

$ixhash{$obsolete_key} = undef;

至

delete $ixhash{$obsolete_key};

或者，如果您能够汇集您的删除 - 如果您可以组织您的代码，以便您通常delete在同一时间以及在散列上的其他操作之间调用多个键 - 那么就有改进的机会Tie::IxHash。

于 2016-05-19T18:27:50.247 回答