1

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

例如：

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

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

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

最多7FF就可以了，这个算法可以用。尽管它不是最好的，但它已经达到了它的目的。但我试图找到更有效的东西，我也想把它应用到 29 位。从 0 到 7FFFFFFF 需要很长时间。

任何想法将不胜感激。

PS：算法应该是用Java编写的。

4

1 回答 1

0

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

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

伪算法将类似于：

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，这些更多或更少相同的东西）。

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

(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 个项目，并且您只需要执行一次，我会选择第一个算法，它可能需要不超过几秒钟的时间来完成（确切的运行时间将取决于忽略列表中的早期匹配项）。

于 2012-12-19T10:06:37.247 回答