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

Device	Single Wordlist	Batch Insert	All Wordlists	Contains	Find
Pixel 5	4.64x faster	16.86x faster	7.76x faster	2.94x faster	24.63x faster
Pixel 3a	3.26x faster	14.67x faster	5.54x faster	3.06x faster	26.23x faster
Galaxy A10e	2.94x faster	9.83x faster	4.84x faster	3.95x faster	11.47x faster
iPhone 15 Pro Max	3.78x faster	10.33x faster	5.13x faster	3.43x faster	23.83x faster
iPhone 11 Pro Max	4.65x faster	13.12x faster	5.21x faster	3.35x faster	23.79x faster
iPhone 7	3.58x faster	12.03x faster	5.65x faster	3.46x faster	26.86x faster

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