浏览器中大型XML文件的快速自然排序
Fast Natural Sort for Large XML File in Browser?
我现在遇到了一个问题,这是我们团队无法控制的服务器当前限制的结果。
我们有一个应该由数据库完成的工作,但我们被迫使用XML文件并使用Javascript/jQuery解析它。我们甚至没有对脚本的写权限(只能通过我们的FTP帐户)…我们不喜欢谈论它,但这就是我们得到的。
这些限制导致的问题是,我们需要解析一个大约500kb的大型XML文件,其中包含1700条文档名称/编号/url记录。
这个数字很复杂,比如"31-2b-1029E",和"T2315342"这样的数字混在一起。
所以,我认为我需要使用一种叫做"自然排序"的东西(谢谢你stackoverflow)。
无论如何,我试着在这里使用这个脚本:
/*
* Reference: http://www.overset.com/2008/09/01/javascript-natural-sort-algorithm/
* Natural Sort algorithm for Javascript - Version 0.6 - Released under MIT license
* Author: Jim Palmer (based on chunking idea from Dave Koelle)
* Contributors: Mike Grier (mgrier.com), Clint Priest, Kyle Adams, guillermo
*/
function naturalSort (a, b) {
var re = /(^-?[0-9]+('.?[0-9]*)[df]?e?[0-9]?$|^0x[0-9a-f]+$|[0-9]+)/gi,
sre = /(^[ ]*|[ ]*$)/g,
dre = /(^(['w ]+,?['w ]+)?['w ]+,?['w ]+'d+:'d+(:'d+)?['w ]?|^'d{1,4}['/'-]'d{1,4}['/'-]'d{1,4}|^'w+, 'w+ 'd+, 'd{4})/,
hre = /^0x[0-9a-f]+$/i,
ore = /^0/,
// convert all to strings and trim()
x = a.toString().replace(sre, '') || '',
y = b.toString().replace(sre, '') || '',
// chunk/tokenize
xN = x.replace(re, ''0$1'0').replace(/'0$/,'').replace(/^'0/,'').split(''0'),
yN = y.replace(re, ''0$1'0').replace(/'0$/,'').replace(/^'0/,'').split(''0'),
// numeric, hex or date detection
xD = parseInt(x.match(hre)) || (xN.length != 1 && x.match(dre) && Date.parse(x)),
yD = parseInt(y.match(hre)) || xD && y.match(dre) && Date.parse(y) || null;
// first try and sort Hex codes or Dates
if (yD)
if ( xD < yD ) return -1;
else if ( xD > yD ) return 1;
// natural sorting through split numeric strings and default strings
for(var cLoc=0, numS=Math.max(xN.length, yN.length); cLoc < numS; cLoc++) {
// find floats not starting with '0', string or 0 if not defined (Clint Priest)
oFxNcL = !(xN[cLoc] || '').match(ore) && parseFloat(xN[cLoc]) || xN[cLoc] || 0;
oFyNcL = !(yN[cLoc] || '').match(ore) && parseFloat(yN[cLoc]) || yN[cLoc] || 0;
// handle numeric vs string comparison - number < string - (Kyle Adams)
if (isNaN(oFxNcL) !== isNaN(oFyNcL)) return (isNaN(oFxNcL)) ? 1 : -1;
// rely on string comparison if different types - i.e. '02' < 2 != '02' < '2'
else if (typeof oFxNcL !== typeof oFyNcL) {
oFxNcL += '';
oFyNcL += '';
}
if (oFxNcL < oFyNcL) return -1;
if (oFxNcL > oFyNcL) return 1;
}
return 0;
}
并使用:
// Natural Sort (disabled because it is super freaking slow.... need xsl transform sorting instead)
var sortedSet = $(data).children("documents").children("document").sort(function(a, b) {
return naturalSort($(a).children('index').text(), $(b).children('index').text());
});
这在我们的其他较小的XML文件上工作得很好,但是对于500kb左右的大文件,Safari (v4)只是简单地挂起几分钟来进行排序,而Firefox(最新)需要大约10秒来处理(仍然不是很好,但至少是正常的)。
我还发现了另一个更小/更轻的脚本叫做Alphanum:
function alphanum(a, b) {
function chunkify(t) {
var tz = [], x = 0, y = -1, n = 0, i, j;
while (i = (j = t.charAt(x++)).charCodeAt(0)) {
var m = (i == 46 || (i >=48 && i <= 57));
if (m !== n) {
tz[++y] = "";
n = m;
}
tz[y] += j;
}
return tz;
}
var aa = chunkify(a);
var bb = chunkify(b);
for (x = 0; aa[x] && bb[x]; x++) {
if (aa[x] !== bb[x]) {
var c = Number(aa[x]), d = Number(bb[x]);
if (c == aa[x] && d == bb[x]) {
return c - d;
} else return (aa[x] > bb[x]) ? 1 : -1;
}
}
return aa.length - bb.length;
}
这在Safari中运行得更快,但仍然会将浏览器锁定一分钟左右。
我做了一些研究,似乎有一些人建议使用XSL对XML条目进行排序,这显然要快得多,因为它被内置到浏览器中,而不是运行在JavaScript之上。
显然有几种不同的实现,Sarissa被多次提到,sourceforge页面似乎表明最后一次更新发生在2011-06-22。
还有其他选择,如xslt.js
我的问题是:- XSL是解决这个特定问题的最佳排序选项吗?
- 如果是这样,我如何使用XSL来做自然排序?(url到资源?)
- 如果对两个问题都是肯定的,我应该使用哪个库来获得最佳兼容性和速度?
- 如果XSL不是最佳选择,那么哪一个才是?
谢谢你看我的问题。
好问题,+ 1。
这里是一个XSLT 1.0解决方案(有一个XSLT 2.0解决方案更简单,更容易编写,可能更有效,但是5个主要浏览器都没有提供XSLT 2.0处理器):
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:ext="http://exslt.org/common" exclude-result-prefixes="xml">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:strip-space elements="*"/>
<xsl:variable name="vDigits" select="'0123456789'"/>
<xsl:variable name="vPadding" select=
"' '"/>
<xsl:variable name="vMaxNumLength"
select="string-length($vPadding)"/>
<xsl:template match="/">
<xsl:variable name="vrtfPass1">
<t>
<xsl:apply-templates/>
</t>
</xsl:variable>
<xsl:variable name="vPass1" select="ext:node-set($vrtfPass1)"/>
<t>
<xsl:for-each select="$vPass1/*/*">
<xsl:sort select="@sortMe"/>
<xsl:copy>
<xsl:value-of select="."/>
</xsl:copy>
</xsl:for-each>
</t>
</xsl:template>
<xsl:template match="str">
<str>
<xsl:apply-templates select="text()" mode="normalize"/>
<xsl:copy-of select="text()"/>
</str>
</xsl:template>
<xsl:template match="text()" mode="normalize" name="normalize">
<xsl:param name="pText" select="."/>
<xsl:param name="pAccum" select="''"/>
<xsl:choose>
<xsl:when test="not(string-length($pText) >0)">
<xsl:attribute name="sortMe">
<xsl:value-of select="$pAccum"/>
</xsl:attribute>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="vChar1" select="substring($pText,1,1)"/>
<xsl:choose>
<xsl:when test="not(contains($vDigits,$vChar1))">
<xsl:variable name="vDig1" select=
"substring(translate($pText,
translate($pText, $vDigits, ''),
''
),
1,1)"/>
<xsl:variable name="vDig">
<xsl:choose>
<xsl:when test="string-length($vDig1)">
<xsl:value-of select="$vDig1"/>
</xsl:when>
<xsl:otherwise>0</xsl:otherwise>
</xsl:choose>
</xsl:variable>
<xsl:variable name="vNewText" select=
"substring-before(concat($pText,$vDig), $vDig)"/>
<xsl:call-template name="normalize">
<xsl:with-param name="pText" select=
"substring($pText, string-length($vNewText)+1)"/>
<xsl:with-param name="pAccum" select=
"concat($pAccum, $vNewText)"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="vNonDig1" select=
"substring(translate($pText, $vDigits, ''),1,1)"/>
<xsl:variable name="vNonDig">
<xsl:choose>
<xsl:when test="string-length($vNonDig1)">
<xsl:value-of select="$vNonDig1"/>
</xsl:when>
<xsl:otherwise>Z</xsl:otherwise>
</xsl:choose>
</xsl:variable>
<xsl:variable name="vNum" select=
"substring-before(concat($pText,'Z'),$vNonDig)"/>
<xsl:variable name="vNumLength" select=
"string-length($vNum)"/>
<xsl:variable name="vNewText" select=
"concat(substring($vPadding,
1,
$vMaxNumLength -$vNumLength),
$vNum
)"/>
<xsl:call-template name="normalize">
<xsl:with-param name="pText" select=
"substring($pText, $vNumLength +1)"/>
<xsl:with-param name="pAccum" select=
"concat($pAccum, $vNewText)"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
:
<t>
<str>Allegia 6R Clasteron</str>
<str>200X Radonius</str>
<str>Xiph Xlater 10000</str>
<str>1000X Radonius Maximus</str>
<str>Callisto Morphamax 6000 SE</str>
<str>10X Radonius</str>
<str>20X Radonius</str>
<str>30X Radonius</str>
<str>20X Radonius Prime</str>
<str>40X Radonius</str>
<str>Allegia 50 Clasteron</str>
<str>Allegia 500 Clasteron</str>
<str>Allegia 50B Clasteron</str>
<str>Allegia 51 Clasteron</str>
<str>Alpha 100</str>
<str>Alpha 2</str>
<str>Alpha 200</str>
<str>Alpha 2A</str>
<str>Alpha 2A-8000</str>
<str>Alpha 2A-900</str>
<str>Callisto Morphamax</str>
<str>Callisto Morphamax 500</str>
<str>Callisto Morphamax 5000</str>
<str>Callisto Morphamax 600</str>
<str>Callisto Morphamax 6000 SE2</str>
<str>Callisto Morphamax 700</str>
<str>Callisto Morphamax 7000</str>
<str>Xiph Xlater 2000</str>
<str>Xiph Xlater 300</str>
<str>Xiph Xlater 40</str>
<str>Xiph Xlater 5</str>
<str>Xiph Xlater 50</str>
<str>Xiph Xlater 500</str>
<str>Xiph Xlater 5000</str>
<str>Xiph Xlater 58</str>
</t>
生成所需的正确的"自然排序"结果:
<t>
<str>10X Radonius</str>
<str>20X Radonius</str>
<str>20X Radonius Prime</str>
<str>30X Radonius</str>
<str>40X Radonius</str>
<str>200X Radonius</str>
<str>1000X Radonius Maximus</str>
<str>Allegia 6R Clasteron</str>
<str>Allegia 50 Clasteron</str>
<str>Allegia 50B Clasteron</str>
<str>Allegia 51 Clasteron</str>
<str>Allegia 500 Clasteron</str>
<str>Alpha 2</str>
<str>Alpha 2A</str>
<str>Alpha 2A-900</str>
<str>Alpha 2A-8000</str>
<str>Alpha 100</str>
<str>Alpha 200</str>
<str>Callisto Morphamax</str>
<str>Callisto Morphamax 500</str>
<str>Callisto Morphamax 600</str>
<str>Callisto Morphamax 700</str>
<str>Callisto Morphamax 5000</str>
<str>Callisto Morphamax 6000 SE</str>
<str>Callisto Morphamax 6000 SE2</str>
<str>Callisto Morphamax 7000</str>
<str>Xiph Xlater 5</str>
<str>Xiph Xlater 40</str>
<str>Xiph Xlater 50</str>
<str>Xiph Xlater 58</str>
<str>Xiph Xlater 300</str>
<str>Xiph Xlater 500</str>
<str>Xiph Xlater 2000</str>
<str>Xiph Xlater 5000</str>
<str>Xiph Xlater 10000</str>
</t>
重要假设:该解决方案假设没有数字超过40位。虽然这在大多数实际情况下是正确的,但如果出现此限制不足的情况,则很容易修改此解决方案以接受限制值作为外部/全局参数。
最后,性能:
处理一个类似于上面的XML文档,但是有1700个str
元素,在我8年的奔腾单核3GHz CPU, 2GB RAM计算机上需要0.659秒。
:
在第一次传递中,除了将
sortMe
属性添加到每个str
元素之外,所有节点都"按原样"复制。该属性包含str
的唯一文本节点子节点的字符串值——其中任何数字都用空格左填充,总固定长度为40。在Pass 2中,我们使用单个排序键(
sortMe
属性)按字母顺序对所有str
元素进行排序。
现在,回答所有最初的4个问题:
我的问题是:XSL是解决这个特定问题的最佳排序选项吗?
如果有,怎么我可以使用XSL来进行自然排序吗?(url到资源?)
如果两者都是问题,我应该使用哪个库以获得最佳兼容性和速度吗?
如果XSL不是最佳选择,那么哪一个才是呢?
:
任何最优排序算法的实现(无论语言)都应该足够了。在这方面,XSLT是个不错的选择。
上面的代码提供了"自然"排序的完整而精确的XSLT实现。
不需要库——只需按原样使用上面的代码。如果需要帮助如何从PL调用转换,请查阅相应的文档。
任何PL(包括XSLT),只要实现了最优排序算法,都是合适的选择。
对辅助问题的几个回答:
(a) Sarissa不是一个XSLT处理器,它是一个Javascript包装层,它为作为浏览器一部分提供的XSLT处理器提供一个通用的Javascript API。
(b) XSLT .js是一个失败的项目,它试图在Javascript中实现XSLT处理器。算了吧,这都是历史了。
在这个方向上最近的努力是Saxon-CE,它目前处于alpha版本(它是用Java编写的,并使用GWT交叉编译为Javascript)。完成后,将在浏览器中显示XSLT 2.0。服务器端Saxon有一个排序,可以给你"自然排序"(<xsl:sort collation='http://saxon.sf.net/collation?alphanumeric=yes'/>
),但这在当前版本的Saxon- ce中不可用。
我以前从未听说过"自然排序"这个名字。
排序函数被调用的次数比数组中被排序的元素的次数要多,实际上要多得多。对于要排序的1700个元素,比较函数可能会被调用10,000到750,000次,具体取决于浏览器…由于排序比较函数很慢,因此您可以通过对每个元素执行一次繁重的操作并存储结果,然后对存储的结果进行排序,从而获益良多。
我打赌主要问题是你在排序函数中使用了jquery。那一定很贵。实际的自然排序比较可能相对较快。我不知道您的xml结构,但如果您可以在排序函数中抛弃jquery,请尝试将元素引用复制到新数组,这是线性时间。然后对数组进行排序。然后,循环遍历已排序的数组,并使用元素引用来设置xml文档中的顺序。
- JavaScript数组排序(函数)用于对表行进行排序,而不是排序
- 使用promise和mongoose对文档进行排序
- Selectize.js:如何对整数值的选项进行排序
- Javascript排序的图像弹出窗口..可以't单独弹出
- 如何通过引用var Using DataTables来进行分页或排序
- 为什么HTML5拖放的目标是孩子?(可排序列表)
- AngularJs对所有页面中的所有记录进行排序
- 当属性不一致时,如何根据属性对JS对象列表进行排序
- 按从高到低对多个int变量进行排序
- jQuery UI可排序-多连接列表拖动
- Javascript排序字符串或数字
- 2个backbone.js集合,具有相同的模型,但排序顺序不同
- sort而不是排序javascript
- 通过从节点父级获取所有子级对节点进行排序(获取子级数组)
- 自然排序、对象数组、多列、反向等
- 浏览器中大型XML文件的快速自然排序
- Intl.使用数字选项的排序器和自然排序不正确地对十进制数字进行排序
- 如何使用Ember.js SortableMixin按自然顺序排序
- 对电子邮件Id应用自然排序's使用ng重复
- 如何在angularJs中进行自然排序