西门子中国总代理商|驱动器代理商

数据结构 算法 效率

一、问题背景

为了让您更好的理解此贴，请先移驾看帖子

【万泉河】我现在告诉你们不用M和T的程序好在哪里

中Zane版在44楼提出的问题，

本帖要说的就是IO地址冲突检测，也就是IO地址性检测中，“空间换时间”策略的应用。

二、由来

在帖子[旧事]--初踏征途虽然实现了地址冲突检测的功能，但由于对数据组织的仓促，以至于在做地址雷同查找操作时（查找历史数据中是否已经存在当前的设定值），使用了遍历存储单元的方法，因此查找效率低下，当IO点的规模越大，需要进行的比较操作的次数越多。

当时手头有别的事情要做，也就没有再深究。

原来的数据规划如图所示

数据块DB中存储了所有有有效的历史数据，每一批历史数据由两部分组成，A区(输入I地址）数据（包含4个DWORD数据）和B区(输出O地址）数据（3个DWORD数据），第个DWORD包括IO地址的字节号WORD和位号WORD,图示共有三批历史数据、一批当前数据，

算法：分别把当前批数据中的A区数据中的每个数据与每批历史数据中A区中的每个数据做比较，当前批数据中的B区数据中的每个数据与每批历史数据中B区中的每个数据也做比较，如果数值相同，则使能输出标志Same。

上个看《算法（第4版》

3.4节的“散列表”（Hash Table），突然想起来可以把数据再重新组织一下，提高查找效率，于是有了此帖。

三、改进

现将数据重新组织如下，IO地址格式为Byte.Bit，每个Byte有8个Bit，这里使用一个包含8个数据类型为INT元素的数据代表一个寻址字节Byte，在博途平台下的PLC数据类型中我们新建一个名为BitsTable的数据类型，它包含一个数组，有8个INT类型的元素，我们将其默认值设为“-1”（表示初始状态）而不是“0”；

另外我们在全局数据块DB中，建立一个包含元素类型为“BitsTable"的数组，并将其命名为”AddressTable"，或者为“BytesTable"则更容易理解，

至此，我们建立了一个可以形象为如下图所示的表格

四、算法描述

至此，我们再处理IO地址冲突检测就方便多了，当设定值Buffer中ByteSet和BitSet在合法范围内时，如ByteSet=0，BitSet=3时，我们只需要直接使用数组的索引首先找到AddressTable[0]，再找到其中的元素BitsTable[3]，即将对应的ByteSet、BitSet值代入并判断表达式”AddressTable[ByteSet].BitsTable[BitSet] = -1“是否成立（当值为”-1“时表示此地址I0.3(以输入I为例）未被使用，然后执行如下语句：

AddressTable[ByteSet].BitsTable[BitSet] = BitSet;    // set value of BitSet to BitsTable[BitSet]

ByteSet := -1;

BitSet := -1;

将BitSet值写入对应的数组元素，并将地址设定Buffer中的ByteSet和BitSet初始为”-1“，为下次地址输入作准备，如果再次输入ByteSet=0,BitSet=3时，

IF AddressTable[ByteSet].BitsTable[BitSet] = -1 THEN

    #AddressAlreadyExists := TRUE;    //output "AddressAlreadyExists" bit

算法简图如下：

功能块FB的接口如图，

块内做了两个辅助功能，ResetChannel和ResetAllChannel，用来将”-1“赋值给BitsTable[]中的单个元素，和所有元素，对接口进行修改后，还可以复位某个AddressTable[k],或者连续几个

AddressTable[k] -- AddressTable[k+n]，有兴趣可自行更改。