由于我们的系统仿真的一部分阵列搜索会员，我建模使用稀疏存储阵列，并保持对象的列表来跟踪那些内部分配的缓冲区的64位寻址的存储空间内存空间。缓冲区被动态分配和解除分配。的范围
我有一个函数，在分配的缓冲区内搜索给定的地址或地址范围，以查看对内存模型的访问是否在分配空间中，并且我的第一次切入“搜索所有缓冲区，直到找到匹配“会使我们的模拟速度减慢10％。我们的UUT执行大量的内存访问，必须通过模拟进行审查。
所以，我试图优化。内存缓冲区对象包含起始地址和长度。我正考虑在对象创建时通过开始地址对对象数组进行排序，然后在调用检查函数时，对数组执行二进制搜索，以查看给定地址是否落入开始/结束范围内。
是否有更好的/更快的方式做到这一点？必须有一些更快/更酷的算法，使用堆或散列签名或一些 - 如，对吗？
二进制搜索，但使得分配/释放缓慢。
一个简单的例子是制作一个有序的二叉树（红黑树，AVR树等），由起始地址索引，这样插入（分配），删除（取消分配）和搜索都是O N）。大多数现代语言已经提供了这样的数据结构（例如C++的std::map）。
我首先想到的也是二进制搜索，我认为这是一个好主意。您应该能够快速插入和删除。使用散列会让你把地址放在桶里（在我看来），然后你很快到达正确的桶（然后必须搜索桶）。经过排序后的数组作品
基本上你的问题是，你有一个定义的“有效”记忆的时间间隔，这些间隔外的内存是“无效的”，并且要检查一个给定的地址是否是一个有效的内存块内与否。
您可以通过存储在二叉树所有分配的内存块的起始地址绝对做到这一点;然后在被查询的地址处或以下搜索最大的地址，并验证地址是否在有效地址的长度内。这给你O（log n）查询时间，其中n =分配块的数量。当然也可以使用相同的查询来实际查找块本身，因此您还可以读取给定地址处块的内容，我想你也需要这样做。
但是，这不是最有效的方案。相反，您可以另外使用一维空间细分树来标记无效的内存区域。例如，使用分支因子为256的树（对应于8位），将其中只有无效地址的所有16kB块映射为“1”，其他映射为“0”;该树将只有两个级别，并且将非常有效地进行查询。当你看到一个地址时，首先询问这棵树，如果它肯定是无效的;只有当它不是时，查询另一个。这会加快速度，只有当您实际获取大量无效的内存参考时;如果所有内存引用实际上都是有效的，而你只是断言，那么你不会保存任何内容。但是你也可以将这个想法翻转过来，并将树标记用于所有那些只有有效地址的16kB或256B块;树增长的大小取决于模拟内存分配器的工作方式。