Какой лучший способ манипулировать и хранить огромные упорядоченные списки или хэши?

Question

У меня есть простой упорядоченный список, который может содержать 1 миллион или более элементов. С этим списком можно выполнить всего несколько действий:

• поиск в значении существует
• найти индекс для значения
• найти значение для индекса
• добавить значение
• получить количество элементов в списке

После добавления значения в список оно никогда не изменяется. Я добавляю элементы в список, не вставляю и не удаляю.

Мне нужно манипулировать этим большим списком и постоянно его хранить. Прямо сейчас я использую базу данных Int => String для представления списка, но я думаю, что мне нужен более эффективный способ сделать это.

Я мог бы использовать memcached, но я думаю, что 2 функции отсутствуют:

• постоянное хранилище
• найти индекс для значения

Answer 1

Похоже, вам также нужна таблица сопоставления String -> Int.

В Perl самый простой способ сделать это - tie хэш-файл DBM (см. man perltie).

Пример кода, не проверенный, почти наверняка может быть улучшен:

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

Не используйте это в многопоточной среде, здесь есть неатомарные операции.

Answer 2

Насколько велики ваши товары? Сколько памяти вы не против использовать? Вы уникальны?

Возможно, вы могли бы получить что-то вроде этого:

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

на каждой вставке вы бы:

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

И для каждого из ваших требований:

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