基于iPhone應(yīng)用的圖片請求匹配方案

夏小玲，朱文術(shù)

（東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，上海 201620）

基于iPhone應(yīng)用的圖片請求匹配方案

夏小玲，朱文術(shù)

（東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，上海 201620）

提出一種異步請求匹配方案——當(dāng)前匹配算法，介紹了當(dāng)前匹配算法的算法思想以及算法實現(xiàn).通過對異步請求特點的分析，得出影響當(dāng)前匹配算法的因素，進而提出亂序因子的概念.亂序因子主要受服務(wù)器處理性能影響，可以通過提高服務(wù)器處理性能來降低亂序因子，進而提高算法效率.通過將當(dāng)前匹配算法與順序查詢及其相關(guān)改進算法進行比較，得出當(dāng)前匹配算法較其他算法更適用于iPhone中異步請求數(shù)據(jù)的匹配.當(dāng)前匹配算法在保證質(zhì)量的基礎(chǔ)上提高了順序查詢算法的效率.最后通過試驗對其進行了驗證，說明了該方案的有效性.

iPhone應(yīng)用；圖片匹配；MVC模式

iPhone是蘋果公司于2007年推出的移動掌上設(shè)備.iPhone的出現(xiàn)打破了傳統(tǒng)手機的模式，受到人們的廣泛喜愛.關(guān)于iPhone的應(yīng)用開發(fā)也進展神速，App Store的應(yīng)用銷售進行得如火如荼.在iPhone的應(yīng)用中會用到大量的圖片資源，且大部分圖片是以服務(wù)請求的方式獲取的，獲得數(shù)據(jù)后在客戶端進行展示.當(dāng)同時有大量的圖片需要請求時，為了加快請求速度，常會用到多線程，即以異步的方式進行請求.由于請求數(shù)據(jù)的大小不同，處理器處理需要的時間不同，會出現(xiàn)返回數(shù)據(jù)順序與請求發(fā)出順序不一致的現(xiàn)象.在數(shù)據(jù)返回后需要根據(jù)其一些特性與請求圖片的對象進行匹配，確定請求圖片的對象.

目前iPhone應(yīng)用數(shù)據(jù)獲取大部分使用異步請求方式.為了使得獲取的數(shù)據(jù)與請求數(shù)據(jù)對象進行匹配，常使用的方法有兩種：一是順序查詢方法，這種方法使用簡單，但效率較差；二是將數(shù)據(jù)請求與數(shù)據(jù)結(jié)構(gòu)體進行綁定，數(shù)據(jù)結(jié)構(gòu)體用于存放系統(tǒng)所需數(shù)據(jù)，將數(shù)據(jù)請求與其綁定，破壞了其結(jié)構(gòu).這兩種解決方案都不可取，為解決該問題，本文提出了另外兩種解決方案.一種是通過視圖請求圖片的方法，使得返回的圖片能夠在相應(yīng)的視圖上正確顯示；另外一種是當(dāng)前匹配算法，即只計算欲匹配數(shù)據(jù)當(dāng)前所在位置之前的數(shù)據(jù)，而不管之后的數(shù)據(jù).這兩種方法都能解決圖片匹配問題，但各有優(yōu)勢.本文分別討論這兩種方案并詳細介紹當(dāng)前匹配算法.

1 iPhone應(yīng)用遵循的架構(gòu)

1.1 iOS

iOS原稱為iPhone OS，是為了滿足iPhone及iTouch的移動環(huán)境而設(shè)計的，它通過系統(tǒng)接口與硬件接觸，相當(dāng)于軟硬件之間的一個中間層.iOS的存在使得底層的變更最小限度地影響上層，不論如何變更底層的硬件，只要保證其接口不變，則上層應(yīng)用不受影響.iOS包含在iPhone和iTouch上運行本地應(yīng)用程序所需的操作系統(tǒng)和技術(shù)基礎(chǔ).iPhone跟Mac OS X 有共同的基礎(chǔ)構(gòu)架和底層技術(shù)［1］.iOS系統(tǒng)架構(gòu)分為4個層次，如圖1所示.

圖1 iOS架構(gòu)層次圖Fig.1 iOS structure levels

根據(jù)4個層次的不同，代碼實現(xiàn)的選擇也不同.其中核心操作系統(tǒng)層和核心服務(wù)層包含了iPhone的基礎(chǔ)接口，用于對文件、底層數(shù)據(jù)類型、網(wǎng)絡(luò)接口等進行訪問.核心操作系統(tǒng)層和核心服務(wù)層位于架構(gòu)的底層，實現(xiàn)也大多基于C語言.觸摸層及媒體層更接近表層，接口也是由C語言及Objective C語言實現(xiàn).例如，在媒體層包含支持二維和三維繪圖以及音頻和視頻的基礎(chǔ)技術(shù)，它還包括了核心動畫技術(shù)等.而觸摸層的接口大多是基于Objective C語言實現(xiàn)的，它提供了應(yīng)用程序的基礎(chǔ)架構(gòu)［1］.該層的UIKit框架提供了開發(fā)所需的各種窗口、視圖以及對象控制器等，它是任何一個新項目的起點.

iOS為應(yīng)用提供了開發(fā)及運行環(huán)境，是iPhone、iTouch以及iPad得以運行的基礎(chǔ)，其重要性不言而喻，因此，了解iOS的架構(gòu)對于應(yīng)用開發(fā)者而言是非常必要的，這是開發(fā)iPhone應(yīng)用的一個重要基礎(chǔ).

1.2 iPhone應(yīng)用架構(gòu)的設(shè)計模式

1.2.1 Cocoa框架的設(shè)計模式

Cocoa框架是蘋果的面向?qū)ο箝_發(fā)框架，它是Mac OS X操作系統(tǒng)的應(yīng)用程序環(huán)境之一［2］，用來支持Mac OS X及iOS的應(yīng)用程序.在傳統(tǒng)的開發(fā)中，經(jīng)常會有“膠水代碼”的困擾，為了保持用戶界面數(shù)據(jù)和狀態(tài)同步，需要進行大量編碼，使代碼變得冗長、易出錯、難維護.為了解決這個問題，Cocoa框架采用了 “模型 （Model）-視圖（View）-控制器（Controller）”即 MVC的設(shè)計模式［3］.MVC模式將業(yè)務(wù)邏輯、用戶界面顯示與數(shù)據(jù)處理相互分離，各司其職.Model負責(zé)系統(tǒng)的業(yè)務(wù)邏輯，接受視圖的數(shù)據(jù)請求并返回處理結(jié)果.View代表用戶交互界面，在Cocoa中，View的代表是UIView.Controller主要用于控制Model與View，以完成需求，在Cocoa中，UIViewController為其代表.

通過MVC模式，Cocoa消除了大部分的“膠水代碼”，降低了模型與視圖間的耦合［4－5］，使它們可以獨立變化，再通過Controller進行組合，使得應(yīng)用具有充分的靈活性.Cocoa中除了整體MVC模型外，其內(nèi)部的一些子系統(tǒng)也會重復(fù)使用MVC設(shè)計模式，可以看出Cocoa中貫穿了這種模式.

1.2.2 iOS應(yīng)用的設(shè)計模式

iOS應(yīng)用為了能夠更好地使用Cocoa框架，也應(yīng)盡量遵守MVC模式.一般iPhone應(yīng)用程序可能會含有多個功能模塊，若將多個模塊使用一個Controller進行控制，管理起來會比較困難，還會造成單個文件過于龐大、邏輯過于復(fù)雜的情況.根據(jù)實際情況可以將應(yīng)用分解成多個功能模塊，每個功能模塊使用一個MVC模式實現(xiàn).這樣就減少了Controller的控制復(fù)雜度，也減少了文件的大小，維護會相對簡單.在實際應(yīng)用中，為了便于修改和維護，使用多個MVC模式的方法得到了廣泛的應(yīng)用.

2 匹配算法

2.1 視圖請求方案

iPhone應(yīng)用中圖片獲取問題成為其不可避免的問題.在實際應(yīng)用中一般數(shù)據(jù)的獲取由控制器驅(qū)動，業(yè)務(wù)邏輯層收到請求后會向服務(wù)器端發(fā)送請求，服務(wù)器端返回數(shù)據(jù)到業(yè)務(wù)邏輯層.業(yè)務(wù)邏輯層再通過委托函數(shù)將獲取的數(shù)據(jù)傳給請求驅(qū)動的控制器，再由控制器分發(fā)給相應(yīng)的視圖進行顯示，這是MVC模式中數(shù)據(jù)流動的一個基本過程.圖片的獲取同一般的數(shù)據(jù)獲取一樣，需要經(jīng)過這樣幾個階段.如果一個控制器只請求一個圖片，則獲取的數(shù)據(jù)直接分發(fā)給視圖進行顯示即可.但當(dāng)控制器需要請求多張圖片時，則需要考慮返回的數(shù)據(jù)如何分發(fā)給視圖，使其能夠在相應(yīng)的視圖上正確顯示.這就需要控制器將取得的數(shù)據(jù)與原本請求數(shù)據(jù)的對象進行匹配，將數(shù)據(jù)按照正確的順序傳送給相應(yīng)的視圖使其正確顯示.

如果要避免多張圖片匹配的問題，最簡單的方法是每次只發(fā)送一個請求.然而，控制器負責(zé)整個應(yīng)用中模型與視圖的控制作用，因此，很難做到在控制器中只發(fā)送一個請求.而通過視圖直接請求圖片則可以實現(xiàn)每次只發(fā)送一個請求的操作.每個視圖請求一個圖片，實現(xiàn)獲取數(shù)據(jù)的委托函數(shù)，將獲取的數(shù)據(jù)直接在該視圖中顯示即可.視圖請求方案的實質(zhì)是避免了返回數(shù)據(jù)與請求模塊的匹配.這種解決方案的優(yōu)勢在于圖片數(shù)據(jù)與視圖是一一對應(yīng)的，即，在請求發(fā)出時已完成匹配，其能夠最大限度地降低時間復(fù)雜度和空間復(fù)雜度.但是，通過視圖進行數(shù)據(jù)請求對MVC設(shè)計模式具有一定的破壞性，對于規(guī)模較小且結(jié)構(gòu)簡單的應(yīng)用使用該種請求方案能夠降低應(yīng)用的復(fù)雜度以及數(shù)據(jù)處理復(fù)雜度.對于規(guī)模較大或結(jié)構(gòu)較復(fù)雜的應(yīng)用，該種解決方案局限性較大.

2.2 當(dāng)前匹配算法

在遵循MVC設(shè)計模式的基礎(chǔ)上，本節(jié)提出另一種有效的解決方案——當(dāng)前匹配算法，它適用于各種規(guī)模的應(yīng)用，且能夠嚴格遵守MVC設(shè)計模式.

在數(shù)據(jù)請求的過程中，發(fā)送到服務(wù)器端的信息始終不會丟失，客戶端可以通過服務(wù)器端返回的數(shù)據(jù)所附的信息與發(fā)送的信息進行比較，將返回數(shù)據(jù)與對應(yīng)的請求數(shù)據(jù)的對象進行匹配.為了簡單起見，假設(shè)所有請求的地址是唯一的，將其作為匹配的標準.根據(jù)標識符進行搜索的圖片匹配算法［6－7］，稱之為當(dāng)前匹配算法.

（1）假設(shè)數(shù)組a和b分別表示長度為n的兩個數(shù)組，a［k］和b［k］分別表示數(shù)組中第k個元素，0≤n，0≤k＜n.

（2）比較a［k］與b［k］，若不相等，則將a［k］與b［k］標識為不匹配，若相等且k＜n－1，則比較a［k＋1］與b［k＋1］，若相等且k＝n－1，則完成匹配.

（3）將b中標志為不匹配的元素b［i］（0≤i＜k）與a中當(dāng)前元素a［k］進行比較，若存在匹配則去除相應(yīng)元素的不匹配標識.比較完畢后將a中不匹配的元素a［i］（0≤i＜k）與b中當(dāng)前元素b［k］進行比較，若存在匹配則去除相應(yīng)元素的不匹配標識.

（4）重復(fù)步驟（2）和（3）直到完成所有匹配.

其中，數(shù)組a表示原始請求序列，數(shù)組b表示返回數(shù)據(jù)附屬信息的序列，即分別為請求地址的序列以及返回數(shù)據(jù)所對應(yīng)的地址，將兩者進行匹配以確定返回數(shù)據(jù)所在的位置.具體算法示意圖如圖2所示.

圖2 算法示意圖Fig.2 Algorithm diagram

當(dāng)前匹配算法的核心思想是比較到達數(shù)據(jù)所在位置之前的序列，之后的序列不做考慮，而且匹配的元素對不參與比較，這樣在位置k處比較的次數(shù)都小于k，大大減少了比較的次數(shù).每次請求比較的數(shù)據(jù)與原序列中當(dāng)前位置的元素進行比較，若不匹配則兩個元素都被標記為不匹配，然后將到來數(shù)據(jù)所在數(shù)組中標記的元素與原數(shù)組中當(dāng)前元素進行比較，再將原數(shù)組中標記的元素與到來的當(dāng)前數(shù)據(jù)進行比較，匹配的數(shù)據(jù)去除標記，則下次參與比較的數(shù)據(jù)減少.這種將一組數(shù)據(jù)中的標記元素與另外一組數(shù)據(jù)中的當(dāng)前元素進行比較的做法，能夠防止出現(xiàn)遺漏或者死循環(huán)現(xiàn)象，保證匹配高質(zhì)量、高效率地進行.

由上述算法可以看出，該算法與返回數(shù)據(jù)的順序相關(guān)性極大，本文給出亂序因子的概念.亂序因子用于表示返回序列與請求序列中順序不一致的程度，用d表示，0≤d≤1，d＝0表示沒有亂序，即返回序列與請求序列完全一致，d＝1表示完全亂序，即返回序列與請求序列在相應(yīng)位置上沒有任何匹配.若d＝0，則該算法的時間復(fù)雜度為O（1），而d＝1時，該算法的時間復(fù)雜度為O（n2），由此可以看出，亂序因子對該算法的影響極大.

3 算法實現(xiàn)

當(dāng)前匹配算法是基于iPhone應(yīng)用提出的，iPhone開發(fā)使用的是Objective C語言.為了遵循MVC模式，將請求圖片的業(yè)務(wù)邏輯封裝為一個模型，使得所有的圖片請求都通過該類實現(xiàn)，將接收參數(shù)的接口以及傳輸數(shù)據(jù)的接口留給用戶，其他的則對用戶透明.在Objective C語言中，數(shù)據(jù)傳遞常通過委托函數(shù)來實現(xiàn)，因此，業(yè)務(wù)邏輯層獲取數(shù)據(jù)后將地址數(shù)據(jù)與獲取的數(shù)據(jù)打包后，通過委托函數(shù)將數(shù)據(jù)傳送給控制器，控制器只要實現(xiàn)模型的委托函數(shù)就能獲取其傳送的數(shù)據(jù).具體的數(shù)據(jù)匹配是在控制器中實現(xiàn)的，將圖片進行匹配后，由控制器將相應(yīng)格式的數(shù)據(jù)傳送給視圖，由視圖進行展示.該算法的偽代碼段如下：

1.將b［k］對應(yīng)的數(shù)據(jù)與相應(yīng)位置的對象綁定｝

在實際應(yīng)用中，數(shù)組b中的地址數(shù)據(jù)是單個傳送過來的，并不是一開始就全部存在該數(shù)組中，實際應(yīng)用中的做法是把不匹配的地址放入數(shù)組b中，若匹配則直接將與該地址對應(yīng)的圖片數(shù)據(jù)保存在相應(yīng)的位置，以供使用.實際應(yīng)用中系統(tǒng)的架構(gòu)如圖3所示.

圖3 系統(tǒng)架構(gòu)圖Fig.3 System architecture

4 試驗結(jié)果及分析

圖4 當(dāng)前匹配算法與順序查詢算法對比Fig.4 Current matching versus normal search

由圖4還可以看出，亂序因子對當(dāng)前匹配算法的影響很大，亂序因子主要受服務(wù)器處理性能的影響.服務(wù)器處理性能高則亂序因子低，服務(wù)器處理性能與亂序因子呈反比關(guān)系.亂序因子越低則當(dāng)前匹配算法效率越高，因此，服務(wù)器處理性能與當(dāng)前匹配算法的效率呈正比關(guān)系.服務(wù)器處理性能與亂序因子的關(guān)系如圖5所示.

已經(jīng)成熟的查詢算法有折半查詢、平衡二叉樹查詢以及哈希表查詢等.這些查詢的時間復(fù)雜度如表1所示.

圖5 亂序因子與服務(wù)器處理性能的關(guān)系Fig.5 Relationship between confused factor and process performance of server

表1 查詢算法比較Table 1 Comparison of search algorithm

由表1可以看出，折半查詢、平衡二叉樹查詢以及哈希表查詢的時間復(fù)雜度都比當(dāng)前匹配算法的時間復(fù)雜度要低.但是這些算法都具有一定的適用環(huán)境，折半查詢適用于有序表，與本文的當(dāng)前匹配算法適用環(huán)境不同.平衡二叉樹查詢算法需要構(gòu)造平衡二叉樹，有額外的時間和空間開銷.而哈希表查詢則是以空間換取時間的典型代表，它需要空間輔助，而在iPhone中，空間資源有限，因而哈希表的方法并不適用.當(dāng)前匹配算法的時間復(fù)雜度雖然不是最優(yōu)，但是通過亂序因子能夠降低一定的復(fù)雜度，而空間消耗也較低，比較適合于iPhone應(yīng)用的使用.

文獻 ［16］中介紹了多種查詢算法，除了傳統(tǒng)的靜態(tài)查詢與動態(tài)查詢算法之外，學(xué)者們還提出了許多其他類型的查詢，典型的字符串查詢則有BM（Boyer Moore）算法和 KMP（Knuth，Pratt，Morris）算法等，這些算法大部分都有一些適用條件或背景.本文所提出的當(dāng)前匹配算法適用于iOS應(yīng)用中特定框架下圖片數(shù)據(jù)亂序匹配的問題，當(dāng)然也可以推廣到非圖片的其他數(shù)據(jù)中加以應(yīng)用.

5 結(jié) 語

目前關(guān)于數(shù)據(jù)與請求數(shù)據(jù)對象的匹配存在很多查詢算法，其中大部分算法是基于特定數(shù)據(jù)模式的，而本文提出的當(dāng)前匹配算法也存在其特定的要求，即需要匹配的數(shù)據(jù)集與原數(shù)據(jù)集在一定程度上具有相似順序.本文提出亂序因子的概念來衡量兩個數(shù)據(jù)集之間順序的相似程度，并通過該參數(shù)觀察當(dāng)前匹配算法所需要消耗的大致時間，研究同時也表明，可以通過提高配置來控制該參數(shù)使得查詢時間大大降低.當(dāng)前匹配算法在存在亂序因子的數(shù)據(jù)集上能夠進行更有效的查詢，節(jié)省查詢時間，提高查詢效率.最后通過試驗驗證了該算法的優(yōu)勢.

參 考 文 獻

［1］和凌志，郭世平.手機軟件平臺架構(gòu)解析［M］.北京：電子工業(yè)出版社，2009：154－163.

［2］Apple Inc.ios參考庫［EB／OL］.（2003－09－09）［2011－10－19］.http：／／www. apple. com. cn／developer／mac／library／documentation／ Cocoa／Conceptual／CocoaOverview／Articles／CocoaFrameworks.html＃／／apple＿ref／doc／uid／20001932.

［3］Apple Inc.ios參考庫［EB／OL］.（2006－12－20）［2011－10－19］.http：／／www.apple.com.cn／developer／mac／library／documentation／Cocoa／Conceptual／CocoaFundamentals／CocoaDesignPatterns／chapter＿5＿section＿4.html＃／／apple＿ref／doc／uid／TP40002974－CH6－SW1.

［4］DAWSON A，KOMAROV A，CHAPMAN C，et al.Mobile design for iPhone and iPad［M］.Germany：Smashing Media GmbH，2010：18－54.

［5］沙洛維，特羅特.設(shè)計模式解析［M］.2版.徐言聲，譯.北京：人民郵電出版社，2006：67－72.

［6］CORMEN T H，LEISERSON C E，RIVEST R L，et al.Introduction to algorithms［M］.3rd ed.America：Mit Pr，2009：147－228，769－897.

［7］HORMKOVIC J.Algorithm adventures：From knowledge to magic［M］.Germany：Springer，2009：37－72，161－194.

［8］MARK D，LAMARCHE J.Beginning iPhone 3development：Exploring the iPhone SDK［M］.America：Apress L P，2009：193－319.

［9］CONWAY J，HILLEGASS A .IPhone programming：The big nerd ranch guide［M］.America：Addison－Wesley Professional，2010：26－70.

［10］ALLEN C，APPELCLINE S.IPhone in action：Introduction to web and SDK development ［M ］. America： Manning Publications，2008：80－101，344－365.

［11］SADUN E. The iPhone developer's cookbook： Building applications with the iPhone 3.0SDK［M］.2nd ed.America：Addison Wesley，2009：257－300.

［12］DUDNEY B.Core animation for Mac OS X and the iPhone：Creating compelling dynamic user interfaces［M］.America：The Pragmatic Bookshelf，2008：58－115.

［13］DANNEN C.IPhone design award－winning projects［M］.America：Apress L P，2009：1－23.

［14］FLING B.Mobile design and development：Practical concepts and techniques for creating mobile sites and web apps［M］.America：Reilly Media，2009：29－41，109－140.

［15］BIRD R.Pearls of functional algorithm design［M］.America：Cambridge University Press，2010：117－135.

［16］CHUNG C.Pro objective－C design patterns for iOS［M］.America：Apress，2011：45－182.

The Solution on the Matching of Images Request Based on iPhone Applications

XIAXiao－ling，ZHUWen－shu
（School of Computer Science and Technology，Donghua University，Shanghai 201620，China）

A solution for asynchronous request—current matching algorithm was proposed.The concept and the realization of the algorithm were described.Through the analysis of the asynchronous request，the confused factor was brought.Confused factor was affected by the process performance of the server mostly，if the process performance of the server was increased，the confused factor would be decreased，and then，the effectiveness of the current matching algorithm would be enhanced.The compare among current matching algorithm and normal search and improved algorithm showed that the current matching algorithm was more suitable for the asynchronous request on iPhone.Current matching algorithm increased the search effectiveness with high quality.Finally the test result was given to show the effectiveness of the algorithm.

iPhone application；image matching；MVC mode

TP 302.2

A

1671－0444（2013）01－0088－06

2010－10－19

夏小玲（1966—），女，湖北武漢人，副教授，博士，研究方向為數(shù)據(jù)可視化與數(shù)據(jù)處理.E－mail：sherlysha＠dhu.edu.cn