将字典序列化到磁盘？

Question

我们有一个Hashtable(特别是C#Dictionary类),它可以保存数千/数百万(Key,Value)对,用于近O(1)搜索命中/未命中.

我们希望能够将此数据结构刷新到磁盘(序列化)并稍后再次加载(反序列化),以便保留Dictionary的内部哈希表.

我们现在做的是:

1. 从磁盘加载=> List<KVEntity>.(KVEntity可序列化.我们使用Avro进行序列化 - 如果需要可以删除Avro)
2. KVEntity从array =>字典中读取每一个.这将重新生成字典/散列表内部状态.
3. <系统运行,字典可以增长/缩小/改变值等>
4. 保存时,从字典读入数组(通过myKVDict.Values.SelectMany(x => x)新的List<KVEntity>)
5. 我们将array(List<KVEntity>)序列化为磁盘以保存原始数据

请注意,在我们的保存/恢复期间,我们会丢失内部tashtable /字典状态,并且每次都必须重建它.

我们想直接序列化到/来自Dictionary(包括它的内部"实时"状态),而不是仅仅为磁盘i/o使用中间数组.我们怎么做？

一些伪代码:

// The actual "node" that has information. Both myKey and myValue have actual data work storing
public class KVEntity
{
    public string myKey {get;set;}
    public DataClass myValue {get;set;}
}

// unit of disk IO/serialization
public List<KVEntity> myKVList {get;set;} 

// unit of run time processing. The string key is KVEntity.myKey
public Dictionary<string,KVEntity> myKVDict {get;set;} 

Answer 1

存储Dictionary实例的内部状态将是不好的做法--OOP的一个关键原则是封装:内部实现细节是故意隐藏的消费者.

此外,使用的映射算法Dictionary可能会在不同版本的.NET Framework中发生变化,特别是考虑到CIL程序集被设计为向前兼容(即,针对.NET 2.0编写的程序通常可以针对.NET 4.5).

最后,序列化字典的内部状态并没有真正的性能提升.使用定义明确的文件格式要好得多,重点放在可维护性而不是速度上.此外,如果字典包含"几千个"条目,那么我应该在15ms内从磁盘加载(假设你有一个有效的磁盘格式).最后,针对RAM优化的数据结构在磁盘上不一定能很好地工作,顺序读/写更好.

你的帖子对于使用字典的内部状态非常坚定,但你现有的方法似乎很好(albiet,它可以做一些优化).如果您透露了更多详细信息,我们可以帮助您加快速度.

最佳化

我在现有实现中看到的主要问题是转换到数组和列表的转换,这是不必要的,因为它Dictionary是可直接枚举的.

我会做这样的事情:

Dictionary<String,TFoo> dict = ... // where TFoo : new() && implements a arbitrary Serialize(BinaryWriter) and Deserialize(BinaryReader) methods

using(FileStream fs = File.OpenWrite("filename.dat"))
using(BinaryWriter wtr = new BinaryWriter(fs, Encoding.UTF8)) {

    wtr.Write( dict.Count );

    foreach(String key in dict.Keys) {

        wtr.Write( key );
        wtr.Write('\0');
        dict[key].Serialize( wtr );
        wtr.Write('\0'); // assuming NULL characters can work as record delimiters for safety.
    }
}

假设你的TFoo Serialize方法很快,我真的不认为你会比这种方法获得更快的速度.

实现反序列化器对读者来说是一种练习,但应该是微不足道的.请注意我是如何将字典的大小存储到文件中的,因此返回的字典可以在创建时设置正确的大小,从而避免了@spender在评论中描述的重新平衡问题.