一、過濾器模式Pro簡(jiǎn)介

前已經(jīng)寫過過濾器模式，這里再寫一篇有以下幾個(gè)方面原因：

1、前一章的算法、數(shù)據(jù)和數(shù)據(jù)規(guī)則沒有分離，這里設(shè)計(jì)一個(gè)可用的工具包；

2、C#里面有統(tǒng)一查詢語言（LINQ）,里面包含數(shù)據(jù)查詢、集合查詢、以及排序，這篇文章也來開發(fā)一個(gè)LabVIEW的統(tǒng)一查詢工具包，實(shí)現(xiàn)以上功能。

功能包含以上內(nèi)容：

1、數(shù)據(jù)查詢；

2、集合運(yùn)算：交集、并集；

3、數(shù)據(jù)排序：升序和降序；

以上功能可以任意組合。

二、過濾器模式Pro-過濾

下圖為我們?cè)O(shè)計(jì)的UML關(guān)系類圖：

1、Abstract Filter過濾器框架：定義了過濾器過濾的基本規(guī)則

2、Abstract Data需要查詢的數(shù)據(jù)類型:只定義的一個(gè)tostring用于顯示數(shù)據(jù)

3、Abstract Rule定義了具體數(shù)據(jù)規(guī)則

下面開始編程

1、創(chuàng)建一個(gè)工程命名為L(zhǎng)LINQ,意思是LabVIEW的LINQ。

2、創(chuàng)建3個(gè)類分別命名為Abstract Filter、Abstract Data和Abstract Rule，在Abstract Filter私有數(shù)據(jù)中添加Abstract Rule和Abstract Data數(shù)組；并創(chuàng)建其數(shù)據(jù)成員訪問。

3、在Abstract Rule的私有數(shù)據(jù)數(shù)據(jù)中添加兩個(gè)Abstract Data分別命名為RData1、RData2，并創(chuàng)建其數(shù)據(jù)成員訪問。

5、在Abstract Rule中創(chuàng)建一個(gè)動(dòng)態(tài)VI命名為Filter rule。

6、在Abstract Filter中添加靜態(tài)類DoFilter，這個(gè)規(guī)則比較簡(jiǎn)單，只要是符合規(guī)則就留下，不符合規(guī)則就剔除。

下邊寫個(gè)實(shí)際DEMO來演示下過濾模式

6.1、創(chuàng)建VI命名為Filer DEMO

6.2、創(chuàng)建一個(gè)類命名為Double data繼承至Abstract Data，在私有數(shù)據(jù)添加一個(gè)double類型數(shù)據(jù)。

6.3、創(chuàng)建一個(gè)類命名為Greate The 0.5繼承至Abstract rule,重寫Filer rule。

6.4、在AbstratFIler中添加數(shù)據(jù)和過濾規(guī)則，進(jìn)行過濾，然后再取出數(shù)據(jù)

三、過濾器模式Pro-集合運(yùn)算

1、并集

在Abstract Filter中創(chuàng)建靜態(tài)方法Uniton，做法分三步

1.1、設(shè)置兩個(gè)過濾器作為輸入；

1.2、找出結(jié)合2中與集合1相同的部分并剔除；

1.3、合并剔除后的集合數(shù)據(jù)并保存到結(jié)果數(shù)據(jù)中。

2、交集

在Abstract Filter中創(chuàng)建靜態(tài)方法Intersection，做法分兩步

2.1、設(shè)置兩個(gè)過濾器作為輸入；

2.2、取出結(jié)合2中與集合1相同的部分,保存到輸出結(jié)果中。

2、集合范例

下面是一個(gè)兩個(gè)數(shù)組，一個(gè)是0--9的整數(shù)，一個(gè)是5--14的整數(shù)，求他們的交集和并集。

先創(chuàng)建一個(gè)整類繼承至Abstract Rule，私有數(shù)據(jù)類型為整型，重寫數(shù)據(jù)規(guī)則Filer Rule：

3、下面是具體的使用代碼：

4、前面板結(jié)果

四、過濾器模式Pro-冒泡排序

數(shù)組排序是一個(gè)經(jīng)常使用的功能，LabVIEW自帶的數(shù)組排序功能只能對(duì)數(shù)值類型數(shù)據(jù)進(jìn)行排序，那么簇，指定類中特定數(shù)據(jù)排序呢，每次都需要自己寫非常麻煩，影響編程效率。下面寫個(gè)通用的冒泡排序算法：

從最底部?jī)蓚€(gè)元素開始比價(jià)，如果上一個(gè)元素大于下一個(gè)元素就交換位置，然后向上挪一個(gè)位置，重復(fù)以上操作直到最頂端。最大值就像泡泡浮出水面一樣，再從最底端到頂端第二個(gè)元素重復(fù)上面動(dòng)作，依次循環(huán)

這個(gè)是冒泡迭代的位置。

具體編碼如下程序框圖：

建一個(gè)double比較的數(shù)據(jù)規(guī)則

創(chuàng)建個(gè)DEMO生成一組隨機(jī)數(shù)看看運(yùn)行結(jié)果：

運(yùn)行下結(jié)果達(dá)到預(yù)期，我們把數(shù)據(jù)數(shù)量改成1000，2000看看運(yùn)行時(shí)間

上面可以看到1000次運(yùn)行時(shí)間為3.39秒，2000次運(yùn)行時(shí)間為13.7秒，這個(gè)時(shí)間感覺太長(zhǎng)了，能優(yōu)化排序算法將時(shí)間縮短不？

看下一章的分治排序法。

五、過濾器模式Pro-分治排序

冒泡排序算法的時(shí)間復(fù)雜度為O(n^2)空間復(fù)雜度為O(1)

我們使用分治排序時(shí)間復(fù)雜度為O(nlog(n))空間復(fù)雜度為O(log(n))

簡(jiǎn)單介紹下原理：

固定第一個(gè)數(shù)，從最后和最前搜索，當(dāng)后面大于第一個(gè)數(shù)，前面小于第一個(gè)數(shù)時(shí)就交換搜到的數(shù)據(jù)。當(dāng)兩個(gè)搜索指針相遇時(shí)，就交換第固定數(shù)和相遇數(shù)。交換后結(jié)果為：相遇位置數(shù)左邊數(shù)小，比右邊的數(shù)大。

將其按照相遇位置前后分成兩組：分別重復(fù)上面內(nèi)容直到分治完成。

下邊開始編寫分治算法代碼，圖中有需要調(diào)用相同的算法需要用到遞歸，我們把主體算法和遞歸部分分離,創(chuàng)建一個(gè)VI命名為Devide Core，VI屬性設(shè)置如下：

分治核心代碼

測(cè)試后1000次時(shí)間為0.58秒，2000次時(shí)間為2.20秒，比冒泡排序有了很大的改善，那么有沒有更快的優(yōu)化方案呢？看下邊異步分治排序法。

五、過濾器模式Pro-異步分治排序

如上圖所示，我們第一次分組后，組一執(zhí)行完后再執(zhí)行組二，組一和組二的數(shù)據(jù)互不干擾，那么我們將異步執(zhí)行組一和組二，以空間換時(shí)間。

具體代碼改造如下：

1、將數(shù)據(jù)轉(zhuǎn)換為引用類型；

2、將組一和組二異步執(zhí)行。

具體代碼如下：

異步分治排序算法：

異步分治核心：

測(cè)試代碼：

有上面例子可以看出，使用異步分治排序算法，排序速度有了指數(shù)級(jí)別提升。

審核編輯：郭婷