基于iPhone应用的图片请求匹配方案

夏小玲，朱文术

（东华大学 计算机科学与技术学院，上海 201620）

基于iPhone应用的图片请求匹配方案

夏小玲，朱文术

（东华大学 计算机科学与技术学院，上海 201620）

提出一种异步请求匹配方案——当前匹配算法，介绍了当前匹配算法的算法思想以及算法实现.通过对异步请求特点的分析，得出影响当前匹配算法的因素，进而提出乱序因子的概念.乱序因子主要受服务器处理性能影响，可以通过提高服务器处理性能来降低乱序因子，进而提高算法效率.通过将当前匹配算法与顺序查询及其相关改进算法进行比较，得出当前匹配算法较其他算法更适用于iPhone中异步请求数据的匹配.当前匹配算法在保证质量的基础上提高了顺序查询算法的效率.最后通过试验对其进行了验证，说明了该方案的有效性.

iPhone应用；图片匹配；MVC模式

iPhone是苹果公司于2007年推出的移动掌上设备.iPhone的出现打破了传统手机的模式，受到人们的广泛喜爱.关于iPhone的应用开发也进展神速，App Store的应用销售进行得如火如荼.在iPhone的应用中会用到大量的图片资源，且大部分图片是以服务请求的方式获取的，获得数据后在客户端进行展示.当同时有大量的图片需要请求时，为了加快请求速度，常会用到多线程，即以异步的方式进行请求.由于请求数据的大小不同，处理器处理需要的时间不同，会出现返回数据顺序与请求发出顺序不一致的现象.在数据返回后需要根据其一些特性与请求图片的对象进行匹配，确定请求图片的对象.

目前iPhone应用数据获取大部分使用异步请求方式.为了使得获取的数据与请求数据对象进行匹配，常使用的方法有两种：一是顺序查询方法，这种方法使用简单，但效率较差；二是将数据请求与数据结构体进行绑定，数据结构体用于存放系统所需数据，将数据请求与其绑定，破坏了其结构.这两种解决方案都不可取，为解决该问题，本文提出了另外两种解决方案.一种是通过视图请求图片的方法，使得返回的图片能够在相应的视图上正确显示；另外一种是当前匹配算法，即只计算欲匹配数据当前所在位置之前的数据，而不管之后的数据.这两种方法都能解决图片匹配问题，但各有优势.本文分别讨论这两种方案并详细介绍当前匹配算法.

1 iPhone应用遵循的架构

1.1 iOS

iOS原称为iPhone OS，是为了满足iPhone及iTouch的移动环境而设计的，它通过系统接口与硬件接触，相当于软硬件之间的一个中间层.iOS的存在使得底层的变更最小限度地影响上层，不论如何变更底层的硬件，只要保证其接口不变，则上层应用不受影响.iOS包含在iPhone和iTouch上运行本地应用程序所需的操作系统和技术基础.iPhone跟Mac OS X 有共同的基础构架和底层技术［1］.iOS系统架构分为4个层次，如图1所示.

图1 iOS架构层次图Fig.1 iOS structure levels

根据4个层次的不同，代码实现的选择也不同.其中核心操作系统层和核心服务层包含了iPhone的基础接口，用于对文件、底层数据类型、网络接口等进行访问.核心操作系统层和核心服务层位于架构的底层，实现也大多基于C语言.触摸层及媒体层更接近表层，接口也是由C语言及Objective C语言实现.例如，在媒体层包含支持二维和三维绘图以及音频和视频的基础技术，它还包括了核心动画技术等.而触摸层的接口大多是基于Objective C语言实现的，它提供了应用程序的基础架构［1］.该层的UIKit框架提供了开发所需的各种窗口、视图以及对象控制器等，它是任何一个新项目的起点.

iOS为应用提供了开发及运行环境，是iPhone、iTouch以及iPad得以运行的基础，其重要性不言而喻，因此，了解iOS的架构对于应用开发者而言是非常必要的，这是开发iPhone应用的一个重要基础.

1.2 iPhone应用架构的设计模式

1.2.1 Cocoa框架的设计模式

Cocoa框架是苹果的面向对象开发框架，它是Mac OS X操作系统的应用程序环境之一［2］，用来支持Mac OS X及iOS的应用程序.在传统的开发中，经常会有“胶水代码”的困扰，为了保持用户界面数据和状态同步，需要进行大量编码，使代码变得冗长、易出错、难维护.为了解决这个问题，Cocoa框架采用了 “模型 （Model）-视图（View）-控制器（Controller）”即 MVC的设计模式［3］.MVC模式将业务逻辑、用户界面显示与数据处理相互分离，各司其职.Model负责系统的业务逻辑，接受视图的数据请求并返回处理结果.View代表用户交互界面，在Cocoa中，View的代表是UIView.Controller主要用于控制Model与View，以完成需求，在Cocoa中，UIViewController为其代表.

通过MVC模式，Cocoa消除了大部分的“胶水代码”，降低了模型与视图间的耦合［4－5］，使它们可以独立变化，再通过Controller进行组合，使得应用具有充分的灵活性.Cocoa中除了整体MVC模型外，其内部的一些子系统也会重复使用MVC设计模式，可以看出Cocoa中贯穿了这种模式.

1.2.2 iOS应用的设计模式

iOS应用为了能够更好地使用Cocoa框架，也应尽量遵守MVC模式.一般iPhone应用程序可能会含有多个功能模块，若将多个模块使用一个Controller进行控制，管理起来会比较困难，还会造成单个文件过于庞大、逻辑过于复杂的情况.根据实际情况可以将应用分解成多个功能模块，每个功能模块使用一个MVC模式实现.这样就减少了Controller的控制复杂度，也减少了文件的大小，维护会相对简单.在实际应用中，为了便于修改和维护，使用多个MVC模式的方法得到了广泛的应用.

2 匹配算法

2.1 视图请求方案

iPhone应用中图片获取问题成为其不可避免的问题.在实际应用中一般数据的获取由控制器驱动，业务逻辑层收到请求后会向服务器端发送请求，服务器端返回数据到业务逻辑层.业务逻辑层再通过委托函数将获取的数据传给请求驱动的控制器，再由控制器分发给相应的视图进行显示，这是MVC模式中数据流动的一个基本过程.图片的获取同一般的数据获取一样，需要经过这样几个阶段.如果一个控制器只请求一个图片，则获取的数据直接分发给视图进行显示即可.但当控制器需要请求多张图片时，则需要考虑返回的数据如何分发给视图，使其能够在相应的视图上正确显示.这就需要控制器将取得的数据与原本请求数据的对象进行匹配，将数据按照正确的顺序传送给相应的视图使其正确显示.

如果要避免多张图片匹配的问题，最简单的方法是每次只发送一个请求.然而，控制器负责整个应用中模型与视图的控制作用，因此，很难做到在控制器中只发送一个请求.而通过视图直接请求图片则可以实现每次只发送一个请求的操作.每个视图请求一个图片，实现获取数据的委托函数，将获取的数据直接在该视图中显示即可.视图请求方案的实质是避免了返回数据与请求模块的匹配.这种解决方案的优势在于图片数据与视图是一一对应的，即，在请求发出时已完成匹配，其能够最大限度地降低时间复杂度和空间复杂度.但是，通过视图进行数据请求对MVC设计模式具有一定的破坏性，对于规模较小且结构简单的应用使用该种请求方案能够降低应用的复杂度以及数据处理复杂度.对于规模较大或结构较复杂的应用，该种解决方案局限性较大.

2.2 当前匹配算法

在遵循MVC设计模式的基础上，本节提出另一种有效的解决方案——当前匹配算法，它适用于各种规模的应用，且能够严格遵守MVC设计模式.

在数据请求的过程中，发送到服务器端的信息始终不会丢失，客户端可以通过服务器端返回的数据所附的信息与发送的信息进行比较，将返回数据与对应的请求数据的对象进行匹配.为了简单起见，假设所有请求的地址是唯一的，将其作为匹配的标准.根据标识符进行搜索的图片匹配算法［6－7］，称之为当前匹配算法.

（1）假设数组a和b分别表示长度为n的两个数组，a［k］和b［k］分别表示数组中第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）直到完成所有匹配.

其中，数组a表示原始请求序列，数组b表示返回数据附属信息的序列，即分别为请求地址的序列以及返回数据所对应的地址，将两者进行匹配以确定返回数据所在的位置.具体算法示意图如图2所示.

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

当前匹配算法的核心思想是比较到达数据所在位置之前的序列，之后的序列不做考虑，而且匹配的元素对不参与比较，这样在位置k处比较的次数都小于k，大大减少了比较的次数.每次请求比较的数据与原序列中当前位置的元素进行比较，若不匹配则两个元素都被标记为不匹配，然后将到来数据所在数组中标记的元素与原数组中当前元素进行比较，再将原数组中标记的元素与到来的当前数据进行比较，匹配的数据去除标记，则下次参与比较的数据减少.这种将一组数据中的标记元素与另外一组数据中的当前元素进行比较的做法，能够防止出现遗漏或者死循环现象，保证匹配高质量、高效率地进行.

由上述算法可以看出，该算法与返回数据的顺序相关性极大，本文给出乱序因子的概念.乱序因子用于表示返回序列与请求序列中顺序不一致的程度，用d表示，0≤d≤1，d＝0表示没有乱序，即返回序列与请求序列完全一致，d＝1表示完全乱序，即返回序列与请求序列在相应位置上没有任何匹配.若d＝0，则该算法的时间复杂度为O（1），而d＝1时，该算法的时间复杂度为O（n2），由此可以看出，乱序因子对该算法的影响极大.

3 算法实现

当前匹配算法是基于iPhone应用提出的，iPhone开发使用的是Objective C语言.为了遵循MVC模式，将请求图片的业务逻辑封装为一个模型，使得所有的图片请求都通过该类实现，将接收参数的接口以及传输数据的接口留给用户，其他的则对用户透明.在Objective C语言中，数据传递常通过委托函数来实现，因此，业务逻辑层获取数据后将地址数据与获取的数据打包后，通过委托函数将数据传送给控制器，控制器只要实现模型的委托函数就能获取其传送的数据.具体的数据匹配是在控制器中实现的，将图片进行匹配后，由控制器将相应格式的数据传送给视图，由视图进行展示.该算法的伪代码段如下：

1.将b［k］对应的数据与相应位置的对象绑定｝

在实际应用中，数组b中的地址数据是单个传送过来的，并不是一开始就全部存在该数组中，实际应用中的做法是把不匹配的地址放入数组b中，若匹配则直接将与该地址对应的图片数据保存在相应的位置，以供使用.实际应用中系统的架构如图3所示.

图3 系统架构图Fig.3 System architecture

4 试验结果及分析

图4 当前匹配算法与顺序查询算法对比Fig.4 Current matching versus normal search

由图4还可以看出，乱序因子对当前匹配算法的影响很大，乱序因子主要受服务器处理性能的影响.服务器处理性能高则乱序因子低，服务器处理性能与乱序因子呈反比关系.乱序因子越低则当前匹配算法效率越高，因此，服务器处理性能与当前匹配算法的效率呈正比关系.服务器处理性能与乱序因子的关系如图5所示.

已经成熟的查询算法有折半查询、平衡二叉树查询以及哈希表查询等.这些查询的时间复杂度如表1所示.

图5 乱序因子与服务器处理性能的关系Fig.5 Relationship between confused factor and process performance of server

表1 查询算法比较Table 1 Comparison of search algorithm

由表1可以看出，折半查询、平衡二叉树查询以及哈希表查询的时间复杂度都比当前匹配算法的时间复杂度要低.但是这些算法都具有一定的适用环境，折半查询适用于有序表，与本文的当前匹配算法适用环境不同.平衡二叉树查询算法需要构造平衡二叉树，有额外的时间和空间开销.而哈希表查询则是以空间换取时间的典型代表，它需要空间辅助，而在iPhone中，空间资源有限，因而哈希表的方法并不适用.当前匹配算法的时间复杂度虽然不是最优，但是通过乱序因子能够降低一定的复杂度，而空间消耗也较低，比较适合于iPhone应用的使用.

文献 ［16］中介绍了多种查询算法，除了传统的静态查询与动态查询算法之外，学者们还提出了许多其他类型的查询，典型的字符串查询则有BM（Boyer Moore）算法和 KMP（Knuth，Pratt，Morris）算法等，这些算法大部分都有一些适用条件或背景.本文所提出的当前匹配算法适用于iOS应用中特定框架下图片数据乱序匹配的问题，当然也可以推广到非图片的其他数据中加以应用.

5 结 语

目前关于数据与请求数据对象的匹配存在很多查询算法，其中大部分算法是基于特定数据模式的，而本文提出的当前匹配算法也存在其特定的要求，即需要匹配的数据集与原数据集在一定程度上具有相似顺序.本文提出乱序因子的概念来衡量两个数据集之间顺序的相似程度，并通过该参数观察当前匹配算法所需要消耗的大致时间，研究同时也表明，可以通过提高配置来控制该参数使得查询时间大大降低.当前匹配算法在存在乱序因子的数据集上能够进行更有效的查询，节省查询时间，提高查询效率.最后通过试验验证了该算法的优势.

参 考 文 献

［1］和凌志，郭世平.手机软件平台架构解析［M］.北京：电子工业出版社，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—），女，湖北武汉人，副教授，博士，研究方向为数据可视化与数据处理.E－mail：sherlysha＠dhu.edu.cn