Автор: Anton Romankov
Big-O нотация описывает сложность алгоритма
В Near сложность алгоритма коррелирует с потреблением газа, поэтому важно понимать для каких операций какая структура данных больше подходит.
O(1) – операция выполняется за константное время вне зависимости от кол-ва элементов O(n) – время выполнения операции растет пропорционально кол-ву элементов O(log n) – время выполнения операции растет логарифмически с количеством элементов
При большом количестве элементов O(log n) будет эффективнее чем O(n), однако O(1) всегда оптимальнее.
В зависимости от задачи, нужно использовать разные коллекции
- Map – когда нам нужна структура типа ключ-значение, к примеру id аккаунта пользователя и его баланс
- Set – когда мы хотим хранить набор уникальных (без дубликатов) данных
- Vector – то же самое что и Set, однако данные могут дублироваться
В near-sdk-res используются следующие структуры
Vector
- Чтение по индексу – O(1)
- Вставка в конец списка – O(1)
- Удаление из конца списка – O(1)
- Поиск через итератор – O(n)
Эта структура данных эффективна, когда нам нужно хранить дублирующиеся значения с доступом к элементам по индексу. Поиск по элементам будет не эффективен.
LookupSet
- Проверка что элемент есть в коллекции – O(1)
- Добавление элемента – O(1)
- Удаление элемента – O(1)
- Поиск через итератор – не реализовано
Эта структура данных подходит, когда нам нужно хранить уникальный набор данных и проверять наличие элемента в коллекции.
UnorderedSet
- Поиск через итератор – O(1)
То же самое что и LookupSet, только с итераторами.
Эта структура подходит, когда нам нужно хранить уникальный набор данных, а также получать значение элемента через итератор.
LookupMap
- Получение элемента по ключу – O(1)
- Добавление элемента – O(1)
- Удаление элемента – O(1)
- Поиск через итератор – не реализовано
Эта структура эффективна, когда нам не нужны итераторы и наши основные операции это чтение и запись по ключу.
UnorderedMap
- Поиск через итератор – O(1)
То же самое что и LookupMap, только с добавлением итератора.
Эту структуру лучше использовать когда нам нужно итерироваться по ключам и значениям и нам нужна возможность очистить данные.
TreeMap
- Получение элемента по ключу – O(log n)
- Добавление элемента – O(log n)
- Удаление элемента – O(log n)
- Поиск через итератор – O(log n)
Эту структуру нужно использовать, когда мы точно знаем какие преимущества получим от AVL-tree
Примеры использования коллекций
Vector Поскольку перебирать элементы будет дорого по газу, в этой структуре нам нужно хранить данные, доступ к которым мы можем получить зная индекс. За пример возьмем стейкинг контракт с разной наградой за каждый день сейкинга. В качестве индекса будет номер дня со старта. Каждый день мы добавляем элемент в коллекцию и нам будет легко и не дорого узнать в какой день бала какая награда. Предполагается что по бизнес логике нас интересует награда за определенный день со старта.
LookupSet Предположим наш контракт хранит список зарегистрированных пользователей, эта структура нам подходит потому что нам дешево добавлять новые аккаунты в коллекцию и проверять, зарегистрирован пользователь или нет.
UnorderedSet Наш контракт позволяет работать только с разрешенными токенами. Мы можем изменять этот список или вывести все разрешенные токены.
LookupMap Контракт без итерации по ключам, поэтому по бизнес логике мы должны знать ключ заранее. Как пример это может быть контракт, который хранит баланс по id пользователя.
UnorderedMap Представим контракт, который создан для игрушки, в которой пользователи 1 раз в день получают награду за убитых врагов. В структуре в качестве ключа будет идентификатор пользователя а в качестве значения убитые враги. Во первых благодаря итераторам, мы можем пройтись по всем пользователям и определить победителя, во вторых мы можем очистить коллекцию в конце игрового дня и также нам дешево будет по id пользователя инкрементировать значение.
TreeMap Наш контракт будет реализовать Orderbook, приказы на покупку и продажу будем хранить в TreeMap, поскольку ключи находятся в отсортированном виде, мы быстро сможем получить несколько лучших по цене приказов на покупку или продажу.