Лучшая структура данных для разреженного двумерного массива с плавающей точкой, допускающего интерполяцию (perl)

Question

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

Я вижу 3 возможных структуры данных:

1. Разреженный2D-массив, может быть 10000 элементов, может быть заполнен на 1/3.

2. 2D-связанный список, то есть: 4 указателя списка для каждого элемента данных (таким образом, 3000 элементов становится 15000)

3. 2D-хэш (возможно, 3000 элементов) с 2 отсортированными списками ключей (возможно, по 100 элементов каждый) в каждом измерении.

Основная проблема заключается в эффективностипоиск, когда требуется интерполяция.Извлечение существующих элементов является относительно простым с любым методом.

В настоящее время я использую вариант 3, но поиск является чем-то вроде клооджа, поскольку мне приходится сканировать списки ключей каждого измерения, пока я не найдузанятые элементы, а затем выполните 2- или 4-стороннюю интерполяцию.Я использую moreUtils :: firstindx ($ _> $ requiredKey), чтобы найти ключи.Связанные списки (вариант 2) избавят меня от поиска в массивах списков ключей.

Вариант 1 также потребует сканирования, не потребует начального шага поиска по списку ключей, но может потребоваться поиск более пустых ячеек.,И вставка была бы настоящим хлопотом.

Я бы делал гораздо больше поисков, чем вставок.

Есть ли у кого-нибудь какие-либо предложения по наиболее эффективной структуре данных.

Answer 1

Поскольку вы в основном выполняете поиск по продолжительности жизни, а поиск по расстоянию и нескольким вставкам, я бы использовал отсортированные массивы для поиска записей с помощью бинарного поиска.

• Определение местоположения существующего элемента: O (log N)
• Определение местоположения отсутствующего элемента: O (log N)
• Вставка: O (N)

Дано,

my @data = (
   [ $lifespan0, $distance0, $bid0, $ask0 ],
   [ $lifespan1, $distance1, $bid1, $ask1 ],
   ...
);

my $lifespan_search_cmp = sub { $a <=> $data[$b][0] };
my $distance_search_cmp = sub { $a <=> $data[$b][1] };

Сначала создайте индексы:

my @by_lifespan = sort { $data[$a][0] <=> $data[$b][0] } 0..$#data;
my @by_distance = sort { $data[$a][1] <=> $data[$b][1] } 0..$#data;

Для поиска:

my $i = binsearch_first \&$lifespan_search_cmp, $lifespan, @by_lifespan;
my $j = binsearch_first \&$distance_search_cmp, $distance, @by_distance;

my @lifespan_matching_idxs = get_run_forward \&$lifespan_search_cmp, $lifespan, $i, @by_lifespan;
my @distance_matching_idxs = get_run_forward \&$distance_search_cmp, $distance, $j, @by_distance;

my @cross_match_idxs = do {
   my %lifespan_matching_idxs = map { $_ => 1 } @lifespan_matching_idxs;
   grep { $lifespan_matching_idxs{$_} }
      @distance_matching_idxs
};

if (@cross_match_idxs) {
   # Exact match(es) found.
   ...
} else {
   my $lifespan_lowerbracket;
   my $lifespan_upperbracket;
   if ($i >= 0) {
      $lifespan_lowerbracket = $lifespan;
      $lifespan_upperbracket = $lifespan;
   } else {
      die "Can't interpolate" if ~$i == 0 || ~$i >= @by_lifespan;
      $lifespan_lowerbracket = $data[~$i    ][0];
      $lifespan_lowerbracket = $data[~$i - 1][0];
   }

   my $distance_lowerbracket;
   my $distance_upperbracket;
   if ($i >= 0) {
      $distance_lowerbracket = $distance;
      $distance_upperbracket = $distance;
   } else {
      die "Can't interpolate" if ~$j == 0 || ~$j >= @by_distance;
      $distance_lowerbracket = $data[~$j    ][1];
      $distance_upperbracket = $data[~$j - 1][1];
   }

   ...
}

Чтобы вставить:

my $i = binsearch_first \&$lifespan_search_cmp, $lifespan, @by_lifespan;
my $j = binsearch_first \&$distance_search_cmp, $distance, @by_distance;

push @data, [ $lifespan, $distance , $bid, $ask ];

splice(@by_lifespan, $i >= 0 ? $i : ~$i, 0, $#data);
splice(@by_distance, $j >= 0 ? $j : ~$j, 0, $#data);

Subs:

sub binsearch_first(&$\@) {
   my  $compare = $_[0];
   #my $value   = $_[1];
   my  $array   = $_[2];

   my $min = 0;
   my $max = $#$array;
   return -1 if $max == -1;

   my $ap = do { no strict 'refs'; \*{caller().'::a'} };  local *$ap;
   my $bp = do { no strict 'refs'; \*{caller().'::b'} };  local *$bp;

   *$ap = \($_[1]);
   while ($min <= $max) {
      my $mid = int(($min+$max)/2);
      *$bp = \($array->[$mid]);

      my $cmp = $compare->();
      if ($cmp < 0) {
         $max = $mid - 1;
      }
      elsif ($cmp > 0) {
         $min = $mid + 1;
      }
      else {
         return $mid if $mid == $min;
         $max = $mid;
      }
   }

   # Converts unsigned int to signed int.
   return unpack('j', pack('J', ~$min));
}

sub get_run_forward(&$\@) {
   my  $compare = $_[0];
   #my $value   = $_[1];
   my  $start   = $_[2];
   my  $array   = $_[3];

   return if $start < 0;

   my $ap = do { no strict 'refs'; \*{caller().'::a'} };  local *$ap;
   my $bp = do { no strict 'refs'; \*{caller().'::b'} };  local *$bp;

   *$ap = \($_[1]);

   my $i = $start;
   while ($i <= $#$array) {
      *$bp = \($array->[$i]);

      my $cmp = $compare->()
         and last;

      ++$i;
   }

   return wantarray ? ($start..$i-1) : $i-1;
}

Возможно, вы захотите использовать допуск в сравнениях с плавающей запятой (то есть в $distance_search_cmp).