java - CAN 硬件接收缓冲区的掩码生成

Question

我正在使用 CAN( Controller 局域网)，我正在尝试提出一种算法来生成硬件缓冲区插槽的掩码和 ID。

例如:

我有两个整数数组，其中包含我希望微 Controller 接收的 ID，以及我希望微 Controller 忽略的 ID。

我现在从最小掩码 0 到最大值，具体取决于表示 ID 的位数(11 位)。

因此，我将从 0 到 7FF 并尝试找到一个掩码，该掩码可以包含我想要接受的 ID 列表中的一条或多条消息，并且不包含我不想接受的 ID。

最多7FF就可以了，可以用这个算法。当然它不是最好的，但它达到了它的目的。但我正在尝试寻找更高效的东西，并且我也想将其应用到29位。从 0 到 7FFFFFFF 需要很长时间。

任何想法将不胜感激。

PS:该算法应该用Java编写。

Answer 1

如果您不需要所有可能的解决方案，而只需要一个掩码列表，该列表至少与“接受列表”中的一项相匹配，并且与“忽略列表”中的任何项都不匹配，那么您很可能可以改进您的解决方案通过编写一个简单的 O(n*m) 算法(其中 n 和 m 是列表长度)来实现当前算法。

如果您的列表相对较短，这会比从 0 迭代到 2²⁹ 快得多。此外，如果这些列表永远不会改变，并且您只需要执行一次，那么这可能是您的最佳选择。

伪算法类似于:

for each candidate in the "accept list"
   do a bitwise AND with all items in the "ignore list"
   if there is a match then (break as soon as you find a match)
       this candidate cannot be matched
   else
       this candidate is one of the solutions

当然，这将返回只能匹配单个项目的掩码。如果您想要最小的掩码集，您可以对候选列表进行后处理并丢弃已包含在其他掩码中的掩码(即额外的 O(n*n))。

如果您的“忽略列表”中有大量项目，并且需要经常查找该列表，那么将您忽略的项目放在 trie 中会更有意义。 (或 radix trie ，或 DAWG ，这些或多或少是相同的东西)。

对于每个候选者，您将一点一点地遍历 trie 并快速丢弃掩码中具有 1 位代替 0 位的项目。这会产生类似于 O(n+m) 的复杂性(O(m) 来构建 trie，O(1*n) 来构建查找接受列表中每个项目的字典树):

(presuming you have built a trie from "ignore list" items)
for each candidate in the "accept list"
    get a binary representation of the candidate
    perform a dfs of the trie 
        if node at level k is 1 and candidate bit at position k is 0
        then 
            discard that subtree
        else
            continue searching until the last leaf

这完全取决于列表的实际长度以及您需要执行此搜索的频率。如果你有两个各有 10000 个项目的列表，并且你只需要执行一次，我会选择第一个算法，它可能需要不超过几秒钟的时间来完成(确切的运行时间将取决于列表的数量)忽略列表中的早期匹配)。