2

在做股市工作时，需要计算包括28天平均线、14天平均线等在内的计算指标。

此外，每天平均需要更新以包括最近一天的收盘价/最高价/最低价/成交量。

现在通常需要循环遍历数组以找到总和、平均值、最大值和最小值。

我认为队列（以动态数组或链表或您能想到的任何其他形式）似乎是基于 FIFO 进入/退出方法的完美数据结构。

问题：

  1. 队列的效率和可扩展性与哈希相比如何？
  2. 运行 Perl 脚本时，队列将不在内存中，因此必须初始化和处理（从 CSV 文件初始化的值），我知道这非常不相关，但哪种数据结构最适合使用每天执行的 Perl 脚本？
4

6 回答 6

2

使用PDL，您可以取一个更大的“数组”（一维矩阵）的切片，然后对该切片进行统计，然后再取另一个切片并重复。PDL 有许多内置的统计功能，如果这还不够，还有附加的PDL::Stats！

PDL 就像 Perl 的 MatLab 或 NumPy（我们认为更好！）。它针对数字数组的“循环”进行了高度优化。我将“循环”放在引号中，因为这些循环是在 C 级别实现的（听起来很快吧？）。看一眼！

于 2013-02-05T21:23:32.880 回答
1

这里没有足够的信息。您是否正在处理一整天的报价以获得每日最高价/最低价/最后价？

你是在每个仪器的基础上做平均值吗？

对于任何移动平均线，您可以只使用构成平均值总和的值列表。随着新值的增加，一个值会下降，然后重新计算。

因此，如果您通过仪器进行操作并即时计算，则为列表哈希。

于 2013-02-05T20:34:06.240 回答
1

如果你每天计算一次这些东西……使用最简单的数据结构来编码！计算真的需要这么多时间吗？如果是，请继续阅读。

总和和平均值可能更容易。如果您添加的是整数，则可以使用 FIFO 并将总和保存在变量中。每当您插入或删除一个元素时，相应地更新总和（加或减）。

如果添加浮点值，则上述方法可能会导致累积错误。如果值的大小非常不同和/或序列很长，则可能会发生这种情况。在这种情况下，您需要更复杂的东西（见下文）。

对于 max 和 min，最有效的数据结构是max/min-heaps。请注意，您可以将它们嵌入到数组中。您需要将它们与 FIFO 队列的元素进行交叉引用，以便立即找到每次都必须删除的元素。

最通用的解决方案是增强自平衡树。Cormen、Leiserson、Rivest 和 Stein 在“算法简介”的第 14 章中解释了增强数据结构。基本上，树将在每个节点中包含数据序列的一个元素。每个节点还包含其子树的总和、最小值和最大值。每次更新节点时，都必须更新从该节点到根的所有路径中的总和、最大值和最小值。在根中，您有全局总和、最大值和最小值。

您可以在此处找到增强自平衡树的 C++ 实现。

但是，由于您只需要固定数量的元素的总和、最小值和最大值，并且总是在一端插入并在另一端移除，因此可以使其更简单。您只需要一个循环缓冲区和一个嵌入数组的树（请参阅如何将这种树嵌入到数组中）。该树将包含部分总和、最小值和最大值，就像之前描述的增强树一样。优点是您不需要重新平衡树，因为您从不在序列中间插入/删除，并且树始终具有相同的大小。

为了获得最近 28 天、最近 14 天、上周和最近 3 天的统计信息（例如），您将使用循环缓冲区和每个周期的数组嵌入树：一个用于最后 3 天，前 4 天（7 减去 3）天，前 7 天，以此类推。每天，您都会获取每个缓冲区的最后一个数据并将其插入下一个缓冲区。

于 2013-02-06T06:54:44.900 回答
1

什么是最有效的真的取决于。

  • 哈希是无序的。他们可以通过字符串键在几乎恒定的时间内查找值。查找在计算上是昂贵的，并且至少比数组查找慢一个数量级。哈希的执行情况取决于“桶”的数量和键的数量。但是，对于所有非平凡的情况，哈希查找将比遍历数组来查找元素更快。哈希比数组需要更多空间。
  • Perl 中的数组具有数组（随机访问）和双向链表（通过 push、pop、shift、unshift）的特性。它们易于使用，而且速度足够快。如果要添加/删除多个元素，请使用切片或splice函数。splice是push..的概括unshift，并且比循环更快。

  • 字符串可用于存储整数数组。这是非常有效的，但也非常有限（仅限整数）。

    my $string = "";
my $i = ~ 0; # a really big number
$string .= chr $i; # get character from integer
# Access elements via `substr`:
my $j = ord substr $string, -1, 1; # last element; ord gets an int from a char

    使用字符串具有数组（随机访问）和单链表（附加很简单.=）的特点。其他操作也相当快（substr有很多用途）。

务实的程序员将对大多数顺序数据使用数组。List::Util他还可以利用来自和的高效函数，List::MoreUtils这些函数提供了sum、和（为了速度而用 C 语言编写）之类的函数。averagemaxmin

当您构建值列表并且只需要固定数量时，请在添加新元素时执行此操作：

push @array, $new_value;
shift @array if @array > $max_length; # keep constant length

这是节省空间的，但可能比简单地构建列表要慢，并且做

splice @array, 0, -$max_length; # remove all but $max_length last elems

要仅访问数组的特定部分（不分配新变量），请使用切片：

use List::Util qw/sum/;
my $last_24_sum = sum @array[-24 .. $#$array];  sum the last 24 elems

如果您想使用散列，但在编译时知道所有可能的字段，您可以为字段定义常量名称，并改用数组。所以不要做

my $hashref = { foo => $x, bar => $y }; # requires a lot of space
$hashref->{foo}; # slooow

但做

use constant {
    EL_FOO => 0, # make sure the integer range is continouus
    EL_BAR => 1, #   Perl doesn't have native enums
};
my $arrayref = [$x, $y];
$arrayref->[EL_FOO]; # faster!

反而。

在处理深度嵌套的数据时，缓存嵌套引用而不是在每次访问时重新计算它们有时会有所回报：

# disputable
for my $i (...) {
  for my $j (...)
    do_something_with $x->[$i][$j][$_] for 1 .. 1e3;
  }
}
# possibly better
for my $i (...) {
  for my $j (...) {
    my $aref = $x->[$i][$j];
    do_something_with $aref->[$_] for 1 .. 1e3;
  }
}
于 2013-02-05T22:47:20.577 回答
0

我只会使用一个简单%hash的键，它是时间戳的一些字符串化或数字化表示，而值是您的数据与该时间序列项相关联的值。您可以对哈希的键进行排序，例如

#numeric
@srtdKeys = sort{$a<=>$b}(keys(%hash));

或者

#string
@srtdKeys = sort(keys(%hash));

并遍历最后的 28 或 14 等，然后从哈希中检索值。

于 2013-02-05T20:23:50.077 回答
0

如果您每次运行都从头开始完全重建数据，也许您应该查看Statistics::Descriptive。

很遗憾您将其作为 CSV 文件。通过访问数据库服务器，您可以通过几个 SQL 查询来获取此信息。

于 2013-02-05T20:34:39.890 回答