react-native-fast-trie

A fast, memory-efficient Trie implementation for React Native. Uses Tessel's HAT-trie.

• 💾 Low memory footprint
• ⚡️ Extremely fast for contructing large tries
• 🧪 Well tested in JS and C++

Installation

npm install react-native-fast-trie
yarn add react-native-fast-trie

Benchmarks

Benchmarks are taken compared to a commonly-used JS implementation (trie-typed) on real devices built in release mode. You can build the example project on your device to reproduce these results.

Tests are as follows:

• Single Wordlist: Insert all the words in the english bip39 dictionary into a Trie
• Batch Insert: Use the batchInsert method with the entire english bip39 array for FastTrie
• All Wordlists: Create a separate trie for each bip39 wordlist by locale and insert into each
• Contains: Access 1,000,000 random words from the english bip39 wordlist
• Find: Find 1,000,000 substrings of random words from the english bip39 wordlist

Screenshots of these benchmarks can be found in the benchmarks folder.

Usage

// index.js
import { FastTrie } from 'react-native-fast-trie';

const trie = new FastTrie();
console.log(trie.contains('test')); // false

trie.insert('test');
console.log(trie.contains('test')); // true
console.log(trie.find('te')); // ['test']

trie.batchInsert(['test2', 'test3']);

// Limit to only 2 results
console.log(trie.find('te', 2)); // ['test2', 'test3']

trie.delete('test2');

console.log(trie.contains('test2')); // false

API

Overview

FastTrie is a high-performance trie implementation designed for React Native applications. It offers efficient operations for inserting elements, checking for their existence, and finding elements with a specific prefix. The implementation provides customization options to balance between speed and memory usage.

FastTrieOptions Type

This type allows configuration of the FastTrie instance.

• burstThreshold?: number
  Specifies the maximum size of an array hash node before a burst occurs. A higher value (e.g., 16,384) is recommended for exact searches, while the default value of 1024 is optimized for prefix searches.

• maxLoadFactor?: number
  Determines the load factor of the trie. A lower value increases speed, while a higher value decreases memory usage. The default value is 8.0.

FastTrie Class

Constructor

Creates a new instance of FastTrie.

• Parameters:

  • options: FastTrieOptions (optional)
    Configuration options for the trie. Includes burstThreshold and maxLoadFactor.

• Example:

  const trie = new FastTrie({ burstThreshold: 2048, maxLoadFactor: 10.0 });
  

Methods

insert(item: string): void

Inserts a string into the trie.

trie.insert('example');

batchInsert(items: string[]): void

Inserts multiple strings into the trie in a single operation. This method is optimized for bulk insertions and is more efficient than inserting items individually.

trie.batchInsert(['apple', 'apricot', 'banana']);

contains(item: string): boolean

Checks if a string is present in the trie.

const isPresent = trie.contains('example');

find(prefix: string, maxResults?: number): boolean

Finds all strings in the trie that start with the given prefix.

const results = trie.find('ex', 10);

delete(item: string): void

Deletes a string if it exists in the trie

trie.delete('apple');

Contributing

See the contributing guide to learn how to contribute to the repository and the development workflow.

License

MIT

Made with create-react-native-library