С модифицированным. Так же в реализации RBTree использовался небольшой хак: число элементов и цвет хранились в одном int. Это корректно, так как по условию задачи максимальное количество элементов 10^6.

u_story Mar 13 2012 at 11:01

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

kashey Mar 13 2012 at 11:06

Например скип листы можно использовать для представления деревьев, при этом находясь на верхней ноде можно простым способом найти всех детей, какой бы глубины дерево дальше не лежало.

Pliner Mar 13 2012 at 11:09

Не очень понял о чем вы :)

kashey Mar 13 2012 at 11:13

Представьте себе отсортированный массив из 10 элементов.
Залейте его в сбалансированный B-Tree.
первая нода будет 5, левее будет 2, правее 7. Представьте как это дерево ветвится.
А теперь посмотрите на картинки в статье.
Если уровень скиплиста приравнять к уровню вложенности дерева — то все станет ясно.

Pliner Mar 13 2012 at 11:17

Например, когда требуется concurrent доступ к коллекции. Из-за локальных изменениях при вставке в SkipList(в отличии от вставки в дерево, само дерево может сильно перестроиться), реализация такой коллекции на SkipList может оказаться эффективнее.

Если интересно, могу об этом рассказать подробнее в следующей статье.

mejedi Mar 13 2012 at 12:52

Интересно.

Вы имеете в виду, что выгода — в том что модифицируется меньше указателей? Не могли бы вы в двух словах сказать, почему это хорошо?

Pliner Mar 13 2012 at 13:56

Именно в этом. Балансировка может сильно перестроить дерево, при этом потребуется заблокировать много его узлов. В Skiplist, как я уже говорил, операция вставки локальна: блокировок потребуют только те узлы, которые непосредственно связаны с вставляемым узлом.

По этому поводу есть хорошая статья.

mejedi Mar 13 2012 at 14:23

Вы предлагаете завести по мьютексу в каждом узле, и лочить их все по-отдельности?
Вряд-ли это будет быстрее чем один мьютекс на всю структуру. Вставки то быстро происходят.

Pliner Mar 13 2012 at 17:32

Мьютекс на всю структуру — не очень хорошая идея. Один поток что-то делает, все остальные ждут.

Акцент стоило сделать на том, что приходится блокировать БОЛЬШОЙ кусок дерева. Из-за этого, при concurrent доступе при увеличении количества потоков скорость работы с деревом сильно деградирует.

mejedi Mar 13 2012 at 18:56

Все зависит от пропорций оверхед на локинг/время, в залоченном состоянии. ИМХО если мы конструируем новый узел заранее, а в залоченном состоянии просто добавляем его в дерево, то оверхед примерно сопоставим со временем перебалансировки.

Улучшая гранулярность блокировок, мы при этом увеличиваем оверхед на локинг.

mihaild Mar 13 2012 at 11:45

А если взять не RB, а что-нибудь с лучшей балансировкой, например AVL? Ну и если уж работаем с вероятностными алгоритмами (кстати, «логарифмически случайное», наверное, лучше заменить на «логарифмическое в среднем»), то как себя поведет декартово дерево?
И что будет, если взять датасеты не такого игрушечного размера, а хотя бы в 10 (а лучше в 100) раз больше?

Pliner Mar 13 2012 at 12:23

Сегодня добавлю сравнение с AVL Tree и увеличу датасеты. С декартовым придется немного подождать :)

ntz Mar 13 2012 at 12:06

~~А почему блог не СКБ Контур?~~

Кстати, сие решение самое очевидное (сам на красно-черном сделал, но и о списках с пропусками подумал), однако памяти жрет (по сравнению самым простым сортированным массивом) мама не горюй.

И вообще, вот же оно intern_develop_solutions.pdf

PS: делал ради интереса, заявок никуда не подавал, в порочащих связях замечен не был.

Pliner Mar 13 2012 at 13:07

1) Я писал от себя, а не от компании, поэтому не в блоге СКБ Контура. Решил начать вести профессиональный блог, начав с описания первого шага в профессию разработчика. Но раз уж вы упомянули, то в этом году тоже проходит Летняя стажировка. Вот ссылка на тестовое: порешайте на досуге =)

2) С сортированным массивом другие трудности(простейший тест, который все рушит, есть в статье). На самом деле, решали эту задачу примерно так: половина — с помощью сортированного массива, четверть — деревом отрезков(с предварительным препроцессингом запросов), четверть — с помощью BST.

metar Mar 13 2012 at 13:34

> четверть — деревом отрезков(с предварительным препроцессингом запросов)
АСМщики детектед. Удивительно, что никто не козырнул битовой магией и не сделал дерево Фенвика. :-)

iago Mar 13 2012 at 15:11

Нормальный человек детектед. А тесты эти не для нас делают :)

voronaam Mar 13 2012 at 17:05

Стажировка в гугл? Мне на собеседовании в Google задавали задачку написать реализацию skiplist на С. Видимо у них используется где-то…

Pliner Mar 16 2012 at 05:14

Стажировка в СКБ Контур. Когда работаешь над новым проектом и в «голове» компании, то больше возможностей повлиять на то, каким будет продукт.

burzzo Jan 10 2016 at 15:43

Xorshift делает равномерное распределения, или характер зависит от the seed set Z?

burzzo Jan 10 2016 at 16:43

Упомянается, что вы открывали книгу Кормена. Я её открыл (издание 2013г.), но там не нашёл сведения про эту структуру данных. А вы, ношли?

burzzo Jan 10 2016 at 19:35

Вы упомнали лекцию, которую пересмаривали вы пересматривали, это Лекция№12?
https://www.youtube.com/watch?v=IXRzBVUgGl8
https://itunes.apple.com/us/itunes-u/introduction-to-algorithms/id341597754

Курса Mit. Algorithms and datastructures из 2005-го года.
Если это она — то круто думаю было бы её добавить в статью в раздел библиографии.