Js-sdslJavascript 標準數(shù)據(jù)結構庫
眾所周知，Javascript 并不像 C++ 或者 Java 這些語言一樣擁有較為完善的數(shù)據(jù)結構庫，Js 的相關體系十分匱乏，甚至不提供堆這樣的常見對象。
好消息是，Js 在 es6 中提供了 Set(WeakSet) 和 Map(WeakMap)，這是一種哈希表結構，為其匱乏的數(shù)據(jù)結構體系增添了一絲色彩，但不幸的是，在許多老版本的瀏覽器中，Set 和 Map 不被支持，并且相關的 polifill 相較于原生實現(xiàn)十分低效
為了解決這種局面，我們以 C++ STL 為參考開發(fā)了 Js-sdsl 這一數(shù)據(jù)結構庫，目前包含堆、紅黑樹、哈希表等多種數(shù)據(jù)結構，在未來，我們會開發(fā)更多的通用數(shù)據(jù)結構來增加其豐富性
在瀏覽器兼容上，其采用 ES5 語法打包，兼容 99% 以上的瀏覽器，包括 chrome 49
在性能上，其已被證明超越了 npm 上最流行的數(shù)據(jù)結構庫 functional-red-black-tree 和 denque，并且未來我們會進一步提高其性能，參考 Benchmark
在流行性上，我們向 eslint 提交了 PR 來優(yōu)化其在縮進檢查所消耗的時間，并得到了 eslint 組織的采納以及 100 美元的贊助，我們將其列舉在了贊助者名單中；在 npm 上，Js-sdsl 已經獲得了超過 30M/month 的下載量
或許現(xiàn)在的成就微不足道，但未來我們會持續(xù)建設和推廣，讓更多的開發(fā)者接觸到 Js-sdsl
Js 糟糕的數(shù)據(jù)結構生態(tài)
在 Js 中，我們可以使用 Array.slice 或 Array.unshift 來模擬雙端隊列和雙端鏈表，但是其效率是低下的，參見 stackoverflow
糟糕的時間復雜度
雖然 Array.push 是 O(1) 實現(xiàn)，Array.slice 和 Array.unshift 確是 O(n) 的，當數(shù)據(jù)量足夠大的時候其性能會呈線性下降
糟糕的底層設計
由于 Js 是一門動態(tài)語言，其中的 Array 并不像 C++ 這種靜態(tài)語言一樣，可以擁有絕對預定義的內存空間，考慮下面這個案例
console.time('test-js-array');
const num = 1024 * 1024 * 6;
const arr = new Array(num);
for (let i = 0; i < num; ++i) arr[i] = i;
console.timeEnd('test-js-array');
// test-js-array: 11.60986328125 ms
console.time('test-js-array');
const num = 1024 * 1024 * 6;
const arr = new Array(num);
arr[arr.length + num] = 1;
for (let i = 0; i < num; ++i) arr[i] = i;
console.timeEnd('test-js-array');
// test-js-array: 619.56884765625 ms
console.time('test-js-array');
const num = 1024 * 1024 * 6;
const arr = {};
arr[arr.length + num] = 1;
for (let i = 0; i < num; ++i) arr[i] = i;
console.timeEnd('test-js-array');
// test-js-array: 81.559814453125 ms
可以看到，當我們直接修改數(shù)組的長度超過一定限度時，修改數(shù)組的操作會變得非常慢
其原因是當我們直接操控數(shù)據(jù)長度或往數(shù)組中插入不同類型的數(shù)據(jù)后 Array 會自動降級為哈希表，并且比原生的 Object 更慢！
這對于開發(fā)者來說十分不友好，因為 Js 的類型不確定性，我們同樣無法在編寫時強感知數(shù)據(jù)是否會變?yōu)槁龜?shù)組，導致出現(xiàn)一定的性能問題
部分功能的缺乏
眾所周知，Js 中不含有堆和紅黑樹等相關功能，考慮以下情形
我有一個 JSON 數(shù)組，包含四個字段 a、b、c，其中 c 是主鍵，每個位置的 c 都不一樣，我想根據(jù) a、b 的值實現(xiàn)去重
使用 ES6.Set 會很困難，但使用 Js-sdsl 會很容易
import { OrderedSet } from 'js-sdsl';
const arr = [{ a: 1, b: 1, c: 1 }];
// 自定義排序函數(shù)實現(xiàn)去重
const st = new OrderedSet(arr, (x, y) => {
if (x.a !== y.a) return x.a - y.a;
if (x.b !== y.b) return x.b - y.b;
return 0;
});
解決方案
為了解決上述的問題，我們提供了 Js-sdsl，一個輕量且高效的數(shù)據(jù)結構庫，旨在打造完整的 Js 數(shù)據(jù)結構生態(tài)，提高開發(fā)效率以及代碼性能，目前我們提供以下數(shù)據(jù)結構，未來我們會使其變得更加豐富
- Stack - 先進后出的堆棧
- Queue - 先進先出的隊列
- PriorityQueue - 堆實現(xiàn)的優(yōu)先級隊列
- Vector - 受保護的數(shù)組，不能直接操作像
length這樣的屬性 - LinkList - 非連續(xù)內存地址的鏈表
- Deque - 雙端隊列，向前和向后插入元素或按索引獲取元素的時間復雜度為 O(1)
- OrderedSet - 由紅黑樹實現(xiàn)的排序集合
- OrderedMap - 由紅黑樹實現(xiàn)的排序字典
- HashSet - 參考 ES6 Set polyfill 實現(xiàn)的哈希集合
- HashMap - 參考 ES6 Set polyfill 實現(xiàn)的哈希字典