优化四状态数据结构

我操纵相同的数据结构，其能够具有四种状态之一的许多实例。目前我使用True /False双执行状态：优化四状态数据结构

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

有了这些数据结构我多次申请两个功能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)

我可以提高在这两个函数的数据结构上？（我想优化速度。）

来源

2012-02-16 Randomblue

你怎么做* *与数据结构？您可以将它们映射为二进制 - 即，使用0,1,2,3 – 2012-02-16 01:45:38

@AndrewJaffe：用数据结构上的操作更新的问题。 – Randomblue 2012-02-16 01:51:45

使用0..3范围内的整数并通过位算术实现状态转换（g xors，1; f xors与3）。

来源

2012-02-16 01:55:34

你用它来操作这些状态的代码会比你如何存储的状态对性能具有更大的影响。而您如何操作它将决定存储它的最佳方式。如果不了解更多涉及的算法，就不可能评论数据表示。

是自然表示为两个布尔值状态，或者是四种不同的状态？

来源

2012-02-16 01:45:49

谢谢。我用我的数据结构中的两个操作编辑了这个问题。 – Randomblue 2012-02-16 01:50:37

您可以使用一个四叉树和存储状态的quadkey。当您需要快速查找以及何时需要查找子树时，查询效率会更高。您可以进一步查看四叉树并使用怪物曲线。怪物曲线的完整性填补了空间，但它仍然是一条曲线。沿着这条曲线放置你的状态，你可以将它们排列成二维，从而将它减小到一维。这就像有一个层次集群。最着名的怪物曲线是希尔伯特曲线。

来源

2012-02-16 01:53:19 Bytemain

使用每个状态的符号表征实施状态：

(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

这里是函数f和g

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

这就是它！希望我已经回答了你的问题。

来源

2012-02-16 02:00:18

嗯，最简单的事情不是使用函数，而是使用由结果给出的参数和值给出的键构建两个字典f和g。

这将比将映射对映射到0 ... 3并使两个数组f和g（数组将快于列表查找，numpy数组甚至更快）或甚至两个函数其实f(x)= 3-x（或不按位：~x）和g(x)=x^1（^是XOR），这可能是最快的。

来源

2012-02-16 02:00:44

优化四状态数据结构

回答

相关问题