(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

С++ библиотека от Google с контейнерами map и set на B-деревьях

Источник: habrahabr
alizar

Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL). 

Разница в том, что контейнеры в STL реализованы на красно-чёрных деревьях, а аналогичные контейнеры cpp-btree - на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера). 

B-деревья известны как инструмент для работы с дисковой памятью: базами данных и файловой системой. Но те же свойства, которые дают выигрыш там, позволяют эффективнее использовать и оперативную память. Каждый узел красно-чёрного дерева содержит один элемент, требует три указателя плюс по биту информации на элемент для сбалансированности. Для сравнения, контейнеры на B-деревьях хранят несколько элементов на узел, поэтому уменьшают оверхед указателей и экономят значительное количество памяти. 

По тестам, структуры данных на B-деревьях занимают на 50-80% меньше места, по сравнению с красно-чёрными деревьями. В таблице показано среднее количество байт на элемент в контейнерах set/map разного типа. К примеру, стандартный контейнер set<int32_t> создаёт оверхед 16 байт на каждый из множества маленьких элементов, в то время как альтернативный контейнер btree_set<int32_t> создаёт оверхед всего по 1 байту на элемент.

Тип Вставка B-Tree (32-bit) Red-Black (32-bit) B-Tree (64-bit) Red-Black (64-bit)
set<int32_t> sorted 4.19 20.00 4.40 40.00
random 4.90 20.00 5.15 40.00
set<int64_t> sorted 8.39 24.00 8.80 40.00
random 9.96 24.00 10.47 40.00
set<string> sorted 24.57 40.00 33.60 64.00
random 29.49 40.00 40.74 64.00
map<int32_t, void*> sorted 8.39 24.00 8.80 48.00
random 9.96 24.00 10.47 48.00
map<int64_t, void*> sorted 12.60 28.00 13.20 48.00
random 15.16 28.00 15.92 48.00
map<string, void*> sorted 28.67 44.00 38.16 72.00
random 34.49 44.00 46.53 72.00

На некоторых больших контейнерах есть ещё и выигрыш в скорости доступа за счёт более эффективного использования кэша. На графике показано среднее время выполнения вставки, в зависимости от размеров контейнера. 


Специально для "российских друзей" автор библиотеки пояснил, что не подписывал ось Y, потому что конкретное время выполнения операции зависит от используемого оборудования. В данном случае на 10 млн элементов операция занимает 1,6 микросекунды на красно-чёрных деревьях, против 400 наносекунд на B-деревьях. Компьютер Intel Xeon CPU E5-1650 @ 3.20GHz with L1=32K, L2=256K, L3=12M.

Разработчик предупреждает об отличии cpp-btree от стандартных контейнеров: поскольку любые операции вставки и удаления узлов в B-дерево аннулируют существующие итераторы, так что в случае необходимости нужно использовать безопасные версии.

Ссылки по теме


 Распечатать »
 Правила публикации »
  Написать редактору 
 Рекомендовать » Дата публикации: 14.02.2013 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
VideoStudio X9 Pro. Электронный ключ.
TeeChart for .NET Standard Business Edition 2017 single license
Nero 2018 Platinum ESD
NERO 2015 Platinum ESD. Электронный ключ
Kaspersky Internet Security для всех устройств. 2-Device 1 year Base Download Pack
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Безопасность компьютерных сетей и защита информации
Новости ITShop.ru - ПО, книги, документация, курсы обучения
OS Linux для начинающих. Новости + статьи + обзоры + ссылки
Один день системного администратора
Delphi - проблемы и решения
Новые программы для Windows
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Беговая дорожка (1)
Купила беговую дорожку вот здесь https://4gym.com.ua/product/technogym-artis-run Очень классная,...
 
Отличается ли ДрифтКазино от беттинга? (12)
Друзья, давно заметил, что на Дрифте уже несколько месяцев во всю рекламируется и предлагается...
 
Как подключить файлы ost в отлуке (3)
Проблема в следующем . База почты (входящие, исходящие, удаленные, отправленные) и адресная...
 
Как извлечь рисунки из файла Word (47)
Вообще-то есть еще способ - сделать в Word-е Copy рисунка, открыть Microsoft Photo Editor и там:...
 
Аналоги виагры (1)
Если мужчине, по каким либо причинам, не подходит виагра, существуют качественные аналоги...
 
 
 



    
rambler's top100 Rambler's Top100