摘要：

数据结构 算法 效率

一、问题背景

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

【万泉河】我现在告诉你们不用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项的和。

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

佩服，厉害！

佩服，厉害！

慢慢钻研

学的越多，见的越多

学习了，谢谢

总结排版 牛逼~

谢谢分享，空间换取时间，很有启发性

这个写的不错，仔细看看。

@Zane 版，前几天在某公众号看到您的论文，公众号嘛，在手机这样的移动端看不太清楚，只简单看了个大概。

以您的成就，是处于山顶的人，而我是山脚下的无名之辈，所以面对您提出的问题，很有压力的。

作为久经沙场的一员老将，无论是您的帖子还是文章向来是以全面、系统、章法结构严谨来服众的，既然是已经出版发行的文章，想必是经过严格审查，论文评审委员会的成员们也都是业界翘楚，所以，对您的文章也就不作任何评论了，只说一点我对里面数据方面的想法。

如果沿用您采用的IO地址的数据结构（UDT)的话，每个IO点的地址设定需要从UDT中获取，我个人认为这就限制了使用简单结构如数组形式对数据进行操作的灵活性和查找的快捷性，这在查找操作中是致命的，尤其是还有嵌套的形式，虽然在数据的封装性上我们获得了一定效益，但是封装在某些情境下也带来了相当的劣势。

如果是我的话，我倒宁愿把所有IO点所具有的每个相同的属性（暂时用来借指UDT中的内容）都拿出来，放到一个简单的数组（表）当中，保持数据结构内数据的保持纯粹单一性，而不是驳杂，再分别使用查表的方法进行处理。要调取每个IO点不同的属性值，只需要使用一个索引index，在多个表中直接获取就可以了，也就是下图中从左到右的变化。

数据的组织形式，决定了我们对数据进行操作的算法的快捷与否，而算法也决定了代码和程序的长短。

在不改变原有UDT的前提下，只能额外再加一些做上述表分割工作的FC或者FB来实现查找操作。

周末闲翻故纸堆，看到有这么一段话：

Let the data structure the program. The theme of this column is that data can structure a program by replacing complicated code with an appropriate data structure. Although the particulars change, the theme remains: before writing code, good programmers thoroughly understand the input, the output and the intermediate data structures around which their programs are built.

英语学得不好，翻译做不到“信、雅、达”的程度，就不翻了。

我还在想，在HMI上不搞什么数字输入了，就直接弄字符串也未尝不可，直接输入"IX.Y"，再对字符串进行分解就是了；甚至还有，在HMI上做能根据变量名查找对应地址，以及反操作的功能，即通过输入地址查找地址对应的变量名。当然，这又是个问题了。

至于如何使用您文中的程序架构，还有数据封装的问题（是直接封装还是做完查找操作后再封装），还得细想想，能否再扁平化一些。

暂时就想到这些，见笑了。