algorithm - 优化 Modbus 请求

Question

我有一个 QMap<int, MyData>其中键是 Modbus 寄存器的地址，MyData是我自己的结构，其中包含一些对这个问题不重要的信息。

键集可能非常大(比如 2000 个值)，其中一些键彼此靠近。例如:

1, 2, 3, 4, 7, 23, 24, 25, 40, 41, 43, ...

我的目标是最终得到 QList<QPair<int,int>> QPair 的项目在哪里类是我将发送的每个 Modbus 请求的下限和上限。应该优化此列表以将相应的值或彼此“非常接近”的值连接在一起。这是为了减少 Modbus 请求的数量，并与请求的数据量进行权衡。

在上面的例子中我想:

[1, 7], [23, 25], [40, 43]  

我将设置几个约束来为每个请求赋予权重。从地址 1 到 7 请求数据比 1 到 4 然后只有 7 值，但如果 7 是 16 则不是......另一个限制是单个请求的最大长度:即使有很多相应的地址，它们也必须分成长度为 N 的段。

我正在询问一些如何处理此类问题的指南。

我到现在为止的想法。使用元素 x 和 x-1 之间的差异创建第二个数组:

1, 2, 3, 4, 7, 23, 24, 25, 40, 41, 43, ...
   1, 1, 1, 3, 16,  1,  1, 15,  1, 2, ...

然后扫描这个数组并找到低于“权重阈值”的任何数字(假设是 4)并创建第一个 QPair包括这些地址的列表:

[1, 7], [23, 25], [40, 43]

最后，检查每对的长度，如果大于允许的最大长度，则将其拆分。

你认为这是一种合理的做法吗？是否有一些著名的算法可能适合这里？做 QMap是一个好的选择？我使用它是因为当我从 Modbus 接收到每个值时，我将发出一个信号，如下所示:

void dataReceived(int address, quint16 value);

因此很容易检索到相关的 MyData .

Answer 1

您认为的解决方案很棒。它解决了 O(n) 中的问题复杂。就复杂性而言，没有比这更好的了。由于构建列表需要遍历所有元素。但是......你可以做得更快一点(假设数组已排序)

构建列表QList<QPair<int,int>>你正在做三个大小为 n 的迭代:

1 - 用差异构建数组。

2 - 创建遍历上一步中构建的数组的列表

3 - 检查每对的长度，如果大于允许的最大长度，则将其拆分。

您只能在一次迭代(一步)中完成；跟踪变量的开始、对的结束和大小。当您发现一个值与之前的值的差异大于"weight threshold"或尺寸大于"maximun allowable" 时 -> 添加与列表配对并使用下一个值重置变量开始、结束和大小。

无论如何，因为列表最多只有 2000 个值，所以差别不大。

关于你的另一个问题。是QMap是一个很好的选择，因为提供 O(1)检索数据的时间复杂度。