是否有可能爲每個密鑰提供多個值而不必首先查找密鑰？

我正在寫一個2D性能無限的地形編輯器。每次用戶繪畫時，他都會創建Node s，此時它將分配給「圖層」類中的字典。由於用戶可以在不同的圖層上繪製現有節點，我想查找這些節點並將其銷燬。使用我目前的設置，這將涉及循環遍歷所有圖層，並從字典中逐個獲得必要的節點。是否有可能爲每個密鑰提供多個值而不必首先查找密鑰？

很明顯，如果每幀要做幾萬次，那麼這太昂貴了。所以現在我想我可以創建一個包含列表中所有節點的字典。然而，事實證明這幾乎可以使用盡可能多的性能事先設置的，因爲現在我不得不爲實例化新的節點時，密鑰是否已經存在進行檢查：

前：

public Node(){ 
    dic.Add(key,this); 
}

現在：

public Node(){ 
    List<Node> nodes; 
    if(dic.TryGetValue(key,out nodes)) 
    nodes.Add(this); 
    else{ 
    list = new List<Node>(); 
    dic.Add(key,list); 
    } 
}

正如你所看到的，而目前的設置爲節點檢查時節省一些性能，它徹底破壞，通過字典查找時間膨脹的實例化時間的影響。

所以現在我正在尋找一些方法來獲得與Dictionary<Key,List<Node>>相同的效果，但沒有在字典中查找列表的成本。是否可能有一種不同類型的字典讓一個堆棧爲每個密鑰提供無限的（或者如果必要的話）有限數量的值？

另外，是否有可能以某種方式爲字典中的值排序，因此我可以使用正常的Dictionary<key, Node>，然後查找第一個鍵並從那裏循環到所有值，直到我點擊某個不再適合搜索的節點標準是什麼？

在僞代碼，我實例化的功能應該是這樣的：

public Node(){ 
    dic.Add(key+LayerIndex,this); 
}

和我的查找功能會是這個樣子

public LookUpAll(key, out list){ 
    var o = dic[key]; // looking up just one node 
    list.Add(o); 
    var keyPosition = o.keyPosition; 
    while(o.position == keyPosition){ // then looping through all other nodes at that position until one comes that has a different position. 
    o = dic.NextValue(); 
    list.Add(o); 
    } 
}

現在，這並不因爲工作是對未分類字典，但因爲我希望有人在這裏可以從中得到一些啓發，並找出一個有效的解決方案。

如何在我的方案中減少查找次數，或者在不查找密鑰的情況下爲每個密鑰添加多個值？

來源

2014-01-14 Sven

您確定字典查找是此過程的瓶頸嗎？ – Bas

我現在運行了一些基準測試，如果我實例化500^2個節點，那麼性能成本加上檢查組成1/2和1％之間的東西。說實話，我認爲它會更好，因爲它曾經是過去的一個主要瓶頸，直到我重寫了散列函數，但即使如此，它也會很好，特別是因爲我希望進一步提高性能我不想讓這件事成爲未來的瓶頸。 – Sven

對於您的替代解決方案，請考慮使用SortedDictionary 。然後，您將爲密鑰傳遞您自己的IComparer實現，以便字典將按照您的查找要求進行正確排序。我不能說這是否會或多或少的表現。 –

由於用戶可以畫在現有節點，而他的上一個不同的層，

我會認爲這是使你最終不會持久，你不要」數據需要。但是，如果用戶不打算刪除該層上的數據呢？他只是想「看到」看起來如何。然後他解除了他的改變和blammo，你沒有關於他剛剛做的改變的數據，所以你不能撤消它。

爲什麼不只是保留所有的節點，除非用戶明確試圖刪除它們？最終用戶總是可以選擇最終結果中截取的是什麼。

你也可以嘗試使用樹狀結構。

來源

2014-01-14 14:17:18

你提到了一個很好的觀點，我還沒有想過可逆性。然而，所有這些微觀優化的主要原因是腳本也需要在遊戲過程中運行。我希望它能夠實時生成地形，而不必依靠多線程來隱藏性能成本。 – Sven

表示您不想依賴多線程來「隱藏性能成本」讓我感到困惑，因爲多線程是一種可以使用的工具。無論哪種方式字典查找速度非常快。正如有人提到，你確定字典是瓶頸嗎？此外，你甚至有基準嗎？還是隻是過早的優化（邪惡）？ –

是的，我是邪惡的......但我仍然想要在任何地方節省性能。那麼你能否詳細說明你的樹狀結構？你的意思是說什麼Bas Brekelmans發佈的內容？ – Sven

如果您只關心與某個鍵相關的最高層節點，並且偶爾需要遍歷所有節點，則可以從節點構建鏈接列表。這允許您迭代節點並通過鍵檢索相關節點。但是它會增加節點的內存消耗。你可以通過創建一個Node的子類來保持Next屬性，同時讓正常的節點沒有底層節點的可能性。儘管這可能會減慢迭代速度。

public Node Next { get; set; } 

public Node() 
{ 
    Node next; 
    if (dic.TryGetValue(key, out next)) 
     this.Next = next; 
    dic[key] = this; 
}

來源

2014-01-14 14:25:03 Bas

是否有可能爲每個密鑰提供多個值而不必首先查找密鑰？

回答

相關問題