alexbers Jul 21 2014 at 09:15

Списки с пропусками: вероятностная альтернатива сбалансированным деревьям

13 min

33K

Algorithms *Mathematics *

Translation

+61

Comments 9

mbait Jul 21 2014 at 09:28

datacompboy Jul 21 2014 at 10:21

Не сказал бы я, что они сильно лучше по простоте кода.
Представить себе корректный lock-free алгоритм вообще невозможно.
Представить себе корректный иммутабельный список тоже сложно.

cheremin Jul 21 2014 at 11:27

>Представить себе корректный lock-free алгоритм вообще невозможно.

j.u.c.ConcurrentSkipListMap?

alexbers Jul 21 2014 at 11:27

Описание Lock-free алгоритмов для списков с пропусками можно найти здесь: http://www.cse.yorku.ca/~ruppert/Mikhail.pdf. Лучше начинать сразу с 61-ой страницы.

datacompboy Jul 21 2014 at 14:37

Спасибо, с такой точки зрения смог представить. Правда, накладные расходы на insert & delete вообще неприятные.

noxwell Jul 21 2014 at 10:42

Мне кажется, или декартово дерево по явному ключу пишется проще, чем эта структура и не уступает по производительности, так как приоритеты выбираются случайно? Интересно было бы сравнить их производительность.

wataru Jul 21 2014 at 14:14

Декартово дерево требует больше памяти (обязательно по 2 указателя на элемент + сгенерированный случайно ключ для кучи).

alexbers Jul 21 2014 at 20:12

Сравнение производительности есть на страницах 67-75 http://www.cepis.org/upgrade/files/full-2004-V.pdf.

Мне тоже стало интересно сравнить производительность этих двух структур. Собрал libdict, сгенерировал 1 000 000 случайных 10 символьных строк, использующихся в качестве ключей, и запустил бенчмарк, входящий в комплекте.

К несчастью для скип-листов, декартово дерево их задоминировало: итоговое время теста стабильно отличалось в 6 раз: 52.2 сек. против 8.5 сек.

Результаты

$ ./benchmark t r.txt
tr container: 0.07kB
tr memory: 48000.07kB
tr insert: 2.232 s ( 25372871 cmp, 0 hash)
insert rotations: 1998984
tr fwd iterate: 0.142 s
tr rev iterate: 0.140 s
tr good search: 2.126 s ( 26510930 cmp, 0 hash)
search rotations: 0
tr bad search: 2.163 s ( 26759480 cmp, 0 hash)
tr remove: 1.698 s ( 23816179 cmp, 0 hash)
remove rotations: 998611
tr total: 8.503 s (102459460 cmp, 0 hash)
total rotations: 2997595

$ ./benchmark S r.txt
sk container: 0.19kB
sk memory: 47992.38kB
sk insert: 7.793 s (265126074 cmp, 0 hash)
sk fwd iterate: 0.093 s
sk rev iterate: 0.092 s
sk good search: 18.019 s (512545083 cmp, 0 hash)
sk bad search: 18.166 s (516927720 cmp, 0 hash)
sk remove: 8.070 s (272280836 cmp, 0 hash)
sk total: 52.234 s (1566879713 cmp, 0 hash)

Всех победило красно-чёрное дерево с общим временем 5.446 сек.

Спасибо за комментарий, узнал про ещё одну хорошую структуру данных.

alexbers Jul 21 2014 at 20:32

Внимательный анализ кода libdict'a показал, что авторы используют p=1/2. Замена p на 1/4 ускорила код с 52.2 сек. до 9.6 сек. Потребление памяти сократилось с 47992kB до 42666kB.

Строчка
unsigned count = __builtin_ctz( r ) + 1;

Была заменена на:
unsigned count = __builtin_ctz( r )/2 + 1;

Новые результаты

$ bin/benchmark S bin/r.txt
sk container: 0.19kB
sk memory: 42666.86kB
sk insert: 2.265 s ( 35900850 cmp, 0 hash)
sk fwd iterate: 0.091 s
sk rev iterate: 0.089 s
sk good search: 2.501 s ( 37698480 cmp, 0 hash)
sk bad search: 2.591 s ( 37965496 cmp, 0 hash)
sk remove: 2.104 s ( 36015791 cmp, 0 hash)
sk total: 9.641 s (147580617 cmp, 0 hash)

Пошлю-ка я им пул-реквест.