(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
ABBYY Lingvo x6 Многоязычная Домашняя версия, электронный ключ
Allround Automation PL/SQL Developer Single user license
Kaspersky Endpoint Security для бизнеса – Стандартный Russian Edition. 10-14 Node 1 year Base License
Quest Software. TOAD for SQL Server Xpert Edition
Zend Guard 1 Year Subscription
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Безопасность компьютерных сетей и защита информации
Новости ITShop.ru - ПО, книги, документация, курсы обучения
OS Linux для начинающих. Новости + статьи + обзоры + ссылки
Новые материалы
Один день системного администратора
Компьютерная библиотека: книги, статьи, полезные ссылки
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Как выводить деньги в лучших казино? (6)
Порой игрок казино из рейтинга 2021 https://casino2021.net/ все сделал точно, заявка на вывод...
 
Отличается ли ДрифтКазино от беттинга? (31)
Друзья, давно заметил, что на Дрифте уже несколько месяцев во всю рекламируется и предлагается...
 
Автомобиль (5)
Доброй ночи. Планируем приобрести авто, рассматриваем б.у варианты, как проще всего подобрать...
 
Помощь по MS Access (341)
Доброе время суток. Случайно оказался на этом сайте, искал статьи по OLAP. Вижу, что...
 
Актуальное зеркало БК Марафон на сегодня (1)
На основном сайте БК Марафон https://rabochee-zerkalo-marafon.ru/ зеркало доступно прямо в...
 
 
 



    
rambler's top100 Rambler's Top100