1

我有一个 Id 映射缓存，它占用了太多内存。它用于容纳对象的 3 种不同类型的 Id 的组合，并且它们的映射从表中读取，并缓存在 6 个不同的字典中，以便从任何一种 Id 类型快速查找/翻译到另一种（性能是对我的申请很重要）。

我想将它重写为内存占用更小的东西，所以我确实实现了 Id 的合并列表，并使用 linq/lambda 表达式来提取我想要的值。现在看起来像这样。

public struct IdMappings
{
     public int Id1;
     public int Id2;
     public int Id3;
}

//new cache    
private static List<IdMappings> AllIdMappings = null;

//current cache implementation
private static Dictionary<int, int> Id1ToId2 = null;
private static Dictionary<int, int> Id1ToId3 = null;
//etc.

public static void FillCache(DataSet data)
{
     foreach (DataRow r in data.Tables[0].Rows)
     {
          //fill list and/or dictionaries with id's
     }
}

示例查找将是：

public static int GetId2FromId1(int id1)
{
    return AllIdMappings.FirstOrDefault(m => m.Id1 == id1).Id2;
    //or
    return Id1ToId2[id1];
}

这在减少内存使用方面满足了我的需求，但是查找的性能因此受到影响，所以我正在研究如何实现不同的东西。有没有办法进行多索引键或多键查找比遍历列表相对更快？

4

4 回答 4

1

是的，对列表进行排序并使用二分搜索（List<> 已经在 Find 方法中为您实现了这一点） 维护排序列表并在 O(logn) 中完成查找。

于 2012-11-27T21:37:40.067 回答
1

一个潜在的性能改进可能是使用 aHashset<IdMappings>而不是 a List<IdMappings>，但这主要有助于直接查找，而不是FirstOrDefault或多或少地按顺序迭代列表。

如果您的查找全部来自 ID1 -> ID2 和 ID3 方向，则可以使用 aDictionary<int, Tuple<int, int>>作为键，这将从当前字典中消除 ID1 的额外值。

无论如何，缓存顾名思义就是用内存换取查找速度，所以我认为你不能大幅提高内存消耗。

于 2012-11-27T21:39:10.737 回答
1

如果添加这三个字典：

private static Dictionary<int, IdMappings> Id1Lookup = null;
private static Dictionary<int, IdMappings> Id2Lookup = null;
private static Dictionary<int, IdMappings> Id3Lookup = null;

并且字典值是相同的引用，它应该使用最少的内存，但保持与原始实现相同的查找速度。

如果我正在考虑这一点，这应该使用您的 6 字典解决方案的一半内存，但List<IdMappings>类型解决方案的两倍。

正如@SWeko 指出的那样，IdMappings需要class不是 astruct以确保使用引用指针而不是它的副本。

于 2012-11-27T21:39:31.210 回答
1

可能你最好的选择是创建一个映射结构：

struct Mapping: IComparable<Mapping>
{
    private readonly int FromId;
    private readonly int ToId;
    public Mapping(int fid, int tid);
    // implement the IComparable.Compare method to compare FromId
}

然后，为每个索引创建一个List<Mapping>，并对列表进行排序。然后，您可以使用List.Find来查找您想要的项目。

于 2012-11-27T21:41:23.440 回答