c# - 双向远程查找表，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 范围内，Ai1-Ai2 范围的大小可以在 10 到 300 之间；而 float 的范围是 0 到 10,000.000(我们只使用小数点后 3 位)，范围 Bi1 - Bi2 的大小可以是 0.100 - 10.000

另一个已知事实是 A 肯定是连续的，而 B 可能不是。但两者都同时增加，但速度不同。而且两个范围都不重叠。两者都是单调递增的。

所以这样的事情是可以预料的:

(Ai1, Ai2) ~ ( Bi1, Bi2)

(1,78) ~ (13.454, 19.546)

(79,114) ~ (19.712,22.335)

(115, 198) ~ ( 22.678, 24.101)

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

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

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

Thnx-埃贡

Answer 1

考虑这种通用方法:

1. 定义ARange和BRange；并将它们指向彼此:

   class ARange
   {
       public int Low;
       public int High;
       public BRange B;
   }
   
   class BRange
   {
       public float Low;
       public float High;
       public ARange A;
   }
   

2. 通过互连两个实例的工厂方法构造成对的 ARange 和 BRange 类。

3. 将 ARange 和 BRange 存储在两个排序数组中。
4. 具有特定的a 或b 值，使用二进制搜索分别查找覆盖ARange 或BRange , 并检索相互关联的相反范围。

在最坏的情况下，二分查找的查找复杂度为 O(log N)，其中 N 是 ARange 和 BRange 的长度> 数组分别。这个特殊的弱类型 Array.BinarySearch过载可以让您快速启动。

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

实现该算法后，考虑这些优化:

• 将 ARange 和 BRange 定义为 struct 以减少动态分配的内存量，改善数据的局部性，并减少开销；
• 提供 ARange 形成连续序列(即没有间隙)，优化 High，并保留成对的 Low， B 和界定序列的上限(例如，作为数组中的人工元素)；
• 提供一个自定义二分搜索实现，它允许您将整数/ float 与 ARanges/BRanges 进行比较；

• 另一个增加数据局部性(从而减少 CPU 缓存未命中)的选项是将类分解为各个字段的数组，因此在二进制搜索中，您可以只使用 Low 范围，并仅针对特定项目访问 High 和 A/B:

  int[] ALow;    // Lows of A-ranges
  int[] AHigh;   // Highs of A-ranges
  int[] AB;      // index into B-arrays from A-ranges
  
  float[] BLow;  // Lows of B-ranges
  float[] BHigh; // Highs of B-ranges
  int[] BA;      // index into A-arrays from B-ranges