tgoop.com/golang_lib/481
Create:
Last Update:
Last Update:
SIMD Binary Search Tree
Этот проект представляет собой бинарное дерево поиска, реализованное с использованием SIMD-инструкций (SSE/AVX/AVX512).
Обычно бинарный поиск требует log₂(n) сравнений. Однако с SIMD можно сравнивать сразу несколько элементов за один проход, значительно снижая число итераций. Это приближает бинарный поиск к константному времени для малых массивов.
Особенности
* Однопроходный бинарный поиск с SIMD.
* Поддержка SSE, AVX2 и AVX512.
* Дерево хранится как массив (без указателей).
* Отложенная перестройка дерева (lazy rebuilding).
* Поддержка поиска и вставки.
* Поддержка произвольных типов через шаблоны C++.
* Совместимость с std::lower_bound / std::upper_bound.
Пример использования
#include "simd_binary_search_tree.hpp"
simd_tree::Tree<int> tree;
tree.insert(10);
tree.insert(5);
tree.insert(15);
auto result = tree.lower_bound(9); // -> 10
Производительность
Проект демонстрирует прирост производительности по сравнению со стандартными алгоритмами STL при поиске в небольших отсортированных массивах, особенно на AVX512.
Структура
*
Tree<T> — основной шаблонный класс.*
insert(T) — вставка элемента.*
lower_bound(T) — найти первое значение не меньше заданного.*
upper_bound(T) — найти первое значение больше заданного.https://clement-jean.github.io/simd_binary_search_tree/
👉 @golang_lib
BY Библиотека Go (Golang) разработчика
Share with your friend now:
tgoop.com/golang_lib/481