Quelle est la meilleure façon de manipuler et de stocker d'énormes listes ordonnées ou des hachages?

Question

J'ai une liste ordonnée simple qui pourrait contenir 1 million ou plus d'articles. Il n'y a que quelques actions qui sont faites avec cette liste:

• recherche dans une valeur existent
• trouver l'index pour une valeur
• valeur découverte pour l'index
• ajouter une valeur
• get nombre d'éléments de la liste

Une fois qu'une valeur est ajoutée à la liste, elle ne change jamais. J'ajoute des éléments à la liste, pas d'insertion ou de suppression.

J'ai besoin de manipuler cette grande liste, et de la stocker de manière persistante. En ce moment j'utilise une base de données Int => String pour représenter la liste, mais je pense qu'il devrait y avoir un moyen plus efficace de le faire.

je pourrais utiliser memcached, mais je pense que 2 fonctions sont manquantes:

• stockage persistant
• trouver l'index pour une valeur

Answer 1

Il semble que vous avez aussi besoin d'une table de correspondance String -> Int .

En Perl, la façon la plus simple de le faire est de tie un hachage à un fichier DBM (voir man perltie).

Exemple de code, non testé, pourrait certainement être amélioré:

use DB_File; 
tie %value2index, 'DB_File', 'value2index'; 
tie %index2value, 'DB_File', 'index2value'; 

sub index_count() { 
    return scalar %value2index; 
} 

sub value_exists() { 
    my $value = shift; 
    return exists($value2index{$value}); 
} 

sub append() { 
    my $value = shift; 
    if (!value_exits($value)) { # prevent duplicate insertions 
     my $index = index_count() + 1; 
     $value2index{$value} = $index; 
     $index2value{$index} = $value; 
    } 
} 

sub find_index() { 
    my $value = shift; 
    return $value2index{$value}; 
} 

sub find_value() { 
    my $index = shift; 
    return $index2value{$index}; 
} 

Ne pas utiliser dans un environnement multi-thread, il y a des opérations non atomiques ici.

Answer 2

Quelle est la taille de vos articles? Combien de mémoire cela vous dérange-t-il d'utiliser? Êtes-vous des objets uniques?

Vous pouvez probablement vous en sortir avec quelque chose comme ceci:

my @list; # This keeps the ordered list 
my %keyval; # This maps key to value 
my %valkey; # This maps value to key 

sur chaque insert vous devez:

push @list, value; 
$valkey{$value} = $#list; 
$keyval{$#list} = $value; 

Et pour chacun de vos besoins:

#Existence of a value: 
if(exists($valkey{$value})); 

#Existence of an index; 
if(exists($keyval{$index})); 

#value for an index: 
$keyval{$index}; 

#value for a key: 
$valkey{$value}; 

#Size 
$#list;