:::

用JSON加快JavaScript的搜尋速度

image

(圖片來源:ICON FINDER)

最近在寫JavaScript程式,在這邊跟大家分享一些程式撰寫的小技巧。JavaScript在網頁應用中通常是作為客戶端的應用程式,而JavaScript的運作速度時常取決於客戶端使用的瀏覽器與電腦效能。要執行複雜的JavaScript運算時,使用Google Chrome跟使用Internet Explorer (簡稱IE,特別是6以下)會有相當驚人的差距。

最近發現我的程式在IE上的瓶頸卡在「搜尋速度」上。如果修過資料結構的同學一定知道,資料結構最常探討的問題就是「搜尋」。提高搜尋速度有很多已知的方法,平常撰寫時通常只會實作最簡單但也是最沒效率的循序演算法(sequential search),而這也就是執行效率的瓶頸。然而多虧JavaScript的特殊資料結構JSON,我們也可以犧牲一些記憶體空間來換取非常快的執行速度,實作雜湊搜尋法(Hash Search)

以下就簡單介紹一下這些方法的差別。


低效率搜尋:循序演算法

現在我想要做一個函式(function),它會要求輸入一個字,並確認這個字是否是大寫英文,輸出「true」或「false」。

陣列版本

簡單一點的作法,我們可以用陣列(array)來實作:

/**
* 檢查一個字是否是英文大寫。(陣列搜尋版本)
* @param String _word 要檢查的字
* @return boolean 是英文,或不是英文
*/
function is_english_by_array(_word) {
var _english_list = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];

for (var _i in _english_list)
{
if (_word == _english_list[_i])
return true;
}
return false;
}

alert(is_english_by_array('Z'));

這是很直覺的寫法,要比對的資料組成一個陣列資料集,然後再一一比對。雖然看起來有點冗長,效率也不高。

正規表示法版本

聰明一點的人會用正規表示法(Regular Expression)來作字串的搜尋,以下是改用正規表示法的寫法:

/**
* 檢查一個字是否是英文大寫。(正規表示法版本)
* @param String _word 要檢查的字
* @return boolean 是英文,或不是英文
*/
function is_english_by_reg(_word) {
var _reg = /^([A-Z])$/;
return _reg.test(_word);
}

alert(is_english_by_reg('Z'));

看起來簡潔多了。但其實正規表示法的效率極差,這樣子的搜尋速度並不會快到哪裡去。

JSON與雜湊演算法

自從學會使用JSON之後,我就愛上了這種特殊的資料格式,特別是用在雜湊演算法的時候實在是很方便。

JSON介紹

以下引用維基百科對JSON的介紹

JSON(Javascript Object Notation)是一種輕量級的資料交換語言,以文字為基礎,且易於讓人閱讀。

JSON用於描述數據結構,有以下形式存在。

  • 物件 (object):一個物件以「{」開始,並以「}」結束。一個物件包含一系列非排序的名稱/值對,每個名稱/值對之間使用「,」分割。
  • 名稱/值對(collection):名稱和值之間使用「:」隔開,一般的形式是:
{name:value}

一個名稱是一個字串; 一個值可以是一個字串,一個數值,一個物件,一個布林值,一個有序列表,或者一個null值。

  • 值的有序列表(Array):一個或者多個值用「,」分割後,使用「[」,「]」括起來就形成了這樣的列表,形如:
[collection, collection]

  • 字串:以""括起來的一串字元。
  • 數值:一系列0-9的數位組合,可以為負數或者小數。還可以用「e」或者「E」表示為指數形式。
  • 布林值:表示為 true 或者 false。
雜湊搜尋法

用JSON實作雜湊搜尋法的方式,跟上面用陣列來實作的方式有點像:他們一樣是要準備一個可供搜尋的資料集,只是資料結構的方式完全不同。

以下是用JSON實作的雜湊搜尋法:

/**
* 檢查一個字是否是英文大寫。(JSON版本)
* @param String _word 要檢查的字
* @return boolean 是英文,或不是英文
*/
function is_english_by_json(_word) {
var _english_list = {'A':1,'B':1,'C':1,'D':1,'E':1,'F':1,'G':1,'H':1,'I':1,'J':1,'K':1,'L':1,'M':1,'N':1,'O':1,'P':1,'Q':1,'R':1,'S':1,'T':1,'U':1,'V':1,'W':1,'X':1,'Y':1,'Z':1};
return (typeof(_english_list[_word])=="number");
}

alert(is_english_by_json('Z'));

跟陣列把要比對的資料放在「值」(value)的方式不同,雜湊法中要比對的資料是放在「名稱」(name)當中。因此一旦用typeof()確認資料集中是否有該名稱時,就能夠知道搜尋的結果。

至於資料集中的值為何是用1?其實在此問題中用什麼值是無所謂,因為我只要確認該_word是否在待比對資料集裡面就好了。


結語

寫JavaScript實在是很有趣。

傳統在教資料結構時,大多是用C或Java在做教學。然而由於語言先天上的限制,像是強型別(Strong Type)、僅有基本的資料型態等等的特性,在實作資料結構與演算法時,其實是需要非常多步驟。對於JavaScript來說,既有JSON這個萬用的資料結構,也可以把function當做是資料型態,因此寫起程式來可說是非常靈活。

然而不僅僅只是在客戶端的應用,現在也越來越多人把JavaScript拿到伺服器端來使用,稱之為Server-side JavaScript (SSJS),目前相當知名應用之一就是Node.js

相信未來JavaScript會更加蓬勃發展,大家一起加油吧。

0 意見:

留言工具: