Structure de données pour le stockage d'éléments uniques

Question

Je cherche une structure de données qui devrait de préférence effectuer une valeur égale à O (1)? pour n'importe quel nombre d'éléments lors de l'ajout/suppression/récupération d'éléments.

Voici quelques conseils supplémentaires,

• la récupération des éléments ne devraient pas entraîner lents keys()
éléments
• doivent toujours être unique et défini
l'ordre des éléments
• est non significatif
• ajout ou le retrait de l'élément devrait n'implique pas d'itération par rapport aux autres éléments
• Les espaces dans la liste d'éléments récupérés sont tolérables et peuvent être représentés par undef valeur

S'il vous plaît suggérer une meilleure solution que,

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; 
    }; 
} 

MISE À JOUR (utilisation)

my $fa = uniqArrayFactory(); 

$fa->(add => 10); 
$fa->(del => 10); 
my $members = $fa->(mebers => 1); 

Answer 1

keys et each sont étonnamment lents en effet. Mais si vous stockez chaque élément en tant que valeur d'un hachage et que vous utilisez values, les choses deviennent plus faibles plus rapidement. Avec

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; 
    }; 
} 

Je reçois:

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

Answer 2

Ironie du sort, Tie::IxHash peut-être, qui a été motivée par le désir de récupérer les clés de un hachage dans un ordre spécifié, est aussi proche que vous allez obtenir ce que vous voulez.

Dans the Tie::IxHash implementation, les clés et les valeurs sont stockées dans des références de groupe. keys renvoie une copie de l'ensemble des clés, mais quelque chose comme (tied %hash)->[1] vous donnerait un accès direct à celui-ci.

La suppression d'éléments dans un Tie::IxHash est O (n). Une solution de contournement possible pour cela serait de remplacer les valeurs par undef plutôt que de les supprimer. Autrement dit, préférant

$ixhash{$obsolete_key} = undef; 

à

delete $ixhash{$obsolete_key}; 

Ou si vous étiez en mesure de mettre en commun vos suppressions - si vous pouvez organiser votre code afin que vous avez appelé habituellement delete sur plusieurs touches dans le même temps et entre d'autres opérations sur le hachage - alors il y a des possibilités d'amélioration sur Tie::IxHash.