1

CAN (Controller Area Network) を使用しており、ハードウェア バッファー スロットのマスクと ID を生成するアルゴリズムを考え出そうとしています。

例えば：

マイクロコントローラーで受け取りたい ID と、マイクロコントローラーで無視したい ID を含む 2 つの整数配列があります。

ID を表すビット数 (11 ビット) に応じて、最小マスク 0 から最大値に変更します。

そこで、0 から 7FF に移動して、受け入れたい ID のリストから 1 つ以上のメッセージを含み、受け入れたくない ID を含まないマスクを見つけようとします。

7FFまでOK、このアルゴリズムが使えます。確かにそれは最高ではありませんが、その目的を果たしました. しかし、私はもっと効率的なものを見つけようとしており、これを 29 ビットにも適用したいと考えています。0 から 7FFFFFFF に移行するには、非常に長い時間がかかります。

どんなアイデアでも大歓迎です。

PS: アルゴリズムは Java で書かれているはずです。

4

1 に答える 1

0

すべての可能な解決策が必要ではなく、「受け入れリスト」の少なくとも 1 つの項目に一致し、「無視リスト」の項目に一致しないマスクのリストのみが必要な場合は、次の方法で現在のアルゴリズムを改善できる可能性が高くなります。単純なO(n*m)アルゴリズムを作成します (ここでn、 とmはリストの長さです)。

リストが比較的短い場合、これは 0 から 2 29まで反復するよりもはるかに高速に機能します。さらに、これらのリストが変更されることがなく、これを 1 回だけ行う必要がある場合は、おそらくこれが最適な選択です。

疑似アルゴリズムは次のようになります。

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)です)。

「無視リスト」に多数のアイテムがあり、リストを頻繁に検索する必要がある場合は、無視されたアイテムをトライ(または基数トライ、またはDAWG、これらはより多くまたは少ない同じもの）。

候補ごとに、トライを少しずつ調べて、マスク1のビットの代わりにビットがあるアイテムをすばやく破棄します。0これはO(n+m)複雑さのようなものを与えます（O(m)トライを構築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 項目の 2 つのリストがあり、これを 1 回だけ実行する必要がある場合、最初のアルゴリズムを選択します。終了までにおそらく数秒しかかかりません (正確な実行時間は、無視リストの初期の一致)。

于 2012-12-19T10:06:37.247 に答える