摘要：

数据结构 算法 效率

一、问题背景

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

【万泉河】我现在告诉你们不用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]，有兴趣可自行更改。

FB块完整代码：

FUNCTION_BLOCK "UniqueAddressDetection"

{ S7_Optimized_Access := 'FALSE' }

VERSION : 0.1

   VAR_INPUT 

      ResetChannel : Bool;   // reset single I/O address

      ResetAllChannels : Bool;   // reset all I/O addresses

   END_VAR

   VAR_IN_OUT 

      ByteSet : Int := -1;

      BitSet : Int := -1;

      AddressTable : Array[0..127] of "BitsTable";

      ByteSetIllegal : Bool;

      BitSetIllegal : Bool;

      AddressAlreadyExists : Bool;

   END_VAR

   VAR_TEMP 

      BeWritten : Bool;

      sum_Byte : Int;

      sum_Bit : Int;

      LastByteSet : Int;

      LastBitSet : Int;

   END_VAR

BEGIN

//*****************************************************

//    envirment : TIA Portal v14 SP1

//    CPU :         CPU 314C-2 PN/DP

//    Date :         2018/11/26

//    Author :      唐诗宋瓷

//*****************************************************

//check ByteSet

IF #ByteSet < 0 OR #ByteSet > 127 THEN

    #ByteSetIllegal := TRUE;

ELSE

    #ByteSetIllegal := FALSE;

END_IF;

//check BitSet

IF #BitSet < 0 OR #BitSet > 7 THEN

    #BitSetIllegal := TRUE;

ELSE

    #BitSetIllegal := FALSE;

END_IF;

//check unique address

IF (#ResetChannel = FALSE 

    AND #ResetAllChannels = FALSE 

    AND #ByteSetIllegal = FALSE 

    AND #BitSetIllegal = FALSE) THEN

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

        #AddressTable[#ByteSet].BitsTable[#BitSet] := #BitSet;

        #BeWritten := TRUE;

        //#LastByteSet := #ByteSet;

        //#LastBitSet := #BitSet;

        #ByteSet := -1;

        #BitSet := -1;

        #AddressAlreadyExists := FALSE;

    ELSE

        #AddressAlreadyExists := TRUE;

        //#ByteSet := -1;

        //#BitSet := -1;

    END_IF;

END_IF;

//reset channel

IF (#ResetChannel = TRUE 

    AND #ResetAllChannels = FALSE 

    AND #ByteSetIllegal = FALSE 

    AND #BitSetIllegal = FALSE) THEN

    #AddressTable[#ByteSet].BitsTable[#BitSet] := - 1;

    #ByteSet := -1;

    #BitSet := -1;

END_IF;

//reset all channels

IF #ResetAllChannels = TRUE THEN

    FOR #sum_Byte := 0 TO 127 DO

        // Statement section FOR

        FOR #sum_Bit := 0 TO 7 DO

            // Statement section FOR

            #AddressTable[#sum_Byte].BitsTable[#sum_Bit] := - 1;

        END_FOR;

    END_FOR;

END_IF;

END_FUNCTION_BLOCK

五、结语

在对数据进行组织的过程中，需要再深入考虑一下不同的数据结构对算法效率的影响。

《编程珠玑》（第2版）的附录4中第一条就列举了这样重要的一条规则：

数据结构与算法也算是从事自动化工作的人需要了解和掌握的基础知识，帖中的这个FB可能在实际工程应用中没有多少用处，只希望这个部分类似于”查表法“的帖子对大家在数据结构和算法方面有所启示吧。

附件：

UniqueAddressDetection.zip

UniqueAddressDetection_20181127_0035.zip

-------------------------------------------------------------------------------------------------------------------------------------------

补：

前文采用的方法等效数组的数组，其实使用一维数组也完全可以实现。毕竟，二维数组的物理存储空间模型本质上还是连续的，我们要做的也还是确认“索引”是多少，这里我们使用一个基数为8的位权的计算公式得到索引的值。

例如，Buffer输入的是3.4，即ByteSet=3,BitSet=4,据计算公式得到Index=3*8+4=28，即可使用Array[28]的值进行判断地址是否已经被使用了。

具体见下图

为保证看帖时思路连续，直接在原帖追加此内容，不再新起楼了。

----------------------------------------------------------------------------------------------------------------------------------------

2018年12月13日更新：

不同电机个数时的效率对比图

50个电机：

100个电机：

200个电机：

500个电机：

X轴为电机个数，Y轴为地址设定值（地址都转换为一个整数值时）比较次数。

直接查表时，第n个电机的IO点的次数为5，常数级别，n个电机总比较次数为5n；

当遍历数组时，第n个电机的IO的比较次数为

3(n-1)[第1个输入点比较次数]

+(3(n-1)+1)[第2个输入点比较次数]

+(3(n-1)+1+1)[第3个输入点比较次数]

+2(n-1)[第1个输出点比较次数]

+(2(n-1)+1)[第2个输出点比较次数]

=13n-9

n个电机总比较次数为（4+(13n-9))n/2=n(13n-5)/2，

即当总电机数n为 ｛1，2，3，...n-2，n-1，n｝时，比较

总次数为等差数列｛4，17，30，...13n-35，13n-22，13n-9｝前n项的和。

数学学得不好，有异议者再议。