双向范围查找表，C#

Question

我需要在某些数据结构上做出设计决策，以实现极快的访问速度。这里的场景是:我必须同步两个不同增长率的变量。我有以下格式的表格数据：

Range( Ai1，Ai2) ~ Range ( Bi1，Bi2)也就是说，对于某些I，范围Ai1 - Ai2与Bi1 - Bi2匹配

现在给定A的整个跨度中的任何Ax，我应该能够确定(Bj1，Bj2)中的适当范围，反之亦然。数据类型:A是int；而B是float。

我不知道什么数据类型最适合这个转换？我的主要需求是速度。此外，任何关于如何在C#中实现此数据结构的帮助都会很有帮助。

这个问题肯定会存储在内存中。A的跨度可以约为0- 300,000，范围A1- Bi2的大小可以是10 - 300；而浮点的跨度的跨度是0- 10,000.000 (我们只使用3位小数点)，范围Bi1 -Bi2的大小可以是0.100 - 10.000

另一个已知的事实是，A是确保连续的，而B可能不是。但两者都是同时增加的，但在不同的rates.Also下，两个范围都没有重叠。两者都是单调递增的。

所以像这样的事情是可以预期的：

(Ai1，Ai2) ~( Bi1，Bi2)

(1,78) ~ (13.454，19.546)

(79,114) ~ (19.712,22.335)

(115198)~( 22.678，24.101)

查询:A= 99，预期返回:B范围= (19.712,22.335)

查询:B= 16.117，预期响应:A range= (1,78)

如果B不在范围内，则需要向前舍入。

Thnx-Egon

Answer 1

考虑以下一般方法：

1. 定义ARange和BRange；并将它们相互指向：

instances.

• Store ARange { public int Low；public int High；public BRange B；} class BRange { public float Low；public float High；public ARange A；}

• 通过一个工厂方法构造ARange和BRange类对，该方法将两个已排序的类中的ARange和BRange互连在一个特定的a或b值中，使用二进制搜索分别查找覆盖的ARange或d17，并检索互连的相反范围。H218<代码>G219

二进制搜索在最坏的情况下会给你一个O(log N)查找复杂度，其中N分别是ARange和BRange数组的长度。这种特殊的弱类型Array.BinarySearch重载可以让您开门见山。

如果您需要一个具有良好可读性的通用解决方案，您可以重载(int, ARange)和(float, BRange)对的比较操作。

在实现此算法后，请考虑以下优化：

• 将ARange和BRange定义为structs，以减少动态分配的内存量，改善数据的局部性，并减少ARanges形成连续序列(即没有间隙)，优化High，并保留成对的Low、B和定界序列的上界(例如，作为array);
• provide中的一个人为元素)自定义的二进制搜索实现，它将允许您将int/floats与D39/D40进行比较；
• 增加数据局部性(从而减少CPU缓存未命中)的另一种选择是将类分解为单个字段的数组，因此在二进制搜索中，您可以只处理Low边界，并仅访问特定项的High和A/B：

int[] ALow；// A-ranges int[] AHigh的低；// A-ranges int[] AB的高；//从A-ranges float[] BLow索引到B-数组；// B-ranges float[] BHigh的低；// B-ranges int[] BA的高；//从B-ranges索引到A-数组

Answer 2

数据的关键属性是，对于A和关联的B，范围：

1. 不要单调地使用overlap.
2. Increase。

这意味着简单的二进制搜索应该有效地工作，并为您提供O(log(n))查找。

按升序存储间隔对的数组。

要执行查找(比方说，在A上)，在"key“间隔(在本例中为A)的start属性上运行二进制搜索，以查找起始小于要搜索的项的最高间隔。然后检查该间隔是否包含项目(end >= toSearch)。“值”(在本例中是关联的B间隔)很容易提取-它是同一数组元素的一部分。

反向查找(即从B到A)的工作方式与此基本相同。