:::

用JSON加快JavaScript的搜尋速度

11月 07, 2011 , , 0 Comments Edit Copy Download

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會更加蓬勃發展，大家一起加油吧。

訂閱： 張貼留言 (Atom)