c++ - 有效关联事件

Question

我正在开发 C++ Windows 应用程序，需要添加关联功能。目前我有两个事件制作人，每个制作人都会生成类似的事件。两个生产者的事件生成的平均组合速率为 2k/sec。然而，它在负载下跳到 300-500 k/sec。这是事件的简化版本的样子

Event
    ProcessId // e.g. 1234 
    Action    // e.g. 0, 1, 2
    Timestamp // e.g. LARGE_INTEGER Windows timestamp

我需要构建的关联规则如下所示

Filter

    // events are from the same process
    ev1.ProcessId == ev2.ProcessId  

    &&

    // events have specific types
    ( ev1.Action == 0 && ev2.Action == 1) 

    &&

    // they are less than 2 secs apart
    ( abs(ev1.Timestamp - ev2.Timestamp) < 2 seconds) 

我在想

• 带有队列(用于时间和 Action 关联)的 HashMap (ProcessId 作为键)
• 提升管道(github 上的示例)

但我不确定如何处理快速事件驱逐，因为我需要保持较低的 CPU 和内存利用率。

任何人都可以提出一个解决方案，使我能够有效地关联事件(对 CPU 的影响最小且内存占用少)吗？

Answer 1

由于相关窗口相当小，您可以从那里拆分数据开始，以便于驱逐。

将流 1(较慢/较小的流)中的所有对象存储在三个 HashMap 的循环缓冲区中。当您刚刚获得的事件的时间戳比您放入最新 HashMap 中的第一个时间戳早两秒以上时，您清空最旧的 HashMap 并将其放在前面，将所有其他 HashMap 向下移动一个步骤。您还记录了您现在放入此存储桶中的第一个项目的“开始时间”。

这允许您保留来自流 1 的大约 4-6 秒数据的循环缓冲区，这为未按正确顺序传递的消息提供了一点缓冲区。

对于流 2(更大/更快的流)，您只需在所有 HashMap 中进行查找。当您获得匹配项时，您可以使用相关函数检查它是否确实是真正的匹配项。这在 O(m+b*n log k/b) 中运行 b HashMap (桶)和 k 流中每秒的消息 n，在 n 和 m 消息流上。对于 b=3，您有 O(m + n log k) 流 n 中每秒 k 条消息。空间要求应在 6k 左右。

如果只使用三个 hashmap 会使性能过高(无论是在内存使用还是 cpu 使用方面(清空 hashmap 确实需要一些时间))，您可以使用更多 hashmap(增加 b) .只保留足够的时间来记住你需要记住的时间，再加上一两次，并记住迟到的小缓冲区。