4状態データ構造の最適化

Question

私は多くのの4つの状態の1つを持つことができる同じデータ構造のインスタンスを操作しています。私は繰り返し、二つの機能f、g

g((True, True)) = (True, False) 
g((True, False)) = (True, True) 
g((False, True)) = (False, False) 
g((False, False)) = (False, True) 

と

f((True, True)) = (False, False) 
f((True, False)) = (False, True) 
f((False, True)) = (True, False) 
f((False, False)) = (True, True) 

は、私が改善することができますを適用し、それらのデータ構造で

(True, True) 
(True, False) 
(False, True) 
(False, False) 

：現在、私はTrue/Falseペアを使用して状態を実装しますそれらの2つの機能のためのこのデータ構造に基づいていますか？ （速度を最適化したいです）

Answer 1

0..3の範囲の整数を使用し、ビット演算（gxors、1; fxors、3）を使用して状態遷移を実装します。

Answer 2

これらの状態を操作するために使用するコードは、状態の格納方法よりもパフォーマンスに大きな影響を与えます。そして、それを操作する必要がどのようにそれを格納するための最良の方法を決定します。関係するアルゴリズムについてもっと知らなくても、データ表現にコメントすることは不可能です。

ステートは自然に2つのブール値として表されていますか、それとも4つの異なるステートですか？

Answer 3

クォードツリーとクワッドキーを使用して状態を保存できます。高速検索が必要な場合やサブツリーを検索する必要がある場合は、クエリがより効率的になります。あなたはさらに四分木を見て、モンスター曲線を使うことができます。モンスターカーブの完成度はスペースを満たしますが、まだカーブです。あなたの状態をその曲線に沿って配置すると、それらを2次元で並べ替えて1次元に減らすことができます。それは階層的クラスタを持つようなものです。最も有名なモンスター曲線はヒルベルト曲線です。

Answer 4

各状態のシンボル表現を使用して状態を実装します。ここでは

(True, True) == 3 decimal or 11 binary 
(True, False) == 2 decimal or 10 binary 
(False, True) == 1 decimal or 01 binary 
(False, False) == 0 decimal or 00 binary 

はそれだ

g((True, True)) = (True, False) 
is the same as 
g(3) == 2 decimal 
or 
XOR with 01 binary operation 

g((True, False)) = (True, True) 
is the same as 
g(2) == 3 
or 
XOR with 01 binary operation 

g((False, True)) = (False, False) 
is the same as 
g(1) == 0 
or 
XOR with 01 binary operation 

g((False, False)) = (False, True) 
is the same as 
g(0) == 1 
or 
XOR with 01 binary operation 

と

f((True, True)) = (False, False) 
is the same as 
f(3) = 0 
or 
XOR with 11 binary operation 

f((True, False)) = (False, True) 
is the same as 
f(2) = 1 
or 
XOR with 11 binary operation 

f((False, True)) = (True, False) 
is the same as 
f(1) = 2 
or 
XOR with 11 binary operation 

f((False, False)) = (True, True) 
is the same as 
f(0) = 3 
or 
XOR with 11 binary operation 

fとgの関数があります！ あなたの質問にお答えしたいと思います。

Answer 5

さて、最も簡単なことは、関数を使うのではなく、結果によって与えられた引数と値によって与えられた2つの辞書fとgを作ることです。

これは、ペアを0から3にマッピングし、2つの配列fとg（配列はルックアップのリストより速く、numpyの配列はたぶん高速です）、または2つの関数を作成するよりも遅くなります。事実f(x)= 3-x（またはビット単位ではない：~x）とg(x)=x^1（^は排他的論理和）です。