词典:访问速度更快，但占用的内存更少 [英] Dictionary: faster access but less memory footprint

问题描述

我想就最小的存储空间和最大的访问性能来建议最佳的存储和访问方式.

例如
对于每辆车，我都想存储其型号和名称.

我在下面有一些想法:

选项1:

Hi,
I want some advise on the best way to store and access with minimum memory footprint and maximum access performance.

Eg.
for each vehicle make i want to store model and name.

i have some thoughts below:

Option 1:

Dictionary<string, Dictionary<string, string>> values = new Dictionary<string, Dictionary<string, string>>();
Dictionary<string, string> list = new Dictionary<string, string>();
list.Add("2001", "Jetta S");
list.Add("2002", "Jetta SE");
list.Add("2002", "Jetta LE");
values.Add("VolksWagen", list);

选项2:

Option 2:

Dictionary<string, List<KeyValuePair<string, string>>> values2 = new Dictionary<string, List<KeyValuePair<string, string>>>();
<pre lang="xml">List<KeyValuePair<string, string>> list2 = new List<KeyValuePair<string, string>>();
list2.Add(new KeyValuePair<string, string>("2001", "Jetta S"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta SE"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta LE"));
values2.Add("VolksWagen", list2);

选项3:

Option 3:

Dictionary<string, List<string>> values1 = new Dictionary<string, List<string>>();
List<string> list1 = new List<string>();
list1.Add("2001:Jetta S");
list1.Add("2002:Jetta SE");
list1.Add("2002:Jetta LE");
values1.Add("VolksWagen", list1);

选项1:更快访问品牌和名称，但占用内存最多
选项2:快速访问品牌和名称，但占用的内存更多
选项3:缓慢访问品牌和名称(必须对其进行解析)，但占用的内存更少

对于加快访问速度但减少内存占用量的任何建议，不胜感激?
谢谢.

Option 1: faster access of make and name but most memory footprint
Option 2: fast access of make and name but more memory footprint
Option 3: slow access of make and name (would have to parse it) but less memory footprint

Any suggestions for fastest access but less memory footprint is appreciated?

Thanks.

推荐答案

都没有！

组合键:一些带有两个单独字符串的结构.覆盖哈希函数System.Object.GetHashCode和System.Object.Equals以反映两个字符串(只需获取级联字符串的标准哈希).

如果希望Year用整数表示，则键会有所不同:

Neither!

Make a combined key: some structure with two separate strings. Override hash function System.Object.GetHashCode and System.Object.Equals to reflect both strings (simply get standard hash of concatenated sting).

If you want Year to be represented by integer, the key will be a bit different:

struct CarKey {
    CarKey(int year, string make) { Year = year; Make = make; }
    public override int GetHashCode() {
        return Year.GetHashCode() ^ Make.GetHashCode();
    }
    public override bool Equals(object obj) {
        if (obj == null) return false;
        if (obj.GetType() != GetType()) return false;
        CarKey another = (CarKey)obj;
        if (object.ReferenceEquals(another, null)) return false;
        return (another.Make == Make) && (another.Year == Year);
    }
    int Year;
    string Make;
}

不要使用字典词典，也不要使用列表.
将单个字典与上述键一起使用.

为什么我认为这是速度和内存占用的最佳组合，这是一个困难的话题，因为确切的答案很大程度上取决于您要在这些矛盾的因素上施加的权重，但至少我敢肯定，这比所有您的方法更好最实用的建议.从这一点上，我建议您进行自己的比较和测试.最终答案还应该高度取决于您所需要的查询，而您没有描述.

在完全分析您的需求之前，没有什么可以给您最终的答案.

—SA

Don''t use dictionary of dictionaries, don''t use lists as well.
Use one single dictionary with the key described above.

Why I think this is the best combination of speed and memory footprint is a difficult topic, because exact answer strongly depends on weights you want to put on those contradicting factors, but at least I''m sure it''s better then all your suggestions for most practical purposes. From this point, I suggest you do your own comparison and tests. Final answer also should highly depend on queries you need, which you did not describe.

Nothing can give you a final answer until you fully all analyze your requirements.

—SA

通常，没有什么比紧凑性和访问速度更好的排序数组了，但是随机插入往往很昂贵.如果您能够按排序顺序填充数组，并保留所需数量的初始元素，则它通常会胜过任何其他常规"解决方案.

使用 Array.BinarySearch< T>(T []，T，IComparer< T>) [ ^ ]或

Usually nothing beats a sorted array for compactness and access speed - but random insertions tends to be expensive. If you are able to populate the array in sorted order, and reserver the required number of initial elements, it will usually outperform any other "general" solution.

Use Array.BinarySearch<T>( T[], T, IComparer<T>)[^] or Array.BinarySearch Method (Array, Object, IComparer)[^] to look up elements in your array. Using the latter enables you to implement IComparer to handle lookup by key, and you are entirely free to define what you want the key to be - string, another object, and so on ...


Regards
Espen Harlinn

这篇关于词典:访问速度更快，但占用的内存更少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！