基于iPhone應用的圖片請求匹配方案

夏小玲，朱文術

（東華大學 計算機科學與技術學院，上海 201620）

基于iPhone應用的圖片請求匹配方案

夏小玲，朱文術

（東華大學 計算機科學與技術學院，上海 201620）

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

iPhone應用；圖片匹配；MVC模式

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

目前iPhone應用數(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).這兩種解決方案都不可取，為解決該問題，本文提出了另外兩種解決方案.一種是通過視圖請求圖片的方法，使得返回的圖片能夠在相應的視圖上正確顯示；另外一種是當前匹配算法，即只計算欲匹配數(shù)據(jù)當前所在位置之前的數(shù)據(jù)，而不管之后的數(shù)據(jù).這兩種方法都能解決圖片匹配問題，但各有優(yōu)勢.本文分別討論這兩種方案并詳細介紹當前匹配算法.

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

1.1 iOS

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

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

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

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

1.2 iPhone應用架構(gòu)的設計模式

1.2.1 Cocoa框架的設計模式

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

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

1.2.2 iOS應用的設計模式

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

2 匹配算法

2.1 視圖請求方案

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

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

2.2 當前匹配算法

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

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

（1）假設數(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中當前元素a［k］進行比較，若存在匹配則去除相應元素的不匹配標識.比較完畢后將a中不匹配的元素a［i］（0≤i＜k）與b中當前元素b［k］進行比較，若存在匹配則去除相應元素的不匹配標識.

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

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

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

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

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

3 算法實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

目前關于數(shù)據(jù)與請求數(shù)據(jù)對象的匹配存在很多查詢算法，其中大部分算法是基于特定數(shù)據(jù)模式的，而本文提出的當前匹配算法也存在其特定的要求，即需要匹配的數(shù)據(jù)集與原數(shù)據(jù)集在一定程度上具有相似順序.本文提出亂序因子的概念來衡量兩個數(shù)據(jù)集之間順序的相似程度，并通過該參數(shù)觀察當前匹配算法所需要消耗的大致時間，研究同時也表明，可以通過提高配置來控制該參數(shù)使得查詢時間大大降低.當前匹配算法在存在亂序因子的數(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］沙洛維，特羅特.設計模式解析［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