Boyer Moore 字符串搜索算法之 JavaScript 实现

0

最近碰到的一个需求需要借助字符串的快速搜索算法,于是看了一些有关字符串搜索的一些算法,最先看的是 KMP 算法,看完之后发现还有更优的算法,那就是 Boyer Moore 算法。编辑器的文本搜索、GNU 的 grep 都有使用 Boyer Moore 算法,那么效率应该是经过权威验证的。

虽然网上有不少介绍资料,但我还是从一个算法小白所理解的算法原理来尝试解析该算法,算法大神可绕道了。

从头至尾搜索一个字符串,看这个被搜索的字符串是否包含指定的子串,有则返回其位置,没有则返回 -1,相当于使用自己的算法来实现 JavaScript 中的 String.prototype.indexOf 的功能。

阅读全文 »

使用 gulp-seajs-combo 合并 seajs 模块

在之前的 前端自动化构建和发布系统的设计(一) 中我有提到过使用 gulp-seajs-combo 合并 JS 模块的问题。在那篇文章中只提供了简单的 demo,当然在 github 上有详细的文档以及测试用例,尽管如此,还是会有人对使用会有诸多疑惑,希望能在看完此文后对使用 gulp-seajs-combo 合并 seajs 模块有更深入的了解。

无论是使用什么样的模块化开发模式,不管是 AMD 还是 CMD,抑或是其他类型的模块化规范,在开发时都会将一个大的应用或功能分割成一些小模块,而到了生产环境,为了能节省 HTTP 请求数,会希望将原来的小模块进行合并。

在开发环境,模块加载器解决了模块的依赖和加载的问题,由于客户端 JS 的使用特性,依赖和加载是绕不开的两个问题,不管你用的是小而美的模块加载器还是看起来很高大上的框架。在生产环境中,对模块按照依赖进行合并,这就是合并工具应该做的事情。

阅读全文 »

Handlebars 和 SeaJS 的结合使用

Handlebars 是一款语义化的模板引擎,其模板语法就像是在写普通的 HTML 代码,并且在性能方面也表现优秀。本文将介绍 Handlebars 如何结合 seajs 来使用。

模板引擎的编译和预编译

开发者用语义化的代码编写好模板,然后将编写好的模板再进行编译,这个编译环节是必不可少的。服务端的模板也同样需要编译,只是这个编译环节是在服务器上进行的。

前端模板引擎要么是直接在浏览器中进行编译,要么就先将模板进行预编译,预编译的代码是可以直接放到浏览器中运行的。在浏览器中编译就意味着会有一些编译时的性能开销,如果要追求前端性能的话,肯定是使用预编译好的模板。

Handlebars 提供了支持编译和不支持编译的 2 种版本,不支持编译的 runtime 版本只能运行预编译好的模板,而 runtime 版本的库文件理所当然要小得多。

在开发环境中,要确保开发方便,引用的是支持编译的库文件,而在生产环节中,模板经过了预编译,此时引用的是 runtime 版本。

阅读全文 »

JavaScript算法题之–查找不同顺序排列的字符串

需求描述:从一组数组中找出一组按不同顺序排列的字符串的数组元素。假如有这样一个数组:

[ 'abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc' ]

需要找出的结果是:

[ 'abcd', 'bdca', 'cadb' ]

那么这里的关键点其实是判断一组字符串是否是否只是字符的顺序不同,只要解决整个关键点其他都好办了。

方法1:

var stringClassify = function( arr ){
	var arrLength = arr.length,
		obj = {},
		i = 0,
		num, item, name, strLength;

	for( ; i < arrLength; i++ ){
		item = arr[i];
		strLength = item.length;
		num = 0;

		// 将单个的字符转换成 Unicode 编码
		// 对编码进行取和计算
		for( j = 0; j < strLength; j++ ){
			num += item.charCodeAt( j );
		}		

		if( !obj[num] ){
			obj[ num ] = [];
		}	

		obj[ num ].push( item );
	}

	for( name in obj ){
		console.log( obj[name] );
	}
};	
阅读全文 »

JavaScript算法题之–随机数的生成

需求描述:从一组有序的数据中生成一组随机并且不重复的数,类似于简单的抽奖程序的实现。

先来生成一个有序的数组:

var arr = [],
	length = 100,
	i = 0;

for( ; i < length; i++ ){
	arr.push( i );
}

从一个长度为 100 的有序数组中随机拿出 10 个随机的数,并且不能有重复。

阅读全文 »