無字典快速多鍵查找？

我有一個Id映射緩存佔用了太多的內存。它用於容納對象的3種不同類型的Id的組合，並且從表中讀入它們的映射，並且緩存在6個不同的字典中，用於從任何1個Id類型到另一個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]; 
}

這做什麼，我需要減少內存使用方面，但對於查找性能遭受結果，所以我看到如何實現的東西不同。有沒有辦法做多索引鍵，或多鍵查找比迭代列表快嗎？

來源

2012-11-27 Tom

'這樣就可以減少內存使用量，但查找性能受到影響 - 這可能是因爲您不再有內存中準備的對象，因此需要檢索它們從你的數據庫中找到該ID後？即它是一個延遲加載而不是急切的加載。你確定性能受到影響的是'查找'而不是'檢索'嗎？ –

緩存在應用開始時填充，因此只有一次。字典/哈希集被設計用於快速查找，按照O（1）的順序。我確實相信使用帶有linq的列表將始終是O（n），因爲它會迭代整個列表以找到匹配項。 – Tom

如果這是迴應我的評論，當你說'緩存已滿'，你的意思是用'objects'還是'keys'？如果您事先檢索對象，您最好創建一個對象的字典而不是它們的關鍵字 - 沒有任何記憶效益。如果你沒有檢索對象，那麼在找到合適的鍵後，你需要從數據庫中獲取相應的對象，這將導致更長的執行時間。 –

如果添加這些三點字典：

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而不是struct以確保使用引用指針而不是副本。

來源

2012-11-27 21:39:31 Thymine

爲此，OP還可能需要將'IdMappings'重新定義爲'class'而不是'struct' – SWeko

是的，對列表進行排序並使用二進制搜索（列表<>已在Find方法中爲您實現此功能）然後在O（logn）中完成維護排序列表和查找。

來源

2012-11-27 21:37:40

一個潛在的性能改進可能是使用Hashset<IdMappings>而不是List<IdMappings>，但這將主要有助於直接查找，而不是FirstOrDefault，它或多或少地按順序迭代列表。

如果您的查找全部來自ID1 - > ID2和ID3方向，則可以使用Dictionary<int, Tuple<int, int>>作爲密鑰，這將消除當前字典中額外的ID1值。

無論如何，緩存是爲了查找速度而定義的內存交易，所以我不認爲你可以提高很多內存消耗。

來源

2012-11-27 21:39:10 SWeko

它們是6種不同的查找，因此6個不同的原始實現字典：id1 - > id2，id1 - > id3，id2 - > id1，id2 - > id3，id3 - > id1，id3 - > id2 – Tom

@Tom：那麼你需要三個'Dictionary '，那樣會（我認爲）將內存佔用減少了大約25％。 – SWeko

大致如此。它與胸腺嘧啶上面的答案一致，這很好。 – Tom

可能是你最好的選擇是創建一個映射結構：

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-27 21:41:23

無字典快速多鍵查找？

回答

相關問題