(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
TeeBI for RAD Studio Suite with source code single license
Allround Automation Direct Oracle Access Standard license
go1984 Enterprise
Allround Automation PL/SQL Developer - Annual Service Contract - Unlimited
FastCube.Net Standard Edition Single License
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Безопасность компьютерных сетей и защита информации
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
OS Linux для начинающих. Новости + статьи + обзоры + ссылки
Один день системного администратора
Программирование на Visual С++
Все о PHP и даже больше
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Как извлечь рисунки из файла Word (42)
Вообще-то есть еще способ - сделать в Word-е Copy рисунка, открыть Microsoft Photo Editor и там:...
 
Сдача экзаменов Microsoft гарантия 100% (13)
Сдача экзаменов Microsoft гарантия 100%. Дополнительная информация по E-mail.
 
Подключение JavaScript (305)
Всем привет! Я подключаю JavaScript нижеприведенным образом. Код: <script...
 
Как восстановить рабочий стол? Помогите срочно надо! (3)
Windows 7 максимальная. В учетной записи сменила пароль и выключила комп, после включения...
 
Пять возможностей Windows, о которых вы могли не знать (5)
пыщпыщ
 
 
 



    
rambler's top100 Rambler's Top100