As we all know, Javascript does not have a relatively complete data structure library like C++ or Java, and the related system of Js is very scarce, and even does not provideheapSuch a common object.

The good news is that Js provides in es6 Set(WeakSet) and Map(WeakMap), which is a hash table structure that adds a touch of color to its sparse data structure system, but unfortunately, in many older versions of browsers,Set and Map is not supported, and the related polifill Very inefficient compared to native implementations

In order to solve this situation, we developed a Js-sdsl This data structure library currently contains various data structures such as heaps, red-black trees, and hash tables. In the future, we will develop more general data structures to increase its richness

on browser compatibilitywhich is packaged in ES5 syntax and compatible with more than 99% of browsers, including chrome 49

in performancewhich has been shown to exceed npm The most popular data structure library on functional-red-black-tree and denqueand we will further improve its performance in the future, refer to Benchmark

in popularitywe send eslint Submitted a PR to optimize the time it spends on indentation checking, and got eslint organization adoption and $100 sponsorship, which we list in thesponsor listin npm On the Internet, Js-sdsl has obtained more than 30M/month downloads

Perhaps the current achievements are insignificant, but in the future we will continue to build and promote, so that more developers can get in touch with Js-sdsl

Home page:https://js-sdsl.org/

Js bad data structure ecology

In Js, we can use Array.slice or Array.unshift To simulate double-ended queues and double-ended linked lists, but its efficiency is low, see stackoverflow

bad time complexity

Although Array.push is an O(1) implementation,Array.slice and Array.unshift indeed O(n) when the amount of data is large enough, its performance will decrease linearly

poor underlying design

Since Js is a dynamic language, the Array Unlike a static language like C++, which can have an absolutely predefined memory space, consider the following case

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

It can be seen that when we directly modify the length of the array beyond a certain limit, the operation of modifying the array will become very slow

The reason is that when we directly manipulate the data length or insert different types of data into the array Array will be automatically downgraded tohash tableand better than the native Object Slower!

This is very unfriendly to developers, because of the type uncertainty of Js, we also cannot strongly perceive whether the data will become a slow array when writing, resulting in certain performance problems

Lack of some functions

As we all know, Js does not contain related functions such as heap and red-black tree. Consider the following situation

I have a JSON array containing four fields a, b, c, where c is the primary key, and c is different in each position. I want to implement deduplication based on the values ​​of a and b

It would be hard with ES6.Set but easy with Js-sdsl

import { OrderedSet } from 'js-sdsl';
const arr = [{ a: 1, b: 1, c: 1 }];
// 自定义排序函数实现去重
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;
});

solution

In order to solve the above problems, we provide Js-sdsl, alightweight and efficientThe data structure library aims to create a complete Js data structure ecology, improve development efficiency and code performance. Currently we provide the following data structures, and we will make them more abundant in the future

• stack – First-in, last-out stack
• Queue – First in first out queue
• PriorityQueue – Priority queue implemented by the heap
• Vector – Protected arrays cannot be manipulated directly like length attributes like this
• LinkList – Linked list of non-contiguous memory addresses
• Deque – Double-ended queue, the time complexity of inserting elements forward and backward or getting elements by index is O(1)
• OrderedSet – A sorted collection implemented by a red-black tree
• OrderedMap – A sorted dictionary implemented by a red-black tree
• HashSet – refer to ES6 Set polyfill Implemented hash collection
• HashMap – refer to ES6 Set polyfill Implemented hash dictionary