list – 唯一元素存储的数据结构

发布时间：2020-12-15 23:36:15 所属栏目：大数据来源：网络整理

导读：我正在寻找一个最好应该执行相等O(1)的数据结构？添加/删除/检索元素时的任意数量的元素. 以下是一些其他指南, 检索元素不应涉及慢键() 元素必须始终唯一且定义元素顺序不重要添加或删除元素不应涉及迭代其他元素检索到的元素列表中的间隙是可以容忍的,可

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

以下是一些其他指南,

>检索元素不应涉及慢键()
>元素必须始终唯一且定义
>元素顺序不重要
>添加或删除元素不应涉及迭代其他元素
>检索到的元素列表中的间隙是可以容忍的,可以用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);

解决方法

键和每个键确实非常慢.但是如果将每个元素存储为哈希值并使用值,则事情会变得更快.同

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,$m;
        $seen->{$m} = ( $members->[-1] );
      }
    }
    return $m;
  };
}

我明白了：

Rate   hash uarray
hash   3205/s     --    -6%
uarray 3401/s     6%     --

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!