武汉java培训
达内武汉中心

15271940953

热门课程

武汉java培训:Java高性能解析器实现思路

  • 时间:2017-03-24
  • 发布:武汉Java培训
  • 来源:Java教程

武汉java培训:Java高性能解析器实现思路

在某些情况下,你可能需要在Java中实现你自己的数据或语言解析器,也许是这种数据格式或语言缺乏标准的Java或开源解析器可以使用。或者虽然有现成的解析器实现,但它们要么太慢,要么太占内存,要么就是没有符合你所需要的特性。又或者是某个开源的解析器存在缺陷,要么是某个开源解析器的项目中止了,原因不一而足。不过无论原因是什么,总之事实就是你必须要自己去实现这个解析器。

当你必须自己实现一个解析器时,你对它的期望会有很多,包括性能良好、灵活、特性丰富、方便使用,以及便于维护等等。说到底,这也是你自己的代码。在本文中,我将为你介绍在Java中实现高性能解析器的一种方式,这种方法并且独一无二,但难度适中,不仅实现了高性能,而且它的模块化设计方式也比较合理。这种设计是受到了VTD-XML的设计方式的启发,后者是我所见过的最快的Java XML解析器,比起StAX和SAX这两种标准的Java XML解析器都要快上许多。

两种基本的解析器类型

为解析器进行分类的方式有好几种,在这里我将解析器分为两种基础类型:

顺序访问解析器

随机访问解析器

顺序访问是指解析器对进行数据进行解析,在数据解析完成后将其转交给数据处理器(processor)的过程。数据处理器只能访问当前正在进行解析的数据,它既不能访问已解析过的数据,也不能访问等待解析的数据。这种解析器也被称为基于事件的解析器,例如SAX和StAX解析器。而随机访问解析器是指解析器允许数据处理代码可以随意访问正在进行解析的数据之前和之后的任意数据(随机访问)。这种解析器的例子有XML DOM解析器。

顺序访问解析器只能让你访问当前正在解析的“视窗”或“事件”,而随机访问解析器允许你任意地浏览所有已解析数据。

设计概况

我在这里所介绍的解析器设计属于随机访问解析器。

随机访问解析器的实现通常会慢于顺序访问解析器,因为它们一般都会为已解析数据创建某种对象树,数据处理代码将通过这棵树对数据进行访问。创建这种对象树不仅要花费较长的CPU时间,消耗的内存也很大。

相对于从已解析数据中创建一棵对象树的方式,另一种性能更佳的方式是为原来的数据缓冲区建立一个对应的索引缓冲区,这些索引会指向在已解析数据中找到的元素的起点与终点。数据处理代码此时不再通过对象树访问数据,而是直接在包括了原始数据的缓冲区中访问已解析数据。以
由于我找不到一个更好的名字,因此我将这种方式简单地命名为“索引覆盖解析器”(Index Overlay Parser)。该解析器为原始数据创建了一个覆盖于其上的索引。这种方式让人联想起数据库索引将数据保存在磁盘的方式,它为原始的、未处理的数据创建了一个索引,以实现更快地浏览和搜索数据的目的。

如同我之前所说的,这种设计方式是受到了VTD-XML(VTD是指虚拟令牌描述符)的启发,因此你也可以把这种解析器称为虚拟令牌描述符解析器。但我还是倾向于索引覆盖这个名字,因为它表现了虚拟令牌描述符的本质,即对原始数据建立的索引。
解析器设计概要

一种常规的解析器设计方式将解析过程分为两步。第一步是将数据分解为内聚的令牌,一个令牌是已解析数据中的一个或多个字节或字符。第二步是对令牌进行解释,并根据这些令牌构建更大的元素。以下是这两个步骤的图示:
这里的元素并不一定是指XML元素(虽然XML元素也是解析器元素),而是指构成解析数据的更大的“数据元素”。比如说,在一个XML文档中元素代表了XML元素,而在一个JSON文档中元素则代表了JSON对象,等等。

举例来说,<myelement>这个字符串可以被分解为以下几个令牌:

一旦数据被分解为令牌,解析器就能够相对容易地了解它的意义,并且决定这些令牌构成的更大的元素。解析器就能够理解一个XML元素是由一个’<’令牌开始,随后是一个字符串(即元素名称),随后有可能是一些属性,最后以一个’>’令牌结尾。
索引覆盖解析器设计

在这种解析器的设计方式中也包含了两个步骤:输入数据首先被一个令牌生成器(tokenizer)组件分解为令牌,解析器随后将对令牌进行解析,以决定输入数据的一个更大的元素边界。

你也可以为解析过程加入一个可选的“元素浏览步骤”。如果解析器从解析数据中构建出一棵对象树,它通常会包含在整棵树中进行浏览的链接。如果我们不选择对象树,而是构建出一个元素索引缓冲区,我们也许需要另一个组件以帮助数据处理代码在元素索引缓冲区中进行浏览。
以下是我们的解析器设计的概要:

我们首先将所有数据读入一个数据缓冲区中,为了能够通过在解析过程中创建的索引对原始数据进行随机访问,所有的原始数据必须已经存在于内存中。

第二步,令牌生成器会将数据分解为令牌。令牌生成器内部的某个令牌缓冲区会将该令牌的起点索引、终点索引和令牌类型都保留下来。使用令牌缓冲区使你能够查找之前或之后的令牌,在这种设计中解析器会利用到这一项特性。

第三步,解析器获取了令牌生成器所产生的令牌,根据上下文对其进行验证,并决定它所表示的元素。随后解析器会根据从令牌生成器处获取的令牌构建一个元素索引(即索引覆盖)。解析器会从令牌生成器中一个接一个地获取令牌。因此令牌生成器不必立即将所有数据都分解为令牌,它只需要每次找到一个令牌就行了。

数据处理代码将浏览整个元素缓冲区,利用它访问原始数据。你也可以选择用一个元素浏览组件将元素缓冲区包装起来,使浏览元素缓冲区的工作更加简单。

这种设计不会从解析数据中生成一棵对象树,但它确实生成了一个可浏览的结构,即元素缓冲区,索引(即整数数组)将指向包含了原始数据的数据缓冲区。你可以使用这些索引浏览原始数据缓冲区中的所有数据。本文的以下部分将分析这种设计的各方面细节。

数据缓冲区

数据缓冲区是一个包括了原始数据的字节或字符缓冲区,而令牌缓冲区和元素缓冲区则包含了指向数据缓冲区的索引。
为了实现对解析数据的随机访问,必须以某种形式将它保留在内存中。我们在这里没有选择对象树,而是选择了包含未处理数据本身的数据缓冲区。

将所有数据全部保留在内存中可能会导致对内存的大量消耗。如果你的数据包含了互相独立的元素,例如日志记录,那么将整个日志文件导入内存很可能会造成崩溃。你应该采取的方式是只导入日志文件的一部分,其中至少包含一条完整的日志记录。由于每一条日志记录都可以不依赖于其它日志记录进行解析和处理,你就不需要将整个日志文件在同一时刻加载到内存里了。我在我的文章《使用缓冲区对流进行迭代处理》中描述了如何对一块数据流进行迭代的方式。

令牌生成器与令牌缓冲区

令牌生成器将数据缓冲区分解为令牌,令牌的信息会保存在令牌缓冲区中,包括以下信息:令牌的位置(起始位置的索引)

令牌长度

令牌类型(可选信息)

当令牌生成器在数据缓冲区中找到令牌之后,它会将该位置(起始位置的索引)插入position数组、将令牌长度插入length数组,并将令牌类型插入type数组。

如果你不使用这个可选的令牌类型数组,你也可以在需要的时候通过令牌中的数据得出令牌的类型。这是一种性能与内存占用之间的权衡。

上一篇:文科性专业的学生学java怎么样?
下一篇:武汉java培训课程:java数组

武汉Java培训:Java如何创建和启动多线程

武汉Java培训:java多线程教程

武汉Java培训:Java数组声明、创建和初始化

武汉Java培训:在Java常量中如何避免反模式

选择城市和中心
贵州省

广西省

海南省