Comments 39
UFO just landed and posted this here
действительно хорошая статья
Ух ты, впервые о таком слышу. Спасибо большое за информацию, может пригодиться.
Хотелось бы увидеть реальные тесты скорости работы данного алгоритма и привычных методов, которые работают за O(log(N)). Действительно, O(LOG(LOG(N))) не намного лучше чем просто O(LOG(N)) при больших N, и тут важен константный множитель, который не учитывается оператором О.
Например, скорость вставки/поиска в массив данных размером 0,1 млн, 1млн, 10млн, 100млн и объем использованной памяти
Например, скорость вставки/поиска в массив данных размером 0,1 млн, 1млн, 10млн, 100млн и объем использованной памяти
Если я правильно понял, то в данном случае N*log(N) надо сравнивать не с N*log(log(N)), а с N*log(log(U)), где log(U) — это количество бит в числах.
Т.е. для 32х разрядных чисел это будет просто N*5 для любого числа элементов (правда, потребление памяти будет эпичнейшим, ну да не суть).
Т.е. для 32х разрядных чисел это будет просто N*5 для любого числа элементов (правда, потребление памяти будет эпичнейшим, ну да не суть).
Да, вы абсолютно правы. Но тесты все-равно хотелось бы увидеть что бы понять имеет смысл этот алгоритм в реальных проектах, или нет
Википедия утверждает, что для маленьких деревьев — очень большие накладные расходы получаются, и предлагает использовать trie, y-fast tries, x-fast tries:
Van_Emde_Boas_tree
However, for small trees the overhead associated with vEB trees is enormous: on the order of 2m/2. This is one reason why they are not popular in practice. One way of addressing this limitation is to use only a fixed number of bits per level, which results in a trie. Other structures, including y-fast tries and x-fast tries have been proposed that have comparable update and query times but use only O(n) or O(n log M) space where n is the number of elements stored in the data structure.
Van_Emde_Boas_tree
However, for small trees the overhead associated with vEB trees is enormous: on the order of 2m/2. This is one reason why they are not popular in practice. One way of addressing this limitation is to use only a fixed number of bits per level, which results in a trie. Other structures, including y-fast tries and x-fast tries have been proposed that have comparable update and query times but use only O(n) or O(n log M) space where n is the number of elements stored in the data structure.
>> где U = 2k
Т.е. для 32х разрядных чисел это будет 2^32 = 4294967296
O(log(log(U))) будет порядка O(log(k)) вместо «обычных» O(log(n)).
Т.е. для 32х разрядных чисел это будет 2^32 = 4294967296
O(log(log(U))) будет порядка O(log(k)) вместо «обычных» O(log(n)).
Спасибо за статью!
> …скажем, мы будем хранить в дереве номера каких-то товаров и по номеру сможем узнавать имя товара…
Но ведь соответствие номер-имя всё равно будет храниться в обычном дереве, со временем выборки N log N?
> …скажем, мы будем хранить в дереве номера каких-то товаров и по номеру сможем узнавать имя товара…
Но ведь соответствие номер-имя всё равно будет храниться в обычном дереве, со временем выборки N log N?
Эта информация будет храниться в дереве вместе с минимумом (то есть T.min и, скажем, T.min_value) и ничего больше нам для этого не будет нужно.
Вместо булева T.exists[] будет структура с доп. информацией.
А те же проверки заменятся на равно (не равно) null.
А те же проверки заменятся на равно (не равно) null.
Поясню, а то два разных ответа. Я ответил про простой случай, в котором нет возможности FindNext и FindPrevios, а Invizory выше про дерево уже с такими возможностями.
Такие соотношения вообще можно держать в хеше, и получится быстродействие O(N) (если грубо), что оптимальнее данного алгоритма, особенно на практике.
Но чаще держат в B-деревьях, так как они оптимизированы под работу блочной структурой диска со сложность N log N.
Такие соотношения вообще можно держать в хеше, и получится быстродействие O(N) (если грубо), что оптимальнее данного алгоритма, особенно на практике.
Но чаще держат в B-деревьях, так как они оптимизированы под работу блочной структурой диска со сложность N log N.
А что с памятью? Вроде в статье есть беглая оценка в O(U) — это странно.
Ведь если каждая операция log(log(U)) времени, то памяти займем не более чем n * log(log(U)), если не делать зверских предобработок.
Ведь если каждая операция log(log(U)) времени, то памяти займем не более чем n * log(log(U)), если не делать зверских предобработок.
Я правильно понимаю, что при больших k (>18-20) мы улетаем за границы кешей процессора, и все начинает так тормозить, что никакое log(log()) не поможет?
Мне кажется это проблема присуща большинству структур данных.
— двоичный поиск будет попадать мимо кеша поначалу
— AVL и RB -деревья тоже могут попадать мимо кеша
А большинство сортировок похоже будут хорошо ложится в кеш:)
— двоичный поиск будет попадать мимо кеша поначалу
— AVL и RB -деревья тоже могут попадать мимо кеша
А большинство сортировок похоже будут хорошо ложится в кеш:)
Во-первых, k у нас является степенью двойки (по очевидным причинам) и немного неправильно писать «k > 18-20».
Во-вторых, могу сказать, что при N >= 10^6, дерево ван Эмде Боаса начинает ощутимо перегонять двоичные деревья поиска, в том числе и красно-черное дерево. Если же нужны красивые графики, большие таблички и конкретные числа — тут нужно уже делать отельный крутой бенчмарк.
Если же все-таки нужны конкретные цифры, то, скажем, на тесте N = 10^7, K = 32 всеми нами любимый STL'ный set (а STL, как известно, не индусы писали — чего только стоит их хитрый sort) работает за 4.856 секунд, когда дерево ван Эмде Боаса (в моей реализации) за 1.471. Вот как-то так.
Во-вторых, могу сказать, что при N >= 10^6, дерево ван Эмде Боаса начинает ощутимо перегонять двоичные деревья поиска, в том числе и красно-черное дерево. Если же нужны красивые графики, большие таблички и конкретные числа — тут нужно уже делать отельный крутой бенчмарк.
Если же все-таки нужны конкретные цифры, то, скажем, на тесте N = 10^7, K = 32 всеми нами любимый STL'ный set (а STL, как известно, не индусы писали — чего только стоит их хитрый sort) работает за 4.856 секунд, когда дерево ван Эмде Боаса (в моей реализации) за 1.471. Вот как-то так.
«STL'ный set… работает за 4.856 секунд» что это значит? Какие операции? Какие данные? Как время замерялось? Какая погрешность? Да и поиск в сортированном векторе почти в 4 раза быстрее чем в set. habrahabr.ru/blogs/cpp/114518/
Я же сказал, что надо делать нормальный бенчмарк. Это я предоставил в качестве примера того, что дерево ван Эмде Боаса работает быстрее сеты в некоторых условиях.
Поиск в отсортированном векторе (и да, раз мы уж о производительности — к черту вектора, используем обычные массивы) бинарным поиском конечно тоже можно применить, но пока еще никто не научился вставлять элемент в середину вектора быстрее, чем за O(n).
Поиск в отсортированном векторе (и да, раз мы уж о производительности — к черту вектора, используем обычные массивы) бинарным поиском конечно тоже можно применить, но пока еще никто не научился вставлять элемент в середину вектора быстрее, чем за O(n).
Да, STL не индусы писали, но всё-таки у сета довольно большая константа. Мне кажется, что дерево ван Эмде Боаса стоит сравнивать по времени работы с деревом отрезков. У дерева отрезков время работы O(N*log(N)), причём константа не сильно большая, а так же оно поддерживает все необходимые вам операции. Что касается памяти, так вроде полностью заполненное дерево вад Эмде Боаса будет хранить более 2*N памяти (размер дерева отрезков) из-за хранения этих дополнительных aux k/2-деревьев.
И ещё остался вопрос по ассимптотике:
Не понятно, почему в случае вставки в aux следующий за ним insert работает за O(1). Ведь нам всё равно при выполнении insert придётся пройти те же самые log(k) уровней до 1-дерева, значит и функция T(k) время работы будет более сложно пересчитываться, разве нет?
И ещё остался вопрос по ассимптотике:
Асимптотика времени его работы будет все так же O(log(log(U))), она оценивается аналогично предыдущей версии функции insert. Необходимо лишь заметить, что если мы выполним вставку в aux, то следующий за ним insert будет работать за O(1), так как это поддерево будет пустым.
Не понятно, почему в случае вставки в aux следующий за ним insert работает за O(1). Ведь нам всё равно при выполнении insert придётся пройти те же самые log(k) уровней до 1-дерева, значит и функция T(k) время работы будет более сложно пересчитываться, разве нет?
Насчет дерева отрезков могу сказать следующее. При K = 32 ось попросту отказалась выделять мне столько памяти для него, ну оно и понятно, поэтому U было снижено до 108. После чего RMQ отработала N = 107 запросов вставки и нахождения следующего за 5.24 секунды, тогда как дерево ван Эмде Боаса за 3.112. Ну как бы понятно, что все бенчмарки, проводимые мною, не совсем честные, поэтому надо делать нормальный, но уже можно видеть, что преимущество дерево ван Эмде Боаса таки дает.
К вопросу об асимптотике. Следующий insert будет работать за асимптотику O(1) по той простой причине, что
по условию дерево T.children[high(x)] — пустое, а вставка в пустое дерево
как можно видеть, работает за константу.
P. S. Привет команде посвята :)
К вопросу об асимптотике. Следующий insert будет работать за асимптотику O(1) по той простой причине, что
if T.children[high(x)].is_empty():
insert(T.aux, high(x))по условию дерево T.children[high(x)] — пустое, а вставка в пустое дерево
if T.is_empty():
T.min = T.max = xкак можно видеть, работает за константу.
P. S. Привет команде посвята :)
Да, теперь видно преимущество этого дерева перед остальными при больших U. Код, правда, чуть более сложный, но при написании больших проектах, где быстродействие важно, это дерево полезно использовать.
Спасибо за уточнение. Что-то я пропустил строки вставки элемента в пустое дерево.
P. S. Мда, мир тесен. Про это дерево вам рассказали в параллели A, или где ты натолкнулся на эту структуру?
Спасибо за уточнение. Что-то я пропустил строки вставки элемента в пустое дерево.
P. S. Мда, мир тесен. Про это дерево вам рассказали в параллели A, или где ты натолкнулся на эту структуру?
спасибо за статью.
плюсовать не хватает кармы ((
плюсовать не хватает кармы ((
Не к чему придраться. Хорошо написано и код качественный! Нужно больше таких авторов на хабре.
Хотелось бы спросить какое отношение имеет автор к этой теме (работа, научная деятельность, олимпиадное программирование или что-то другое)?
Хотелось бы спросить какое отношение имеет автор к этой теме (работа, научная деятельность, олимпиадное программирование или что-то другое)?
Ваша реализация падает в деструкторе. linux, gcc version 4.5.2.
UFO just landed and posted this here
Имею честь быть с Петером ван Эмде Босом знакомым лично. Писал в со-авторстве с его женой книгу…
Интересно, что не все добавившие статью в избранное, поставили плюс этой статье :)
Это очень частое явление…
Обычно это значит что не у всех, добавивших в избранное, есть возможность ставить плюсы.
Или что человек поставит плюс, когда прочитает статью, я обычно добавляю статью в избранное, чтобы когда появится время — посидеть и спокойно почитать и разобраться.
Только плюсы можно ставить в течение двух дней с момента публикации. Часто у хороший статей плюсов меньше, чем число человек, добавивших статью в избранное.
Я обычно плюсую статью уже за то, что она заинтересовала меня. А если была полезной, то автору плюс и в карму поставлю (благо, это можно сделать всегда).
Я обычно плюсую статью уже за то, что она заинтересовала меня. А если была полезной, то автору плюс и в карму поставлю (благо, это можно сделать всегда).
Спасибо за статью.
Видимо я что-то не понял в подсчёте сложности. Поясните, пожалуйста. Вопрос по простому алгоритму. Что мы считаем элементарной операцией? Считаете ли вы любую функции high и low требующими одну операцию? Обращение по индексу длины k/2 является одной операцией?
Видимо я что-то не понял в подсчёте сложности. Поясните, пожалуйста. Вопрос по простому алгоритму. Что мы считаем элементарной операцией? Считаете ли вы любую функции high и low требующими одну операцию? Обращение по индексу длины k/2 является одной операцией?
Конечно, у нас же обращение к массиву за O(1).
По поводу high и low — вот их реализация битовыми сдвигами:
По поводу high и low — вот их реализация битовыми сдвигами:
high(x) = x >> (k / 2)
low(x) = x & (~(1 << (k / 2)))Не очень понял. Поместить индекс длины k/2 это тоже одна операция? Деление числа k на 2, сдвиг на k/2 бит — одна операция?
Я имею в виду, почему Вы не считаете битовую сложность? Если Вы говорите о числах длины k, то нужно операции над числами длины k считать не константными.
Не 1 операция, а O(1), это важно.
Далее, все эти операции, будь то сдвиг или еще что выполняются за одну процессорную операцию и ему абсолютно по-барабану какое там k.
Например, вот такой сдвиг влево
и вот этот
вообще ничем не отличаются и выполняются за одно и то же число процессорных тактов.
Далее, все эти операции, будь то сдвиг или еще что выполняются за одну процессорную операцию и ему абсолютно по-барабану какое там k.
Например, вот такой сдвиг влево
shl eax, 1и вот этот
shl eax, 8вообще ничем не отличаются и выполняются за одно и то же число процессорных тактов.
Sign up to leave a comment.
Дерево ван Эмде Боаса