真理的最佳实施table
Optimal implementation of truth table
我确定了一个真相table 如下面的
prev_state| input1 | input2 |next_state| Action
(def/new) |(Disable/Enable)|(Off/On)| |
def | D | Off | def | Nothing
def | D | On | def | Nothing
def | E | Off | def | Nothing
def | E | On | new | call function1
new | D | Off | def | call function2
new | D | On | def | call function2
new | E | Off | def | call function2
new | E | On | new | Nothing
我想知道实现此目标所需的最少检查次数是多少。
我想使用 Karnaugh map 如下所示:
00| 01| 11| 10
-----------------
0 | A | A | B | A |
-----------------
1 | C | C | A | C |
-----------------
其中A什么都不对应,B调用function1,C调用function2
据我所知,你有 2 个 A 的 2 个组合和一个 A 的总共 3 个组合
1个
和 2 个 C 的 2 个组合
是不是说最少要比较3+1+2=6次?
但是因为 A 什么都不做,所以最小的实现需要
只有 B 和 C 的 3 种组合?
测试实施
if (prev_state == new && input1 == disable) {
function2();
}
else if (prev_state == new && input2 == Off) {
function2();
}
else if (input1 == enable && input2 == On) {
function1();
}
现在我也看到了上面那个和这个哪个更好:
if ((prev_state == new && input1 == disable) || (prev_state == new && input2 == Off)) {
function2();
}
else if (input1 == enable && input2 == On) {
function1();
}
感谢那些提出查找 table 的人,它的复杂度为 O(1),但占用了 space 内存。
我现在意识到我更愿意有一个不使用额外内存的解决方案。您是否同意使用卡诺图是得出最少比较量的有效方法?
如果行为是静态的,那么做测试是没有用的,你可以
使用一个 3 维数组,其中每个值都是一对下一个状态和动作,第一个维度是 prev_state 0/1,第二个输入 1 D/E -> 0 /1,第三个输入 2 off/on -> 0/1
但是因为您的输入非常有限,您也可以只将 3 个索引编码为一个 = prev_state * 4 + input1 * 2 + input2
并使用大小为 8 的简单向量。正如 Schwern 在评论中建议的那样,您可以还对 prev_state * 4 + input1 * 2 + input2
的结果执行 switch/case
I was wondering what is the minimum number of checks that you need to achieve ...
零。使用查找 table
void f_Nothing(void) {
; // do nothing
}
void f_function1(void) {
; // something interesting
}
void f_function2(void) {
; // something interesting
}
int main(void) {
typedef void (*fun_type)(void);
fun_type f[2][2][2] = { //
{{f_Nothing, f_Nothing}, {f_Nothing, f_function1}},
{{f_function2, f_function2}, {f_function2, f_Nothing}}};
bool prev_state, input1, input2;
//...
f[prev_state][input1][input2]();
OP 后来评论 。
if ( (input1 == E && input2 == ON) && (prev_state == def)) function1();
if (!(input1 == E && input2 == ON) && (prev_state == new)) function2();
// or
if (input1 == E && input2 == ON) {
if (prev_state == def) function1();
} else {
if (prev_state == new) function2();
}
你可以删除一些重复的测试,但它在实践中是否有很大的不同取决于编译器的优化。
if (prev_state == new) {
if (input1 == disable || input2 == Off) {
function2();
}
} else {
if (input1 == enable && input2 == On) {
function1();
}
}
或者:
if (input1 == disable || input2 == Off) {
if (prev_state == new) {
function2();
}
} else {
if (prev_state == def) {
function1();
}
}
我会做如下的事情。
int check = (int)((prev_state == new) << 2 | (input1 == E)<<1 | (input2 == on));
/*def | E | On | new | call function1 == 3
new | D | Off | def | call function2 == 4
new | D | On | def | call function2 == 5
new | E | Off | def | call function2 == 6 */
if (check == 4 || check == 5 || check == 6)
function2();
else if (check == 3)
function1();
我确定了一个真相table 如下面的
prev_state| input1 | input2 |next_state| Action
(def/new) |(Disable/Enable)|(Off/On)| |
def | D | Off | def | Nothing
def | D | On | def | Nothing
def | E | Off | def | Nothing
def | E | On | new | call function1
new | D | Off | def | call function2
new | D | On | def | call function2
new | E | Off | def | call function2
new | E | On | new | Nothing
我想知道实现此目标所需的最少检查次数是多少。
我想使用 Karnaugh map 如下所示:
00| 01| 11| 10
-----------------
0 | A | A | B | A |
-----------------
1 | C | C | A | C |
-----------------
其中A什么都不对应,B调用function1,C调用function2
据我所知,你有 2 个 A 的 2 个组合和一个 A 的总共 3 个组合 1个 和 2 个 C 的 2 个组合
是不是说最少要比较3+1+2=6次? 但是因为 A 什么都不做,所以最小的实现需要 只有 B 和 C 的 3 种组合?
测试实施
if (prev_state == new && input1 == disable) {
function2();
}
else if (prev_state == new && input2 == Off) {
function2();
}
else if (input1 == enable && input2 == On) {
function1();
}
现在我也看到了上面那个和这个哪个更好:
if ((prev_state == new && input1 == disable) || (prev_state == new && input2 == Off)) {
function2();
}
else if (input1 == enable && input2 == On) {
function1();
}
感谢那些提出查找 table 的人,它的复杂度为 O(1),但占用了 space 内存。 我现在意识到我更愿意有一个不使用额外内存的解决方案。您是否同意使用卡诺图是得出最少比较量的有效方法?
如果行为是静态的,那么做测试是没有用的,你可以
使用一个 3 维数组,其中每个值都是一对下一个状态和动作,第一个维度是 prev_state 0/1,第二个输入 1 D/E -> 0 /1,第三个输入 2 off/on -> 0/1
但是因为您的输入非常有限,您也可以只将 3 个索引编码为一个 =
prev_state * 4 + input1 * 2 + input2
并使用大小为 8 的简单向量。正如 Schwern 在评论中建议的那样,您可以还对prev_state * 4 + input1 * 2 + input2
的结果执行 switch/case
I was wondering what is the minimum number of checks that you need to achieve ...
零。使用查找 table
void f_Nothing(void) {
; // do nothing
}
void f_function1(void) {
; // something interesting
}
void f_function2(void) {
; // something interesting
}
int main(void) {
typedef void (*fun_type)(void);
fun_type f[2][2][2] = { //
{{f_Nothing, f_Nothing}, {f_Nothing, f_function1}},
{{f_function2, f_function2}, {f_function2, f_Nothing}}};
bool prev_state, input1, input2;
//...
f[prev_state][input1][input2]();
OP 后来评论
if ( (input1 == E && input2 == ON) && (prev_state == def)) function1();
if (!(input1 == E && input2 == ON) && (prev_state == new)) function2();
// or
if (input1 == E && input2 == ON) {
if (prev_state == def) function1();
} else {
if (prev_state == new) function2();
}
你可以删除一些重复的测试,但它在实践中是否有很大的不同取决于编译器的优化。
if (prev_state == new) {
if (input1 == disable || input2 == Off) {
function2();
}
} else {
if (input1 == enable && input2 == On) {
function1();
}
}
或者:
if (input1 == disable || input2 == Off) {
if (prev_state == new) {
function2();
}
} else {
if (prev_state == def) {
function1();
}
}
我会做如下的事情。
int check = (int)((prev_state == new) << 2 | (input1 == E)<<1 | (input2 == on));
/*def | E | On | new | call function1 == 3
new | D | Off | def | call function2 == 4
new | D | On | def | call function2 == 5
new | E | Off | def | call function2 == 6 */
if (check == 4 || check == 5 || check == 6)
function2();
else if (check == 3)
function1();