uzluga.ru
добавить свой файл
Размышление об использовании 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.