操作和存储大量有序列表或哈希的最佳方法是什么？

Question

我有一个简单的有序列表,可能包含100万或更多的项目.此列表只执行了一些操作:

• 存在值的查找
• 找到值的索引
• 找到索引的值
• 添加一个值
• 获取列表中的项目数

将值添加到列表后,它永远不会更改.我将项目附加到列表,没有插入或删除.

我需要操纵这个大清单,并持久存储它.现在我使用数据库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};
}

不要在多线程环境中使用它,这里有非原子操作.