Разработать эффективные а) представление и б) реализации операций вставки, удаления и поиска для двоичных деревьев;
Домашнее задание №2, также как №1, подразумевало исследовательскую составляющую.
В данной работе было разработано кэш-эффективное представление двоичных НЕ сбалансированных деревьев (для сбалансированных смотрите btree). Для этого дерево было разбито на кластеры, которые содержат по C вершин. Вершины внутри кластера выкладывались внутри массива с помощью различных "укладок" BFS/vEB/DFS/INORDER. В результате тестов было выяснено, что порядок vEB позволяет достичь наибольшей скорости для операций вставка/поиск, а размер кластера оптимально брать 63. (см отчёт.pdf)
Операция удаления реализована не была.
Код написан на языке С, для компиляции выполнить:
- qmake Arch2_b.pro
- make
В файле "include.h"
- Если объявлено
#define USE_CACHE_TEST
То выполняется тестирование "кэш-эффективной" версии, иначе обычной версии бинарных деревьев
- Если объявлено
#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.
Приложение является консольным, первым параметром принимает путь к файлу с тестами на вставку. Вторым параметром путь к файлу с тестами на поиск. Выводит время, которое потребовалось на выполнение всех операций вставки и поиска.
Формат файла с тестами:
- В первой строке 64 разрядное беззнаковое число количество пар ключ-значение
- Во второй и последующий 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