perl - 允许插值的稀疏有序二维浮点数组的最佳数据结构(perl)
问题描述
数据是股票期权。我想根据到期前的天数(int)和标准化距离(浮动)制作一个二维数组,其值是标准化买入价和卖出价的列表。如果所需的元素不在数组中,我希望能够在最近的元素之间进行插值。
我看到了 3 种可能的数据结构:
一个稀疏的二维数组,可能有 10000 个元素,可能是 1/3。
一个二维链表,即:每个数据元素有 4 个列表指针(因此 3000 个元素变为 15000 个)
一个 2D 散列(可能有 3000 个元素),每个维度中有 2 个排序的键列表(每个可能有 100 个元素)。
主要问题是需要插值时的有效检索。使用任何方法检索现有元素都相对简单。
我目前正在使用选项 3,但检索有点麻烦,因为我必须沿着每个维度的键列表扫描,直到找到被占用的元素,然后进行 2 或 4 路插值。我使用 moreUtils::firstindx($_ > $desiredKey) 来查找密钥。链表(选择 2)可以让我不用搜索键列表数组。
选择 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);
潜艇:
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;
}
您可能希望在浮点比较中使用容差(即 in $distance_search_cmp
)。
推荐阅读
- tensorflow - dropout后减少的参数数量
- java - 我的 else if 语句有什么问题?
- html - 将网站部署到 Netlify 时不出现 FontAwesome 图标
- javascript - 在使用 jsconfig.conf 和 webpack 管理的 js 项目中导入图像
- c++ - 香农熵算法返回负值
- java - Firebase - 允许用户只访问自己的数据
- node.js - 渲染页面时 NextJS 错误,发布后
- uwp - 调试或发布我应该将哪些文件复制到 uwp 应用程序的 nuget 打包中的目标位置?
- arrays - 电子表格 IF 大于 0,使另一个单元格等于这个
- c# - 来自 AWS 的 API 调用失败