Размышление об использовании Treap 
при работе с неравномерно распределенными данными.
Веретенников Александр Борисович
Уральский государственный университет им. А. М. Горького
abvmt2@mail.ru, abvmt@e1.ru
http://cs.usu.edu.ru/home/abv/

	Treap – комбинация бинарного дерева и бинарной кучи. Как описано в [1-6], в каждом узле бинарного дерева хранится ключ и приоритет. При этом для текущего узла выполняется следующее условие для ключей: все ключи на узлах его левого поддерева меньше его ключа, а все ключи в правом поддереве больше. Для приоритетов выполняется следующее условие: все приоритеты дочерних узлов больше или равны приоритета текущего узла.
	Как правило приоритеты берутся случайным образом. Однако, в силу организации дерева, оно обладает важным свойством: если мы зададим приоритет для добавляемого ключа значительно меньше, чем для других ключей, то данный ключ скорее всего попадет ближе других ключей к началу дерева, т. е. расстояние от корня до соответствующего узла будет меньше. Это свойство автор исследует в данной работе. За счет установки нужных приоритетов попробуем добиться ускорения скорости поиска в дереве.
	В качестве данных для эксперимента был взят набор естественных текстов. Как известно, слова в обычных языках, таких как русский, имеют определенное распределение по частоте, проще говоря некоторые слова встречаются гораздо чаще других.
	Будем добавлять в дерево пару (слово, – частота слова). Минус добавляем перед частотой, чтобы наиболее часто встречающиеся слова попадали в начало дерева, и следовательно, их поиск в дереве был бы быстрее.

Структура эксперимента

1.	Этап подготовки данных. Читаем заданный объем текстов, в результате получаем массив Words – список слов, без повторений, и массив Counts – в котором для каждого слова из Words сохранено количество его вхождений в текстах. Слова в Words хранятся в соответствие с тем порядком, в каком они находились в текстах. Также получаем массив слов WordsList, в котором сохраняются все слова, с учетом повторов, в том же порядке, в котором они встретились в текстах.
2.	Анализ времени поиска, используя std::set. Используем std::set и добавляем в него все слова из Words. После чего измеряем время поиска всех прочитанных слов, хранящихся в WordsList, в std::set. Указанный здесь std::set – представляет собой стандартную реализацию сбалансированных красно-черных деревьев [8, 9] из библиотеки STL.
3.	Анализ времени поиска, используя АВЛ дерево [7]. Используем АВЛ дерево и добавляем в него все слова из Words. После чего измеряем время поиска всех прочитанных слов, хранящихся в WordsList, в АВЛ дереве.
4.	Анализ времени поиска, используя Treap. Используем Treap и добавляем в него все слова из Words с соответствующими приоритетами, равными (– частота слова), где частота слова берется из Counts. После чего замеряем время поиска всех прочитанных слов, хранящихся в WordsList, в Treap.
5.	Анализ времени поиска, используя Treap с обратными приоритетами. Используем Treap и добавляем в него все слова из Words с приоритетами равными (+ частота слова), где частота слова берется из Counts. В этом случае часто используемые слова должны быть дальше от корня дерева. После чего замеряем время поиска всех прочитанных слов, хранящихся в WordsList, в Treap.

Эксперименты проводились на следующей конфигурации:

Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш: L1  Data – 2 x 32 кб, L1 inst. 2 x 32 кб, L2 - 4096 кб.
Оперативная память: 8 гб, DDR2 800.
FSB 1066 MHz.
Операционная система: Microsoft Windows 2008 Enterprise x64 Edition with Service Pack 1.
Для компиляции использовался компилятор из Microsoft Visual Studio 2008.

Результаты экспериментов

	Были проведены 9 экспериментов с разным объемом входных данных.
	В следующей таблице приведено количество слов

Объем текста, в Мб.	Количество уникальных слов,
совпадает с количеством слов хранящихся в Words	Общее количество слов, совпадает с количеством слов хранящихся в WordsList	
100	811710	14218727	
200	1610031	27706305	
300	2207889	41936384	
400	2574429	56973792	
500	2923163	71983804	
600	3468259	86202744	
700	3743113	101805293	
800	4337975	116014332	
900	4771604	130286820	

	Далее приведено время поиска

Объем текста, в Мб.	Время поиска всех слов из WordsList используя std::set, в секундах.	Время поиска всех слов из WordsList используя АВЛ дерево, в секундах	Время поиска всех слов из WordsList используя Treap, в секундах.	Время поиска всех слов из WordsList используя Treap с обратными приоритетами,  в секундах.	
100	16.668	11.210	9.346	25.614	
200	35.059	23.860	19.111	53.347	
300	56.835	37.998	30.016	86.444	
400	79.977	52.632	40.912	122.557	
500	103.022	67.372	51.872	158.209	
600	125.785	83.894	64.581	192.772	
700	151.133	100.919	74.585	232.377	
800	172.812	113.487	82.792	262.363	
900	196.782	128.082	93.559	299.449	

	Далее даны дополнительные характеристики АВЛ дерева и Treap в каждом случае

Объем текста, в мегабайтах	Высота АВЛ дерева	Высота
Treap	Высота Treap с обратными приоритетами	
100	24	68	69	
200	25	66	224	
300	26	69	225	
400	26	590	582	
500	26	590	582	
600	26	588	582	
700	26	588	581	
800	27	588	586	
900	27	588	586	
	
	Рассмотрим Treap в случае, когда узлы с часто встречающимися ключами располагаются в начале дерева. В этом случае результаты экспериментов показывают значительное превосходство по скорости поиска в Treap, по сравнению с поиском в сбалансированном дереве. Treap в данном случае быстрее std::set примерно в два раза, и быстрее АВЛ дерева примерно на 25 %.
	При этом видно, что если мы назначаем обратные приоритеты, тем самым помещая узлы с часто встречающимися узлами дальше от начала дерева – мы естественно получаем значительное замедление поиска.
	Обратите внимание на интересную динамику высоты Treap, приведенную во второй таблице. Как известно, отсутствие гарантии сбалансированности дерева является основным недостатком Treap. Особенно интересен скачек от 69 до 590, который виден во второй колонке. Тем не менее, данные из второй таблицы говорят о том, что данное изменение высоты дерева не повлияло существенно на скорость поиска. Судя по всему, в нижней части дерева оказались те ключи, которые очень редко встречаются.
	Программа, использующаяся для описанных экспериментов, была скомпилирована под 32-битную архитектуру. Автор провел аналогичные эксперименты для 64-битной архитектуры. Полученные результаты аналогичны случаю 32-битной архитектуры.

Одновременная вставка и поиск

	Эксперимент заключается во вставке всех элементов списка WordsList вначале в std::set, затем в АВЛ дерево, затем в Treap. В каждом случае замеряется время.
	Вставка в дерево, std::set, АВЛ или Treap, в каждом случае включает в себя два этапа: во первых мы ищем элемент в дереве, во вторых, если мы не нашли его, мы добавляем новый элемент в дерево.
	По сути, поскольку в нашем случае количество уникальных слов гораздо меньше, чем всех слов, следует ожидать, что суммарное время вставки всех слов из WordsList  в дерево, примерно совпадает с указанным выше временем поиска в дереве, по крайней мере для std::set и АВЛ дерева.
	Следует отметить следующий факт: когда мы добавляем слово в std::set или АВЛ дерево, если такое слово там уже есть, то дерево не изменяется.

	Вставка элемента в Treap обычно заключается в следующем
1)	Вставка элемента как в обычное бинарное дерево.
2)	Корректировка приоритетов, при необходимости за счет правых или левых поворотов элемент всплывает вверх по дереву.

	При добавлении элемента в Treap автор данной работы поступил несколько необычным образом. Добавляем каждое слово в Treap с приоритетом (– 1).  Если слова не было в Treap – то оно как обычно добавляется в Treap. Если же мы находим слово в Treap – то мы уменьшаем на единицу приоритет соответствующего узла. После этого, мы при необходимости поднимаем узел вверх путем левых или правых поворотов (в случае, если приоритет узла оказался меньше чем у родительского узла).

Объем текста, в Мб.	Время вставки всех слов из WordsList используя std::set, в секундах.	Время вставки всех слов из WordsList используя АВЛ дерево, в секундах	Время вставки всех слов из WordsList используя Treap, в секундах.	
100	14.404	12.824	8.459	
200	31.117	27.078	17.893	
300	49.581	42.849	27.761	
400	70.068	59.661	37.956	
500	90.452	76.570	47.642	
600	110.812	93.391	57.741	
700	133.409	111.624	68.438	
800	154.805	131.080	80.065	
900	176.227	145.536	91.142	

	Проведенные эксперименты также показывают преимущество Treap, как и эксперименты поиска. Но, следует отметить важный факт, в данном случае конечные приоритеты (частоты слов) нам заранее неизвестны. Однако, что весьма важно, часто встречающиеся слова автоматически поднимаются вверх по дереву.
	Следует сказать, что хотя автор в данной работе исследует в основном поиск и вставку слов, однако сделанные выводы должны быть справедливы и для данных произвольной природы.

Литература

1.	Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees", Foundations of Computer Science, 30th Annual Symposium on: 540-545.
2.	Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees", Algorithmica 16 (4/5): pp. 464-497.
3.	Vuillemin, Jean (1980), "A unifying look at data structures", Commun. ACM (New York, NY, USA: ACM) 23 (4): 229–239.
4.	Blelloch, Guy E.,; Reid-Miller, Margaret, (1998), "Fast set operations using treaps", SPAA '98: Proc. 10th ACM Symp. Parallel Algorithms and Architectures, New York, NY, USA: ACM, pp. 16–26.
5.	Naor, M.; Nissim, K. (April 2000), "Certificate revocation and certificate update", IEEE Journal on Selected Areas in Communications 18 (4): 561–570.
6.	Martinez, Conrado; Roura, Salvador (1998), "Randomized binary search trees", Journal of the ACM 45 (2): 288–323.
7.	Адельсон-Вельский Г. М., Ландис Е. М. (1962). Один алгоритм организации информации. Докл. АН. СССР, 146, с. 263-266.
8.	Rudolf Bayer (1972), Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms, Acta Informatica (1): 290-306.
9.	Leo J. Guibas and Robert Sedgewick (1978), A Dichromatic Framework for Balanced Trees, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pp. 8-21. IEEE Computer Society.
10.	J. W. J. Williams. Algorithm 232 - Heapsort, 1964, Communications of the ACM 7(6): 347–348.