DOCSEARCHbyAlgolia
Submit Docs

mnemonist

repository·master·Indexed 25 days ago

https://github.com/yomguithereal/mnemonist

A curated collection of performant, modular, and fully typed data structures for JavaScript and TypeScript. It includes classic structures like Heaps, Tries, and Stacks, as well as specialized options such as Burkhard-Keller trees, Bloom Filters, Suffix Arrays, and bidirectional maps (BiMap). Version 0.40.4.

Tokens
40.8K
Snippets
23
Records
337
Agent score
81%

What's inside mnemonist

  1. Overview of Mnemonist data structures

    master

    Mnemonist is a curated, modular, and fully typed collection of data structures for JavaScript and TypeScript. It is designed to be performant and consistent with standard JavaScript object APIs.

    Available data structures are categorized as follows:

    Classics

    • Heap
    • Linked List
    • LRUCache, LRUMap
    • MultiMap
    • MultiSet
    • Queue
    • Set (helpers)
    • Stack
    • Trie
    • TrieMap

    Low-level & Specific Use Cases

    • Circular Buffer
    • Fixed Deque
    • Fibonacci Heap
    • Fixed Reverse Heap
    • Fixed Stack
    • Hashed Array Tree
    • Static DisjointSet
    • SparseQueueSet
    • SparseMap
    • SparseSet
    • Suffix Array
    • Generalized Suffix Array
    • Vector

    Information Retrieval & NLP

    • Fuzzy Map
    • Fuzzy MultiMap
    • Inverted Index
    • Passjoin Index
    • SymSpell

    Space & Time Indexation

    • Static IntervalTree
    • KD-Tree

    Metric Space Indexation

    • Burkhard-Keller Tree
    • Vantage Point Tree

    Probabilistic & Succinct Data Structures

    • BitSet
    • BitVector
    • Bloom Filter

    Utility Classes

    • BiMap
    • DefaultMap
    • DefaultWeakMap

    Note: This library does not include a Graph data structure. For graph implementations, the maintainers recommend using the graphology library instead.

  2. Simulate low-level memory with TypedArrays

    master

    Since JavaScript does not allow direct control over memory layout, you can simulate a manual memory allocation system (similar to malloc in C) using TypedArrays (e.g., Uint8Array, Uint16Array, Float32Array). This is particularly useful for implementing high-performance data structures like linked lists where you can use indices in a typed array as 'pointers' instead of object references.

    // Using byte arrays to simulate pointers in a linked list
function LinkedList(capacity) {
  this.head = 0;
  this.next = new Uint16Array(capacity);
  this.values = new Array(capacity);
}

// Changing a pointer using an index
this.next[nodeIndex] = otherNodeIndex;

  3. Performance optimization: Minimize hashmap lookups

    master

    In JavaScript, every lookup in a Map or Object has a cost. When implementing data structures, avoid performing multiple lookups for the same key within a single operation. Instead, perform one lookup and check the result for existence.

    Inefficient (2 lookups):

    if (this._nodes.has(node)) throw Error(...);
const data = this._nodes.get(node);

    Efficient (1 lookup):

    const data = this._nodes.get(node);
if (typeof data === 'undefined') throw Error(...);
    // Efficient pattern: One lookup
Graph.prototype.getNodeAttribute = function(node, data) {
  const data = this._nodes.get(node);

  if (typeof data === 'undefined') {
    throw Error(...);
  }

  return data[name];
};

  4. Performance optimization: Avoid costly object allocations

    master

    To maintain high performance in JavaScript, minimize the creation of new objects and functions during hot loops or frequent operations:

    1. Avoid re-creating Regular Expressions: Define regexes as constants outside of functions.
    2. Avoid nesting functions: Creating functions inside other functions (e.g., inside a forEach callback) leads to repeated allocations.
    3. Avoid mixing types in arrays: Keep arrays monomorphic (containing the same type of elements) to help the JIT engine optimize.
    // BAD: Regex created every call
const test = x => /regex/.test(x);

// GOOD: Regex defined once
const REGEX = /regex/;
const test = x => REGEX.test(x);

// BAD: Function created per iteration
function(array) {
  array.forEach(subarray => {
    subarray.forEach(x => console.log(x));
  });
}

  5. Implement well-known JavaScript interfaces for custom structures

    master

    To make your custom data structures feel native to the JavaScript ecosystem, implement standard protocols:

    JSON Serialization

    Implement toJSON() so that JSON.stringify(structure) returns the expected data format.

    Iteration Protocol

    Implement [Symbol.iterator] to allow your structures to be used in for...of loops.

    Node.js Inspection

    Implement inspect (or Symbol.for('nodejs.util.inspect.custom')) to provide a clean, readable representation when using console.log() in Node.js.

    // JSON Serialization
Structure.prototype.toJSON = function() {
  return this.items;
};

// Iteration Protocol
Queue.prototype[Symbol.iterator] = Queue.prototype.values;

// Node.js Inspection
Queue.prototype.inspect = function() {
  return somethingUseful;
};

  7. Access Mnemonist data structures via the unified CommonJS endpoint

    master

    The mnemonist library provides a unified CommonJS entrypoint that exports all available data structures. While modular access (importing specific files) is preferred for better tree-shaking and performance, you can access everything through the main module export.

    Available data structures include heaps, trees, maps, sets, vectors, and specialized structures like Bloom Filters, BK-Trees, and LRU Caches.

  8. Use CritBitTreeMap for efficient string-based key-value storage

    master

    CritBitTreeMap is a JavaScript implementation of a crit-bit tree (also known as a PATRICIA tree). It is a bitwise radix tree designed to be more efficient than a standard Trie for string keys. It provides $O(k)$ performance where $k$ is the length of the key.

    Use it when you need a Map-like structure optimized for string keys, offering efficient insertion, deletion, and lookup.

    Key Methods

    • set(key, value): Sets the value for the given string key. Returns the map instance.
    • get(key): Retrieves the value associated with the key, or undefined if not found.
    • has(key): Returns true if the key exists in the tree, false otherwise.
    • delete(key): Removes the key from the tree. Returns true if the key existed, false otherwise.
    • clear(): Removes all entries from the tree.
    • forEach(callback, scope): Iterates over the tree in key order. The callback receives (value, key).

  9. Available data structures in Mnemonist

    master

    Mnemonist provides a wide variety of specialized data structures. You can import these directly from the main entrypoint. The available structures include:

    Maps and Sets

    • BiMap, InverseMap: Bidirectional mappings.
    • DefaultMap, DefaultWeakMap: Maps with default value providers.
    • FuzzyMap, FuzzyMultiMap: Maps supporting fuzzy matching.
    • MultiMap, MultiSet: Collections that allow multiple values per key or element.
    • SparseMap, SparseSet: Memory-efficient sparse collections.
    • TrieMap: A map implementation based on a Trie.

    Heaps and Priority Queues

    • Heap, MinHeap, MaxHeap: Standard priority queues.
    • FibonacciHeap, MinFibonacciHeap, MaxFibonacciHeap: Heaps using the Fibonacci heap structure.
    • FixedReverseHeap: A heap with a fixed capacity that maintains elements in reverse order.

    Trees and Spatial Structures

    • BKTree: A tree for metric space searching.
    • HashedArrayTree: A tree structure using hashing.
    • KDTree: A k-dimensional tree for spatial partitioning.
    • StaticIntervalTree: A tree for managing static intervals.
    • Trie: A prefix tree.
    • VPTree: A vantage-point tree for metric space searching.

    Buffers, Stacks, and Queues

    • CircularBuffer: A fixed-size buffer that wraps around.
    • FixedDeque, FixedStack: Deques and stacks with fixed capacities.
    • Queue, Stack: Standard queue and stack implementations.
    • LinkedList: A doubly linked list.

    Vectors and Specialized Arrays

    • Vector: A general-purpose dynamic array.
    • Typed Vectors: Uint8Vector, Uint8ClampedVector, Int8Vector, Uint16Vector, Int16Vector, Uint32Vector, Int32Vector, Float32Vector, Float64Vector.
    • PointerVector: A vector optimized for pointer storage.
    • SuffixArray, GeneralizedSuffixArray: Specialized arrays for string processing.

    Other Specialized Structures

    • BitSet, BitVector: Bit-level collections.
    • BloomFilter: A probabilistic data structure for membership testing.
    • InvertedIndex: An index for fast full-text search.
    • LRUCache, LRUCacheWithDelete, LRUMap, LRUMapWithDelete: Least-Recently-Used caching mechanisms.
    • PassjoinIndex: An index for passjoin operations.
    • SymSpell: A structure for symmetric spelling correction.
    • StaticDisjointSet: A disjoint-set (union-find) structure for static sets.

  10. What is a FixedReverseHeap and when to use it

    master

    A FixedReverseHeap is a static heap implementation with a fixed capacity. It is a "reverse" heap because it stores elements in reverse order, allowing the worst item to be replaced in logarithmic time.

    Key Characteristics:

    • Fixed Capacity: You must define the maximum number of items at construction.
    • No Popping: You cannot pop individual items from the heap. Instead, you consume the entire heap at once.
    • Efficiency: It is highly efficient for finding the $n$ smallest or largest items from a larger dataset (e.g., implementing $k$-nearest neighbors).

  11. Use FuzzyMap for approximate key matching

    master

    A FuzzyMap is a specialized map where keys are processed by hash functions before read or write operations. This allows for approximate matching, such as case-insensitive lookups by using a lowercasing function.

    Constructor

    new FuzzyMap(descriptor)

    The descriptor can be:

    1. A function: Used as both the writeHashFunction (for set/add) and the readHashFunction (for get/has).
    2. An array [writeHashFunction, readHashFunction]: Allows different logic for writing keys versus reading them.

    If no function is provided, it defaults to an identity function (returning the key unchanged).

  12. How KDTree works and when to use it

    master

    A KDTree (k-dimensional tree) is a space-partitioning data structure used for organizing points in a $k$-dimensional space. It is highly efficient for multidimensional range searches and nearest neighbor lookups.

    Mental Model

    • Construction: The tree is built by recursively splitting the data along different axes using a median-finding approach (via inplaceQuickSortIndices). This creates a balanced tree.
    • Search: When searching for a neighbor, the algorithm traverses the tree by comparing the query point to the split value at each node. It uses the squared Euclidean distance to avoid expensive square root operations.
    • Complexity:
      • Construction: $O(n \log n)$ where $n$ is the number of points.
      • Nearest Neighbor Search: Average case $O(\log n)$, though worst-case can be higher depending on data distribution.

    When to use

    • Use KDTree when you have a static set of points in low-to-medium dimensional space and need to perform frequent nearest-neighbor queries.
    • Use KDTree.from() for easy integration with standard JavaScript arrays/iterables.
    • Use KDTree.fromAxes() for high-performance scenarios where data is already in typed arrays.