react native fast trie

реагировать-родной-быстро-попробовать

Быстрая и эффективно использующая память реализация Trie для React Native. Использует HAT-трие Tessel.

• ? Низкое потребление памяти
• ⚡️ Чрезвычайно быстро для создания больших попыток.
• ? Хорошо протестирован на JS и C++.

Установка

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

Тесты

Тесты сравниваются с широко используемой реализацией JS (три-типизированной) на реальных устройствах, созданных в режиме выпуска. Вы можете создать пример проекта на своем устройстве, чтобы воспроизвести эти результаты.

Тесты следующие:

• Одиночный список слов : вставьте все слова из английского словаря bip39 в Trie.
• Пакетная вставка : используйте метод BatchInsert со всем английским массивом bip39 для FastTrie.
• Все списки слов : создайте отдельную таблицу для каждого списка слов bip39 по локали и вставьте в каждый
• Содержит : Доступ к 1 000 000 случайным словам из английского списка слов bip39.
• Найти : найти 1 000 000 подстрок случайных слов из английского списка слов bip39.

Устройство	Одиночный список слов	Пакетная вставка	Все списки слов	Содержит	Находить
Пиксель 5	в 4,64 раза быстрее	В 16,86 раз быстрее	в 7,76 раз быстрее	в 2,94 раза быстрее	В 24,63 раза быстрее
Пиксель 3а	в 3,26 раза быстрее	в 14,67 раз быстрее	в 5,54 раза быстрее	в 3,06 раза быстрее	В 26,23 раза быстрее
Галактика А10е	в 2,94 раза быстрее	в 9,83 раза быстрее	в 4,84 раза быстрее	в 3,95 раза быстрее	в 11,47 раз быстрее
айфон 15 про макс	в 3,78 раза быстрее	в 10,33 раза быстрее	в 5,13 раза быстрее	в 3,43 раза быстрее	В 23,83 раза быстрее
айфон 11 про макс	в 4,65 раза быстрее	В 13,12 раза быстрее	в 5,21 раза быстрее	в 3,35 раза быстрее	В 23,79 раза быстрее
айфон 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 

API

Обзор

FastTrie — это высокопроизводительная реализация Trie, разработанная для приложений React Native. Он предлагает эффективные операции по вставке элементов, проверке их существования и поиску элементов с определенным префиксом. Реализация предоставляет возможности настройки для балансировки между скоростью и использованием памяти.

Тип FastTrieOptions

Этот тип позволяет настраивать экземпляр FastTrie.

• burstThreshold?: number
  Указывает максимальный размер узла хеш-массива до возникновения пакета. Более высокое значение (например, 16 384) рекомендуется для точного поиска, тогда как значение по умолчанию 1024 оптимизировано для префиксного поиска.

• maxLoadFactor?: number
  Определяет коэффициент загрузки дерева. Меньшее значение увеличивает скорость, а большее значение уменьшает использование памяти. Значение по умолчанию — 8,0.

Класс FastTrie

Конструктор

Создает новый экземпляр FastTrie.

• Параметры:

  • options: FastTrieOptions (необязательно)
    Параметры конфигурации для trie. Включает в себя burstThreshold и maxLoadFactor .

• Пример:

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

Методы

insert(item: string): void

Вставляет строку в дерево.

 trie . insert ( 'example' ) ;

batchInsert(items: string[]): void

Вставляет несколько строк в дерево за одну операцию. Этот метод оптимизирован для массовой вставки и более эффективен, чем вставка элементов по отдельности.

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

contains(item: string): boolean

Проверяет, присутствует ли строка в дереве.

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

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

Находит все строки в дереве, начинающиеся с заданного префикса.

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

delete(item: string): void

Удаляет строку, если она существует в дереве

 trie . delete ( 'apple' ) ; 

Содействие

См. руководство по участию, чтобы узнать, как внести свой вклад в репозиторий и рабочий процесс разработки.

Лицензия

Массачусетский технологический институт

---

Сделано с помощью create-react-native-library