react native fast trie

反应本机快速特里

React Native 的快速、内存高效的 Trie 实现。使用 Tessel 的 HAT-trie。

• ？内存占用低
• ⚡️ 构建大型尝试的速度非常快
• ？在 JS 和 C++ 中经过良好测试

安装

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

基准测试

基准测试是与在发布模式下构建的真实设备上常用的 JS 实现（trie 类型）进行比较。您可以在您的设备上构建示例项目来重现这些结果。

测试如下：

• Single Wordlist ：将英语 bip39 词典中的所有单词插入 Trie 中
• 批量插入：将batchInsert方法与FastTrie的整个英语bip39数组一起使用
• 所有单词列表：按区域设置为每个 bip39 单词列表创建一个单独的 trie 并插入到每个单词列表中
• 包含：从英语 bip39 单词列表中访问 1,000,000 个随机单词
• 查找：从英语 bip39 单词列表中查找 1,000,000 个随机单词的子串

设备	单个单词表	批量插入	所有单词表	包含	寻找
像素5	速度提高 4.64 倍	速度提高 16.86 倍	速度提高 7.76 倍	速度提高 2.94 倍	速度提高 24.63 倍
像素3a	速度提高 3.26 倍	速度提高 14.67 倍	速度提高 5.54 倍	速度提高 3.06 倍	速度提高 26.23 倍
银河A10e	速度提高 2.94 倍	速度提高 9.83 倍	速度提高 4.84 倍	速度提高 3.95 倍	速度提高 11.47 倍
iPhone 15 Pro 最大	速度提高 3.78 倍	速度提高 10.33 倍	速度提高 5.13 倍	速度提高 3.43 倍	速度提高 23.83 倍
iPhone 11 Pro 最大	速度提高 4.65 倍	速度提高 13.12 倍	速度提高 5.21 倍	速度提高 3.35 倍	速度提高 23.79 倍
iPhone 7	速度提高 3.58 倍	速度提高 12.03 倍	速度提高 5.65 倍	速度提高 3.46 倍	速度提高 26.86 倍

这些基准测试的屏幕截图可以在基准测试文件夹中找到。

用法

 // 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 

应用程序编程接口

概述

FastTrie 是专为 React Native 应用程序设计的高性能 trie 实现。它提供了插入元素、检查元素是否存在以及查找具有特定前缀的元素的高效操作。该实现提供了自定义选项来平衡速度和内存使用量。

FastTrieOptions类型

该类型允许配置 FastTrie 实例。

• burstThreshold?: number
  指定突发发生前数组哈希节点的最大大小。建议使用较高的值（例如 16,384）进行精确搜索，而默认值 1024 则针对前缀搜索进行优化。

• maxLoadFactor?: number
  确定 trie 的负载因子。较低的值会提高速度，而较高的值会减少内存使用量。默认值为 8.0。

FastTrie类

构造函数

创建 FastTrie 的新实例。

• 参数：

  • options: FastTrieOptions （可选）
    trie 的配置选项。包括burstThreshold和maxLoadFactor 。

• 例子：

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

方法

insert(item: string): void

将字符串插入到 trie 中。

 trie . insert ( 'example' ) ;

batchInsert(items: string[]): void

通过一次操作将多个字符串插入到 trie 中。此方法针对批量插入进行了优化，并且比单独插入项目更有效。

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

contains(item: string): boolean

检查 trie 中是否存在字符串。

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

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

查找 trie 中以给定前缀开头的所有字符串。

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

delete(item: string): void

如果字符串存在于 trie 中，则删除该字符串

 trie . delete ( 'apple' ) ; 

贡献

请参阅贡献指南，了解如何为存储库和开发工作流程做出贡献。

执照

麻省理工学院

---

使用 create-react-native-library 制作