data-structures - F# 用于高频实时流数据的不可变数据结构

Question

我们正处于一个 f# 项目的开始阶段，该项目涉及流数据的实时和历史分析。数据包含在 C# 对象中(见下文)，并作为标准 .net 事件的一部分发送。在实时情况下，我们通常接收到的事件数量变化很大，从每台仪器每秒不到 1 个事件到每秒约 800 个事件，因此可能会非常突发。一般情况下，每个工具每天可能会累积 500 万行/元素

C# 事件数据结构的通用版本如下所示:

public enum MyType { type0 = 0, type1 = 1}

public class dataObj
{
    public int myInt= 0;
    public double myDouble;
    public string myString;
    public DateTime myDataTime;
    public MyType type;
    public object myObj = null;

}

我们计划以两种方式在 f# 中使用此数据结构:

1. 使用有监督和无监督机器学习(CRF、聚类模型等)进行历史分析
2. 使用上述模型对数据流进行实时分类

数据结构需要能够随着我们添加更多事件而增长。这排除了 array<t>因为它不允许调整大小，尽管它可以用于历史分析。数据结构还需要能够快速访问最近的数据，并且理想情况下需要能够跳转到 x 点之前的数据。这排除了 Lists<T>因为线性查找时间并且因为没有对元素的随机访问，只是“仅向前”遍历。

根据this post , Set<T>也许是一个不错的选择...

> " ...Vanilla Set<'a> does a more than adequate job. I'd prefer a 'Set' over a 'List' so you always have O(lg n) access to the largest and smallest items, allowing you to ordered your set by insert date/time for efficient access to the newest and oldest items..."

编辑:朱音的回答让我更加清楚地了解了我的问题。我编辑了帖子的其余部分以反射(reflect)这一点。此外，该问题的先前版本因引入历史分析要求而变得困惑。我已经省略了它们。

以下是实时过程的步骤分割:

1. 收到实时事件
2. 该事件被放置在数据结构中。 这是我们试图确定的数据结构。应该是 Set<T> ，或其他结构？
3. 为了生成特征，提取或以某种方式迭代元素的子集。这可以是数据结构的最后 n 行/元素(即最后 1000 个事件或 10,000 个事件)，也可以是最后 x 秒/分钟中的所有元素(即最后 10 分钟中的所有事件)。理想情况下，我们需要一个能够让我们高效地完成此操作的结构。特别是，允许​​随机访问第 n 个元素而不迭代所有其他元素的数据结构是有值(value)的。
4. 生成模型的特征并将其发送到模型进行评估。
5. 我们可能会修剪旧数据的数据结构以提高性能。

所以问题是，用于存储我们将用于生成特征的实时流事件的最佳数据结构是什么。

Answer 1

您应该考虑FSharpx.Collections.Vector 。 Vector 将为您提供类似数组的功能，包括索引 O(log32(n)) 查找和更新(在 O(1) 的范围内)，以及向序列末尾添加新元素。 Vector 还有另一种实现，可以在 F# 中使用 Solid Vector 。文档非常齐全，某些函数在大规模(元素计数 > 10K)时执行速度提高了 4 倍。两种实现在元素数量达到或超过 1M 时都表现良好。