双向远程查找表,C#

Question

我需要对某些数据结构做出设计决策,以便快速访问.这里的场景:我必须同步两个不同增长率的变量.我列出了以下格式的数据:

范围(Ai1,Ai2)〜范围(Bi1,Bi2)也就是说范围Ai1-Ai2与某些i的Bi1-Bi2匹配

现在给定AI的整个范围内的任何Ax应该能够确定(Bj1,Bj2)中的适当范围,反之亦然.数据类型明智:A是int; 而B是浮动的.

我不知道这个翻译最合适的数据类型是什么？我的主要要求是速度.此外,有关如何在C#中实现此数据结构的任何帮助都会有所帮助.

确保问题适合记忆.A的跨度可以是0-300,000的范围,并且范围Ai1-Ai2的大小可以是10到300的范围; 而浮点的跨度跨度为0到10,000.000(我们只使用3个小数位),范围Bi1 - Bi2的大小可以是0.100 - 10.000

另一个已知的事实是确保A是连续的而B可能不是.但两者同时增加,但速度不同.也不是Ranges重叠.两者都是单调增加的.

所以可以预期这样的事情:

(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,预期响应:范围=(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将s 和BRanges存储在两个已排序的数组中。
4. 有了特定的aorb值，使用二分查找分别查找覆盖的ARangeor BRange，并检索互连的相反范围。

在最坏的情况下，二分搜索会给您带来查找复杂性，其中 N 分别是和数组O(log N)的长度。这种特殊的弱类型重载可以给你一个启动的机会。ARangeBRangeArray.BinarySearch

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

该算法实现后，考虑以下优化：

• DefineARange和BRangeas structs，以减少动态分配的内存量，提高数据的局部性，减少开销；
• 提供ARanges 形成连续序列（即没有间隙），优化High并保留Low,B和界定序列的上限（例如，作为数组中的人工元素）；
• 提供自定义二分搜索实现，允许您将整数/浮点数与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