Каждый использует анонимность как хочет, многих людей она привлекает не только чувством вседозволенности и отсутствия ответственности, но тем, что анонимность позволяет отчистить общение от внешних условностей. У тебя есть слова, у собеседника есть слова и, в общем-то, не важно как вы оба выглядите, кем работаете и где живете. Важно только то, что есть в голове. Другое дело, что анонимное общение превратилось давно в субкультуру состоящую в своей массе из школьников и офисного планктона с унылым стереотипным поведением. Люди постоянно забывают, что любое общение это не то, как оно реализовано, а какие люди принимают в этом участие. Чем-то подобным мы руководствовались, создавая Хайв.
Насчет дерева отрезков могу сказать следующее. При K = 32 ось попросту отказалась выделять мне столько памяти для него, ну оно и понятно, поэтому U было снижено до 108. После чего RMQ отработала N = 107 запросов вставки и нахождения следующего за 5.24 секунды, тогда как дерево ван Эмде Боаса за 3.112. Ну как бы понятно, что все бенчмарки, проводимые мною, не совсем честные, поэтому надо делать нормальный, но уже можно видеть, что преимущество дерево ван Эмде Боаса таки дает.
К вопросу об асимптотике. Следующий insert будет работать за асимптотику O(1) по той простой причине, что
if T.children[high(x)].is_empty():
insert(T.aux, high(x))
по условию дерево T.children[high(x)] — пустое, а вставка в пустое дерево
Я же сказал, что надо делать нормальный бенчмарк. Это я предоставил в качестве примера того, что дерево ван Эмде Боаса работает быстрее сеты в некоторых условиях.
Поиск в отсортированном векторе (и да, раз мы уж о производительности — к черту вектора, используем обычные массивы) бинарным поиском конечно тоже можно применить, но пока еще никто не научился вставлять элемент в середину вектора быстрее, чем за O(n).
Во-первых, k у нас является степенью двойки (по очевидным причинам) и немного неправильно писать «k > 18-20».
Во-вторых, могу сказать, что при N >= 10^6, дерево ван Эмде Боаса начинает ощутимо перегонять двоичные деревья поиска, в том числе и красно-черное дерево. Если же нужны красивые графики, большие таблички и конкретные числа — тут нужно уже делать отельный крутой бенчмарк.
Если же все-таки нужны конкретные цифры, то, скажем, на тесте N = 10^7, K = 32 всеми нами любимый STL'ный set (а STL, как известно, не индусы писали — чего только стоит их хитрый sort) работает за 4.856 секунд, когда дерево ван Эмде Боаса (в моей реализации) за 1.471. Вот как-то так.
Это наш портированный VPN-клиент, который был изначально создан для десктопа. В качестве технологии работы используется OpenVPN, но клиент отличается тем, что он прост и в него уже все интегрировано, в том числе и биллинг. Поэтому для подключения и смены IP «на лету» необходимо нажать в нем всего одну кнопку и все будет работать без каких-либо настроек. Как-то так.
А оно никуда и не устанавливается, приложение-то портабельное. Разве что только драйвера, если очень хочется, их можно удалить в «Диспетчере устройств».
Далее, все эти операции, будь то сдвиг или еще что выполняются за одну процессорную операцию и ему абсолютно по-барабану какое там k.
Например, вот такой сдвиг влево
и вот этот
вообще ничем не отличаются и выполняются за одно и то же число процессорных тактов.
По поводу high и low — вот их реализация битовыми сдвигами:
К вопросу об асимптотике. Следующий insert будет работать за асимптотику O(1) по той простой причине, что
по условию дерево T.children[high(x)] — пустое, а вставка в пустое дерево
как можно видеть, работает за константу.
P. S. Привет команде посвята :)
Поиск в отсортированном векторе (и да, раз мы уж о производительности — к черту вектора, используем обычные массивы) бинарным поиском конечно тоже можно применить, но пока еще никто не научился вставлять элемент в середину вектора быстрее, чем за O(n).
Во-вторых, могу сказать, что при N >= 10^6, дерево ван Эмде Боаса начинает ощутимо перегонять двоичные деревья поиска, в том числе и красно-черное дерево. Если же нужны красивые графики, большие таблички и конкретные числа — тут нужно уже делать отельный крутой бенчмарк.
Если же все-таки нужны конкретные цифры, то, скажем, на тесте N = 10^7, K = 32 всеми нами любимый STL'ный set (а STL, как известно, не индусы писали — чего только стоит их хитрый sort) работает за 4.856 секунд, когда дерево ван Эмде Боаса (в моей реализации) за 1.471. Вот как-то так.
2. Оно ничего не ставит, кроме драйверов, на самом деле. Само приложение портабельно.