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

概述我正在寻找一个最好应该执行相等O(1)的数据结构？添加/删除/检索元素时的任意数量的元素. 以下是一些其他指南, >检索元素不应涉及慢键() >元素必须始终唯一且定义 >元素顺序不重要 >添加或删除元素不应涉及迭代其他元素 >检索到的元素列表中的间隙是可以容忍的,可以用undef值表示 请建议更好的解决方案, sub uniqArrayFactory { my $members = []; 我正在寻找一个最好应该执行相等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 uarrayhash   3205/s     --    -6%uarray 3401/s     6%     --

总结

以上是内存溢出为你收集整理的list – 唯一元素存储的数据结构全部内容，希望文章能够帮你解决list – 唯一元素存储的数据结构所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。