【譯】如何百倍加速 Lo-Dash？引入惰性計(jì)算

jonh_felix 發(fā)布于2019-08-19 17:13 / 1264人閱讀

摘要：原文作者譯文如何百倍加速引入惰性計(jì)算譯者我一直以為像這樣的庫(kù)已經(jīng)不能再快了，畢竟它們已經(jīng)足夠快了。函數(shù)返回價(jià)格低于的所有元素。延遲執(zhí)行和惰性計(jì)算一起使用的是延遲執(zhí)行。懶惰計(jì)算并不是行業(yè)里的新理念。

原文：How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation.
作者: Filip Zawada

譯文：如何百倍加速 Lo-Dash？引入惰性計(jì)算
譯者：justjavac

我一直以為像 Lo-Dash 這樣的庫(kù)已經(jīng)不能再快了，畢竟它們已經(jīng)足夠快了。
Lo-Dash 幾乎完全混合了各種 JavaScript 奇技淫巧（YouTube）來(lái)壓榨出最好的性能。

惰性計(jì)算

但似乎我錯(cuò)了 - 其實(shí) Lo-Dash 可以運(yùn)行的更快。
你需要做的是，停止思考那些細(xì)微的優(yōu)化，并開(kāi)始找出更加適用的算法。
例如，在一個(gè)典型的循環(huán)中，我們往往傾向于去優(yōu)化單次迭代的時(shí)間：

var len = getLength();
for(var i = 0; i < len; i++) {
    operation(); // <- 10毫秒 - 如何優(yōu)化到9毫秒?!
}

代碼說(shuō)明：取得數(shù)組的長(zhǎng)度，然后重復(fù)執(zhí)行 N 遍 operation() 函數(shù)。譯注 by @justjavac

但是，這（優(yōu)化 operation() 執(zhí)行時(shí)間）往往很難，而且對(duì)性能提升也非常有限。
相反，在某些情況下，我們可以?xún)?yōu)化 getLength() 函數(shù)。
它返回的數(shù)字越小，則每個(gè) 10 毫秒循環(huán)的執(zhí)行次數(shù)就越少。

這就是 Lo-Dash 使用惰性計(jì)算的思想。
這是減少周期數(shù)，而不是減少每個(gè)周期的執(zhí)行時(shí)間。
讓我們看看下面的例子：

function priceLt(x) {
   return function(item) { return item.price < x; };
}
var gems = [
   { name: "Sunstone", price: 4  },
   { name: "Amethyst", price: 15 },
   { name: "Prehnite", price: 20 },
   { name: "Sugilite", price: 7  },
   { name: "Diopside", price: 3  }, 
   { name: "Feldspar", price: 13 },
   { name: "Dioptase", price: 2  }, 
   { name: "Sapphire", price: 20 }
];

var chosen = _(gems).filter(priceLt(10)).take(3).value();

代碼說(shuō)明：gems 保存了 8 個(gè)對(duì)象，名字和價(jià)格。priceLt(x) 函數(shù)返回價(jià)格低于 x 的所有元素。譯注 by @justjavac

我們把價(jià)格低于 10 美元的前 3 個(gè) gems 找出來(lái)。
常規(guī) Lo-Dash 方法（嚴(yán)格計(jì)算）是過(guò)濾所有 8 個(gè) gems，然后返回過(guò)濾結(jié)果的前 3 個(gè)。

不難看出來(lái)，這種算法是不明智的。
它處理了所有的 8 個(gè)元素，而實(shí)際上我們只需要讀取其中的 5 個(gè)元素就能得到我們想要的結(jié)果。
與此相反，使用惰性計(jì)算算法，只需要處理能得到結(jié)果的最少數(shù)量就可以了。
如圖所示：

我們輕而易舉就獲得了 37.5％的性能提升。
但是這還不是全部，其實(shí)很容易找到能獲得 1000 倍以上性能提升的例子。
讓我們一起來(lái)看看：

// 99,999 張照片
var phoneNumbers = [5554445555, 1424445656, 5554443333, … ×99,999];

// 返回包含 "55" 的照片
function contains55(str) {
    return str.contains("55"); 
};

// 取 100 張包含 "55" 的照片
var r = _(phoneNumbers).map(String).filter(contains55).take(100);

在這個(gè)例子中，map 和 filter 用來(lái)處理 99,999 個(gè)元素。
不過(guò)我們只需要它的一個(gè)子集就可以得到想要的結(jié)果了，例如 10,000 個(gè)，
性能提升也是非常大的（基準(zhǔn)測(cè)試）：

Pipelining

惰性計(jì)算帶來(lái)了另一個(gè)好處，我稱(chēng)之為 "Pipelining"。
它可以避免鏈?zhǔn)椒椒▓?zhí)行期間創(chuàng)建中間數(shù)組。
取而代之，我們?cè)趩蝹€(gè)元素上執(zhí)行所有操作。
所以，下面的代碼：

var result = _(source).map(func1).map(func2).map(func3).value();

將大致翻譯為如下的常規(guī) Lo-Dash（嚴(yán)格計(jì)算）

var result = [], temp1 = [], temp2 = [], temp3 = [];

for(var i = 0; i < source.length; i++) {
   temp1[i] = func1(source[i]);
}

for(i = 0; i < source.length; i++) {
   temp2[i] = func2(temp1[i]);
}

for(i = 0; i < source.length; i++) {
   temp3[i] = func3(temp2[i]);
}
result = temp3;

如果我們使用惰性計(jì)算，它會(huì)像下面這樣執(zhí)行：

var result = [];
for(var i = 0; i < source.length; i++) {
   result[i] = func3(func2(func1(source[i])));
}

不使用臨時(shí)數(shù)組可以給我們帶來(lái)非常顯著的性能提升，特別是當(dāng)源數(shù)組非常大時(shí)，內(nèi)存訪(fǎng)問(wèn)是昂貴的資源。

延遲執(zhí)行

和惰性計(jì)算一起使用的是延遲執(zhí)行。
當(dāng)你創(chuàng)建一個(gè)鏈，我們并不立即計(jì)算它的值，直到 .value() 被顯式或者隱式地調(diào)用。
這種方法有助于先準(zhǔn)備一個(gè)查詢(xún)，隨后我們使用最新的數(shù)據(jù)來(lái)執(zhí)行它。

var wallet = _(assets).filter(ownedBy("me"))
                      .pluck("value")
                      .reduce(sum);

$json.get("/new/assets").success(function(data) {
    assets.push.apply(assets, data); // 更新我的資金
    wallet.value(); // 返回我錢(qián)包的最新的總額
});

在某些情況下，這樣做也可以加速執(zhí)行時(shí)間。我們可以在前期創(chuàng)建復(fù)雜的查詢(xún)，然后當(dāng)時(shí)機(jī)成熟時(shí)再執(zhí)行它。

Wrap up

懶惰計(jì)算并不是行業(yè)里的新理念。它已經(jīng)包含在了許多庫(kù)里面，例如 LINQ、Lazy.js 等等。我相信 Lo-Dash 和這些庫(kù)最主要的區(qū)別是，你可以在一個(gè)更新的、更強(qiáng)大的引擎里面使用原有的 Underscore API。不需要學(xué)習(xí)新的庫(kù)，不需要修改代碼，只是簡(jiǎn)單升級(jí)。

但是，即使你不打算使用 Lo-Dash，我希望這篇文章啟發(fā)了你。
現(xiàn)在，當(dāng)你發(fā)現(xiàn)你的應(yīng)用程序存在性能瓶頸，不要僅僅是去 jsperf.com 以 try/fail 風(fēng)格優(yōu)化它。
而是去喝杯咖啡，并開(kāi)始考慮算法。
最重要的是創(chuàng)意，但良好的數(shù)學(xué)背景會(huì)讓你如魚(yú)得水（book）。祝你好運(yùn)！