Разработать эффективные а) представление и б) реализации операций вставки, удаления и поиска для двоичных деревьев;

Домашнее задание №2, также как №1, подразумевало исследовательскую составляющую.

В данной работе было разработано кэш-эффективное представление двоичных НЕ сбалансированных деревьев (для сбалансированных смотрите btree). Для этого дерево было разбито на кластеры, которые содержат по C вершин. Вершины внутри кластера выкладывались внутри массива с помощью различных "укладок" BFS/vEB/DFS/INORDER. В результате тестов было выяснено, что порядок vEB позволяет достичь наибольшей скорости для операций вставка/поиск, а размер кластера оптимально брать 63. (см отчёт.pdf)

Операция удаления реализована не была.

Код написан на языке С, для компиляции выполнить:

• qmake Arch2_b.pro
• make

В файле "include.h"

1. Если объявлено

#define USE_CACHE_TEST

То выполняется тестирование "кэш-эффективной" версии, иначе обычной версии бинарных деревьев

2. Если объявлено

#define USE_CLUSTER_SORT

То при вставке в "кэш-эффективной" версии появляется перебалансировка внутри кластера.

#define CACHE_LINE_SIZE 64 

Задает размер кэш-линии (используется в malloc для выравнивания).

#define C_SIZE ((1 << 5)-1) 

Задает размер кластера. Должна быть степенью двойки >= 4 (то что тестировалось).

//#define USE_BFS
#define USE_VEB
//#define USE_DFS
//#define USE_INORDER

Задает используему укладку кластера.

#define USE_ALLOCATOR

Использование самописного простого аллокатора памяти. Иначе используется malloc.

Приложение является консольным, первым параметром принимает путь к файлу с тестами на вставку. Вторым параметром путь к файлу с тестами на поиск. Выводит время, которое потребовалось на выполнение всех операций вставки и поиска.

Формат файла с тестами:

1. В первой строке 64 разрядное беззнаковое число количество пар ключ-значение
2. Во второй и последующий 64 разрядные беззнаковые пары чисел "ключ значение"

Пример входного теста:

2
1 2
3 4

Пример результата работы программы:

Used layout: vEB
C_SIZE: 31
KEYS_SIZE: 15
NEXT_SIZE: 16
EXIST_SIZE: 4
CACHE_MISS on exist = 1
Loading data...
Test: insert cache_tree
time elapsed: 1.66600000000000023e-06
Loading data...
Test: search cache_tree
time elapsed: 1.13400000000000007e-06
No-cache tree alloced memory:  0 GB   3 Mb   0 Kb 880 B
Cache-tree alloced memory:     0 GB  24 Mb   0 Kb 960 B