11

我们正处于一个涉及流数据的实时和历史分析的 f# 项目的开始阶段。数据包含在 ac# 对象中（见下文），并作为标准 .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>因为线性查找时间并且因为没有随机访问元素，只是“仅向前”遍历。

根据这篇文章，Set<T>可能是一个不错的选择...

> " ...Vanilla Set<'a> 做得非常好。我更喜欢 'Set' 而不是 'List' 所以你总是可以 O(lg n) 访问最大和最小的项目，让你按插入日期/时间订购您的套装，以便有效访问最新和最旧的物品..."

编辑：殷朱的回答让我更清楚地知道我在问什么。我已经编辑了帖子的其余部分以反映这一点。此外，该问题的先前版本因引入历史分析要求而变得混乱。我省略了它们。

以下是实时过程步骤的细分：

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

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

4

4 回答 4

11

您应该考虑 FSharpx.Collections.Vector。Vector<T> 将为您提供类似数组的功能，包括索引 O(log32(n)) 查找和更新，在 O(1) 的距离内，以及在序列末尾添加新元素. 还有另一个 Vector 实现，可以在Solid Vector的 F# 中使用。非常有据可查，一些函数在大规模（元素计数 > 10K）时的执行速度提高了 4 倍。两种实现都表现得非常好，甚至可能超过 1M 元素。

于 2013-07-31T03:42:54.757 回答
10

在他的回答中，Jack Fox 建议使用 Greg Rosenbaum 的 FSharpx.CollectionsVector<'T>或 Solid Vector<'t>( https://github.com/GregRos/Solid )。我想我可以通过提供有关如何启动和运行每个社区的说明来回馈社区。

使用 FSharpx.Collections.Vector<'T>

这个过程非常简单：

  1. 使用 Project Manager Console 或 Manager Nuget Packages for Solution 下载 FSharpx.Core nuget 包。两者都可以在 Visual Studio -> 工具 -> 库管理器中找到。
  2. 如果您在 F# 脚本文件中使用它，请添加#r "FSharpx.Core.dll". 您可能需要使用完整路径。

用法：

open FSharpx.Collections

let ListOfTuples = [(1,true,3.0);(2,false,1.5)] 
let vector = ListOfTuples |> Vector.ofSeq

printfn "Last %A" vector.Last
printfn "Unconj %A" vector.Unconj
printfn "Item(0) %A" (vector.[0])
printfn "Item(1) %A" (vector.[1])
printfn "TryInitial %A" dataAsVector.TryInitial
printfn "TryUnconj %A" dataAsVector.Last

使用 Solid.Vector<'T>

使用 SolidVector<'t>的设置要复杂一些。但是 Solid 版本具有更多方便的功能，并且正如 Jack 指出的那样，具有许多性能优势。它还有很多有用的文档。

  1. 您需要从https://github.com/GregRos/Solid下载 Visual Studio 解决方案
  2. 一旦你下载了它，你将需要构建它，因为没有准备好使用预构建的 dll。
  3. 如果您像我一样，您可能会遇到许多缺失的依赖项，这些依赖项会阻止构建解决方案。就我而言，它们都与 nuit 测试框架相关（我使用了不同的框架）。只需下载/添加每个依赖项，直到解决方案构建。
  4. 一旦完成并构建了解决方案，您将在 Solid/Solid/bin 文件夹中拥有一个闪亮的新 Solid.dll。这就是我出错的地方。那是核心 dll，只够 C# 使用。如果您只包含对 Solid.dll 的引用，您将能够在 f# 中创建一个向量<'T>，但从那时起就会发生一些奇怪的事情。
  5. 要在 F# 中使用此数据结构，您需要同时引用文件夹中的 theSolid.dll和Solid.FSharp.dllwhich 。\Solid\SolidFS\obj\Debug\你只需要一个 open 语句 ->open Solid

下面是一些代码，显示了 F# 脚本文件中的用法：

#r "Solid.dll"
#r "Solid.FSharp.dll" // don't forget this reference

open Solid

let ListOfTuples2 = [(1,true,3.0);(2,false,1.5)] 
let SolidVector = ListOfTuples2 |> Vector.ofSeq

printfn "%A" SolidVector.Last
printfn "%A" SolidVector.First
printfn "%A" (SolidVector.[0])
printfn "%A" (SolidVector.[1])
printfn "Count %A" SolidVector.Count

let test2 = vector { for i in {0 .. 100} -> i }
于 2013-07-31T15:20:32.137 回答
5

假设您dataObj包含一个唯一的 ID 字段，那么任何设置的数据结构都适合您的工作。不可变数据结构主要用于函数式代码或持久性。如果你不需要这两个，你可以使用.Net 集合库中的HashSet<T>或SortedSet<T>。

一些特定于流的优化可能很有用，例如，Queue<T>为流中的最新数据对象保持固定大小，并将较旧的对象存储在更重的权重集中。我建议在切换到这种混合数据结构解决方案之前进行基准测试。

编辑：

在更仔细地阅读了您的要求后，我发现您想要的是一个具有用户可访问索引或后向枚举器的队列。在这种数据结构下，您的特征提取操作（例如平均/求和等）成本为 O(n)。如果您想在 O(log n) 中进行一些操作，您可以使用更高级的数据结构，例如区间树或跳过列表。但是，您必须自己实现这些数据结构，因为您需要将元信息存储在集合 API 后面的树节点中。

于 2013-07-30T08:40:07.200 回答
5

该事件被放置在数据结构中。这是我们试图确定的数据结构。它应该是 Set、Queue 还是其他结构？

没有更多信息很难说。

如果您的数据以升序的时间戳进入（即它们永远不会乱序），那么您可以使用某种队列或可扩展数组。

如果您的数据可能出现乱序并且您需要对它们进行重新排序，那么您需要一个优先队列或索引集合。

每秒大约 800 个事件

这些是对插入率的极其温和的性能要求。

为了特征生成的目的，提取或以某种方式迭代元素的子集。这可能是数据结构的最后 n 行/元素（即最后 1000 个事件或 10,000 个事件）或最后 x 秒/分钟内的所有元素（即最后 10 分钟内的所有事件）。理想情况下，我们需要一个能够让我们有效地做到这一点的结构。特别是，允许​​随机访问第 n 个元素而无需遍历所有其他元素的数据结构是有价值的。

如果您只想要靠近开头的元素，为什么要随机访问？您真的想要通过索引进行随机访问，还是真的想要通过其他键（例如时间）进行随机访问？

根据您所说，我建议使用Map由 a 维护的普通 F# 键控索引，MailboxProcessor它可以附加一个新事件并检索一个允许对所有事件进行索引的对象，即将所有事件包装Map在一个提供其自己的Item属性和实现的对象中的IEnumerable<_>。在我的机器上，这个简单的解决方案需要 50 行代码，每秒可以处理大约 500,000 个事件。

于 2013-08-02T11:59:53.983 回答