由於我們的系統仿真的一部分陣列搜索會員，我建模使用稀疏存儲陣列，並保持對象的列表來跟蹤那些內部分配的緩衝區的64位尋址的存儲空間內存空間。緩衝區被動態分配和解除分配。的範圍
我有一個函數，在分配的緩衝區內搜索給定的地址或地址範圍，以查看對內存模型的訪問是否在分配空間中，並且我的第一次切入「搜索所有緩衝區，直到找到匹配「會使我們的模擬速度減慢10％。我們的UUT執行大量的內存訪問，必須通過模擬進行審查。
所以，我試圖優化。內存緩衝區對象包含起始地址和長度。我正考慮在對象創建時通過開始地址對對象數組進行排序，然後在調用檢查函數時，對數組執行二進制搜索，以查看給定地址是否落入開始/結束範圍內。
是否有更好的/更快的方式做到這一點？必須有一些更快/更酷的算法，使用堆或散列簽名或一些 - 如，對嗎？
二進制搜索，但使得分配/釋放緩慢。
一個簡單的例子是製作一個有序的二叉樹（紅黑樹，AVR樹等），由起始地址索引，這樣插入（分配），刪除（取消分配）和搜索都是O N）。大多數現代語言已經提供了這樣的數據結構（例如C++的std::map）。
我首先想到的也是二進制搜索，我認爲這是一個好主意。您應該能夠快速插入和刪除。使用散列會讓你把地址放在桶裏（在我看來），然後你很快到達正確的桶（然後必須搜索桶）。經過排序後的數組作品
基本上你的問題是，你有一個定義的「有效」記憶的時間間隔，這些間隔外的內存是「無效的」，並且要檢查一個給定的地址是否是一個有效的內存塊內與否。
您可以通過存儲在二叉樹所有分配的內存塊的起始地址絕對做到這一點;然後在被查詢的地址處或以下搜索最大的地址，並驗證地址是否在有效地址的長度內。這給你O（log n）查詢時間，其中n =分配塊的數量。當然也可以使用相同的查詢來實際查找塊本身，因此您還可以讀取給定地址處塊的內容，我想你也需要這樣做。
但是，這不是最有效的方案。相反，您可以另外使用一維空間細分樹來標記無效的內存區域。例如，使用分支因子爲256的樹（對應於8位），將其中只有無效地址的所有16kB塊映射爲「1」，其他映射爲「0」;該樹將只有兩個級別，並且將非常有效地進行查詢。當你看到一個地址時，首先詢問這棵樹，如果它肯定是無效的;只有當它不是時，查詢另一個。這會加快速度，只有當您實際獲取大量無效的內存參考時;如果所有內存引用實際上都是有效的，而你只是斷言，那麼你不會保存任何內容。但是你也可以將這個想法翻轉過來，並將樹標記用於所有那些只有有效地址的16kB或256B塊;樹增長的大小取決於模擬內存分配器的工作方式。