двухсторонняя таблица поиска, C #

Question

Мне нужно принять проектное решение по некоторой структуре данных для чрезвычайно быстрого доступа. Вот сценарий: Я должен синхронизировать две переменные с разной скоростью роста. У меня есть данные в следующем формате:

Range (Ai1, Ai2) ~ Range (Bi1, Bi2) То есть, диапазон Ai1 - Ai2 соответствует Bi1 - Bi2 для некоторого i

Теперь, учитывая любой топор во всем диапазоне A, я должен быть в состоянии определить соответствующий диапазон в (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 - нет. Но оба вида увеличиваются одновременно, но с разной скоростью. Также ни один из диапазонов не перекрывается. Оба монотонно растут.

Так что можно ожидать чего-то подобного:

(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 и BRange s в двух отсортированных массивах.
4. Имея определенное значение a или b, используйте бинарный поиск для поиска покрытия ARange или BRange соответственно,и извлеките взаимосвязанный противоположный диапазон.

Двоичный поиск даст вам O(log N) сложность поиска в худшем случае, где N - длина массивов ARange и BRange соответственно.Эта особая перегрузка Array.BinarySearch со слабым типом может дать вам толчок.

Если вам нужно универсальное решение с хорошей читабельностью, вы можете перегрузить операции сравнения для пар (int, ARange) и(float, BRange).

После реализации этого алгоритма рассмотрите следующие оптимизации:

• определите ARange и BRange как struct с, чтобы уменьшить объем динамически выделяемой памятиулучшите локальность данных и сократите накладные расходы;
• , обеспечивающие ARange s, образуют непрерывную последовательность (т.е. без пропусков), оптимизируйте High и сохраните пары Low, B иверхняя граница, ограничивающая последовательность (скажем, как искусственный элемент в массиве);
• обеспечивает пользовательскую реализацию двоичного поиска, которая позволит вам сравнивать числа / числа с плавающей запятой с ARange s / BRange s;

• Еще один способ увеличить локальность данных (и, таким образом, уменьшить количество кешей ЦП) - разбить классы на массивы отдельных полей, поэтому в бинарном поиске вы можетеork с 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
  

Answer 2

Важными свойствами ваших данных является то, что для A и связанных B диапазонов:

1. Не перекрывайтесь.
2. Увеличивается монотонно.

Это означает, что простой двоичный поиск должен работать эффективно и предоставить вам O(log(n)) lookup.

Сохранять массив пар интервалов в порядке возрастания.

Чтобы выполнить поиск (скажем, A), запустите двоичный поиск по свойству start интервала «ключа» (в данном случае A), чтобы найти наивысший интервал, начало которого меньше, чем предмет для поиска. Затем проверьте, содержит ли этот интервал элемент (end >= toSearch). «Значение» (в данном случае связанный B интервал) тривиально для извлечения - это часть того же элемента массива.

Обратный поиск (т. Е. От B до A) работает почти так же.