Pull to refresh

Comments 27

Что-то куда-то к концу статьи пропала такая часть изначальной постановки как извлечение среза. Для него можно какие-то числовые замеры сделать?
Промахнулся и ответил ниже.
Для каких тесткейзов вам интересны числовые замеры? :) Взятие среза размером 10^3, 10^4, 10^5, 10^6 подойдет?
Вы сравнивали скорость вставки и потребление памяти со «стоковым» RBTree, или модифицированным (с хранением размера поддерева в узлах)?
С модифицированным. Так же в реализации RBTree использовался небольшой хак: число элементов и цвет хранились в одном int. Это корректно, так как по условию задачи максимальное количество элементов 10^6.
прошу прощения, если не внимательно читал, но скажите, когда есть смысл использовать подобную структуру данных в реальных задачах?
Например скип листы можно использовать для представления деревьев, при этом находясь на верхней ноде можно простым способом найти всех детей, какой бы глубины дерево дальше не лежало.
Не очень понял о чем вы :)
Представьте себе отсортированный массив из 10 элементов.
Залейте его в сбалансированный B-Tree.
первая нода будет 5, левее будет 2, правее 7. Представьте как это дерево ветвится.
А теперь посмотрите на картинки в статье.
Если уровень скиплиста приравнять к уровню вложенности дерева — то все станет ясно.
Например, когда требуется concurrent доступ к коллекции. Из-за локальных изменениях при вставке в SkipList(в отличии от вставки в дерево, само дерево может сильно перестроиться), реализация такой коллекции на SkipList может оказаться эффективнее.

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

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

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

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

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

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

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

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

2) С сортированным массивом другие трудности(простейший тест, который все рушит, есть в статье). На самом деле, решали эту задачу примерно так: половина — с помощью сортированного массива, четверть — деревом отрезков(с предварительным препроцессингом запросов), четверть — с помощью BST.
> четверть — деревом отрезков(с предварительным препроцессингом запросов)
АСМщики детектед. Удивительно, что никто не козырнул битовой магией и не сделал дерево Фенвика. :-)
Нормальный человек детектед. А тесты эти не для нас делают :)
Стажировка в гугл? Мне на собеседовании в Google задавали задачку написать реализацию skiplist на С. Видимо у них используется где-то…
Стажировка в СКБ Контур. Когда работаешь над новым проектом и в «голове» компании, то больше возможностей повлиять на то, каким будет продукт.
Xorshift делает равномерное распределения, или характер зависит от the seed set Z?
Упомянается, что вы открывали книгу Кормена. Я её открыл (издание 2013г.), но там не нашёл сведения про эту структуру данных. А вы, ношли?
Вы упомнали лекцию, которую пересмаривали вы пересматривали, это Лекция№12?
https://www.youtube.com/watch?v=IXRzBVUgGl8
https://itunes.apple.com/us/itunes-u/introduction-to-algorithms/id341597754

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

Articles