Comments 44
Странно, что нет библиотеки нормальной
Шарп богат всякими прикладными библиотеками
А в других языках пробовали искать а потом подключить как-то?
Тоже был удивлён отсутствием либы. В других языках не искал.
В конце концов я не жалею о проделанной работе, для реализации дерева интервалов всё равно потребовалось бы вникать в работу красно-чёрного. Ну и сам факт, что запрограммировал что-то интересное (и невероятно полезное для моего проекта), радует.
спасибо интересно очень
В стандартной библиотеке есть SortedSet, у него под капотом сабж
Да, а ещё SortedDictionary. Вопрос только в том, как данные классы удовлетворяют выдвинутым мной в статье требованиям? Могу ли я добавить объекты с повторяющимися ключами? Могу ли взять ссылку на конкретный узел, чтобы реализовать нужные мне вещи? А дерево интервалов как над ними построить?
Что SortedSet, что SortedDictionary попадали в поле моего зрения, вот только я с ними ничего сделать не смогу в рамках своих хотелок.
К сожалению, кажется, что статья не была прочитана перед написанием комментария.
Могу ли я добавить объекты с повторяющимися ключами?
Конечно, так же, как вы сделали в статье — использовать в качестве значения LinkedList. Кстати, зря вы выбрали LinkedList, просто List на современном железе быстрее практически во всех сценариях, тем более в системе со сборкой мусора.
А дерево интервалов как над ними построить?
Так же.
Всё-таки нельзя говорить "структура A быстрее структуры B", не сказав, о какой операции речь. Взятие элемента по индексу? Да, у List это O(1), у LinkedList — O(N). Добавление и удаление? У LinkedList это O(1) всегда, но у List будет O(N) в худшем случае.
Но если вы читали статью, у меня нет операций взятия по индексу, а вот добавление и удаление как раз активно используются. Связный список в этих сценариях хорош тем, что просто меняет пару указателей, а вот списку (List, который на основе массива) нужно ещё периодически выделять память, двигать и копировать элементы.
Прелесть нотации "O" большое в том, что мне даже не нужно бенчмарки запускать для понимания скорости. Но я всё же их сделал:
результаты: https://gist.github.com/melanchall/b672c206cc3fb5985fa7d4906ced851a
код бенчмарков: https://gist.github.com/melanchall/fd07c11e4ade32c7b1aba5f0c1008686
Спойлер: там всё, как и ожидается. Связный список для добавления и удаления лучше. Поиск плохой, да, оно и неудивительно. Но поиск мне и не нужен, см. статью. Кроме того, при увеличении N заметна разница в потреблении памяти обеими структурами (LinkedList делает меньше выделений памяти).
Про построение дерева интервалов не понял. Как так же его построить? Стандартные классы .NET предоставляют какие-то коллбэки на добавление и удаление данных, где я могу запустить обновление границ узлов? А саму груницу узлов где повесить? А доступ к узлам вообще есть?
Спойлер: там всё, как и ожидается. Связный список для добавления и удаления лучше.
У вас там разница меньше статистической погрешности.
Кроме того, при увеличении
Nзаметна разница в потреблении памяти обеими структурами (LinkedListделает меньше выделений памяти).
Так вы создали для листа худший случай: когда вы в него добавляете новый элемент, он у вас забит под завязку, и листу приходится реаллоцироваться.
У вас там разница меньше статистической погрешности.
Пусть так. Можно ли при этом говорить, что List быстрее?
Так вы создали для листа худший случай
Верно. Я библиотеку не для себя делаю, а для широкого круга пользователей. А потому всегда должен смотреть на худший случай тоже.
когда вы в него добавляете новый элемент, он у вас забит под завязку, и листу приходится реаллоцироваться
Верно, но не совсем. Когда List "забит" под завязку, то в большинстве случаев реаллокаций не будет, потому что List с запасом выделяет внутренний массив (если не ошибаюсь, в случае нехватки он делает массив двойной длины). Но при добавлении в середину он будет всегда проводить сдвиг всех элементов после добавляемого.
Но связному списку реаллоцироваться не нужно. Память он выделяет только под узлы для элементов. При этом да, не спорю, массив (который внутри List'а) при определённых обстоятельствах займёт меньше памяти, чем LinkedList.
Если нужные мне операции выполняются по скорости не хуже (в пределах статистической погрешности), чем List, но при этом в худшем случае List проигрывает, зачем использовать List? Я LinkedList не просто так выбрал, а исходя из сложности нужных мне операций, взвесив все за и против касательно List. Но я согласен, что нужно было все эти рассуждения включить в статью, дабы выбор был понятен.
Возвращаясь к дереву: все мои вопросы про доступ к узлам остаются без ответа. Потому что такого доступа стандартные классы не предоставят.
Важно, что LinkedList выделяет в куче индивидуальные ноды, тогда так List - массивы (с запасом).
Если списки не настолько большие, чтобы перейти в LOH, то начиная с определённого момента затраты на GC и "утрамбовку" памяти для списка могут стать гораздо дешевле, чем для связного списка.
Не знаю как в вашем случае, а для какого-нибудь хайлоада/хай срупута я бы предпочел список (если быть до конца точным - структуру, основанную на массивах и не допускающую попадания в ЛОХ)
А потому всегда должен смотреть на худший случай тоже.
Это не всегда хорошая затея.
Фишка в том, что этот "худший" случай не может происходить слишком часто. Если выражаться формально, то там аммортизированное O(1).
Если вы не желаете структуры данных под реальное время, то вам стоит смотреть на суммарное время выполнения операций — а оно у списков кратно быстрее.
Прелесть нотации "O" большое в том, что мне даже не нужно бенчмарки запускать для понимания скорости
Вообще нет. Если бы это было бы так, мы бы все использовали фибоначеву кучу и галактические алгоритмы (спойлер: у них очень хорошее O, но на всех доступных сейчас объёмах данных, они очень медленные).
Ну, или с другой стороны: знали ли Вы, что современные реализации сортировок используют сортировку вставками, а не квиксорт в некоторых случаях — так быстрее.
Стоит признать, что вы правы. Спасибо за конструктивное замечание. Я выполнил бенчмарки интересных мне случаев:
вставка в конец коллекции;
удаление с конца, с начала и рандомно.
Да, List выигрывает у LinkedList, если операции выполнить в цикле. Нужно будет подумать, стоит ли переходить на List. Потому что массовые операции происходят только при иницализации дерева (и то, в большинстве случаев изначально дерево пустое будет), а потом уже точечные будут. Замерю на досуге.
знали ли Вы, что современные реализации сортировок используют сортировку вставками, а не квиксорт в некоторых случаях
Нет, я этого не знал. Сейчас прочитал и таки-да, разумно.
а потом уже точечные будут. Замерю на досуге
На самом деле, замерить худший случай не так то и просто будет. Самая главная проблема - это нагрузка на аллокатор и сборщик мусора.
Например, при добавлении в связный список, у нас всегда аллоцируется узел списка. Чаще всего, это просто инкремент указателя в чистилище. Но, если окажется, что чистилище у нас занято - произойдёт малая сборка мусора. А это линейный проход по всему чистилищу (вероятно 16-256 MB на десктопе) - то есть довольно долго.
В случае же List, у нас либо хватает места и произойдёт простой инкремент индекса/указателя. Может не хватить места и произойдёт реаллок - это всего лишь копия элементов списка, а не целого чистилища. И крайний случай - может тоже не хватить памяти и произойдёт малая сборка мусора - тут тот же худший случай.
Поэтому наивный бенчмарк может померять не то (особено в языках с GC - у них большой фактор играет сборка мусора).
На практике, при длинах списка до 100 элементов, List работает быстрее LinkedList даже в худщем случае. Вся вот эта история с быстрыми точечными операциями становиться интересной когда у Вас миллионы элементов в списке - но там обычный LinkedList плохо работает, нужны интрузивные структуры данных.
Спасибо за статью. Хотел уточнить про добавление в дерево элементов с одинаковым ключем - почему нельзя было бы использовать сложный ключ - что-то типа время+номер трека?
Интересное предложение. Теоретически, наверное, так сработает. Только второй компонент не номер трека, а noteNumber + noteChannel. Потому что ноту однозначно идентифицирует её номер и канал.
Но две совершенно одинаковые ноты могут оказаться в одной и той же точке во времени. Это не запрещено стандартом, и, хотя ситуация странная, может возникнуть. И тогда мы снова получим дублированные ключи. Да и сравнивать такие ключи будет сложнее. Что значит A > B? Что у A время больше ИЛИ номер ноты больше ИЛИ номер канала больше?
Ну и событие в воспроизведении не всегда с нотой связано, есть масса других типов. Получается, что ключи будут ещё различаться набором данных внутри. Что ещё больше усложняет логику сравнения.
Всё же более понятным и однозначным вариантом выглядит простой ключ и набор значений в узле.
Да и сравнивать такие ключи будет сложнее. Что значит
A > B? Что уAвремя больше ИЛИ номер ноты больше ИЛИ номер канала больше?
Сравнение как раз довольно простое - если использовать например SortedSet<T>, то достаточно воспользоваться конструктором который принимает IComparer и передать туда имплементацию с методом Compare что-то типа:
(x, y) => x.Time - y.Time != 0 ? x.Time - y.Time : x.Channel - y.Channel
Цепочку сравнений можно сколь угодно увеличивать.
Вместо отдельной имплементации IComparer, можно у самого элемента имплементировать IComparable<T>.
Говоря о проблемах сравнения, я, разумеется имел в виду логику сравнения, алгоритм. Не реализацию на языке программирования. Закодить-то несложно (если есть алгоритм). Наиболее простым способом будет реализовать IComparable<> на классе-ключе, чтобы не менять код самого дерева.
Но именно логика сравнения является сложной частью головоломки. Во-первых, класс-ключ будет содержать большое число условий и проверок. Во-вторых, проблемы, описанные выше. В третьих, придётся менять и код дерева тоже. Потому что теперь мы не сможем легко и просто взять значения, у которых время равно T. Ибо ключ не равен времени, и нужно заглядывать внутрь ключа.
Как я и писал выше, в теории оно сработает, можно и так сделать. Другое дело, что композитный ключ порождает большое количество вопросов и проблем. А зачем, если можно сделать проще? Разве что в качестве интеллектуального упражнения.
Ну и статья про красно-чёрное дерево, не про SortedSet<>. Почему мне оно не подходит, я в другом комментарии отвечал.
уже пол года висит у меня начавшийся но недоделанный самобалансирующееся двоичное дерево поиска, поизучаю ваше решение, я плох в ООП, будет над чем подумать. Но я, как и вы, не вижу тут применения List, сам гонял разные тесты и двунаправленный список работает быстрее на вставках и удалениях (для меня это архи важно), а со списком сдвигов данных так много, что всё мне очень не нравится.
Так вы просто забирайте код из статьи ;-)
посмотрим, но я не хотел делать красно-черное дерево, я в целом не понял смысла в делении на красное и черное, плюс балансировка делается изменением указателя, то есть для чего нужно поле с явным указанием на красное или черное я так и не сообразил. Ваш код мне будет подспорьем наверное в том как оформить сам класс и методы, но содержимое будет другим. Вообще я еще думаю делать или нет доступ по индексу, что чтение было O(1).
"Цвет" нужен как раз для понимания, нужно ли переставить узлы и какие именно. У красно-чёрного дерева есть ряд условий на соседство цветов, которые должны соблюдаться. Вот их нарушение и запускает балансировку.
Взятие элемента по индексу за O(1) вы в дереве не сделаете. Только если рядом хранить какой-то массив и держать его в отсортированном состоянии. Но тогда и дерево не нужно.
в этом и проблема, для балансировки не нужен ни цвет ни условия связанные с ним, достаточно хранить два значения высоты правого и левого крыла дерева.
ну если сделаю О(1) то напишу статью, но это не вопрос того что нельзя сделать, а только вопрос того нужно ли оно мне. А дерево нужно чтобы у вас поиск был за О(logN), а не за O(N), так что оно нужно. Это же вопрос того что именно вам требуется от дерева, а не того нужно ли это в принципе всегда и всем.
Если вы делаете алгоритм в терминах высот поддеревьев, возможно, вам пригодится AVL-дерево. В нём в качестве balance factor используется разница высот слева и справа. И упаковка дерева плотнее выходит. В красно-чёрном используется "цвет" и не такие жёсткие ограничения на высоту, что даёт чуть более быстрое удаление за счёт меньшего количества вращений.
Я бы с удовольствием почитал статью про реализацию взятия элемента в дереве по индексу за O(1). Я в алгоритмах не особый специалист и всякие хитрые штуки изучить хотелось бы.
Что-то мне подсказывает что меня в этом смысле специалистом лучше не называть )
Почитайте про skiplist - прикольная штука.
Не знал про skip list, спасибо!
мне подсказал @wataru
Скип лист хорошая вещь, но там поиск по индексу все те же O(log n). Мне неизвестна структура, у которой одновременно поиск по индексу O(1) и добавление/удаление за O(log n).
сбалансированное бинарное дерево поиска и массив, в теории, до практики я пока не созрел. при операциях происходит обновление и массива и дерева.
Вам в массив надо в середину будет вставлять. И это за O(1) не сделать.
Вы в начале статьи упоминали о баге в "Redblack tree implementation in C#" библиотеке. Я не нашёл его описания в статье
Если вы про
Red-Black Tree Implementation in C#. Нет метода удаления данных. Кроме того, в коде найден баг (см. комментарии).
так ведь нужно перейти по ссылке. Там будет gist, в комментарии к которому найдёте подробное описание:
Unfortunately, it doesn't work for string keys. "paws" shouldn't have been "handbag"'s left child.
Еще интересный вариант дерева: cartesian tree, оно же treap, оно же декартово дерево. Там у каждого элемента 2 ключа. По превому оно дерево поиска, по второму - куча. Вторые выбираются случайно. В среднем там все операции тоже за O(log n), но требует чуть побольше памяти. Зато реализуется очень просто и дает еще возможность легко разбивать дерево на 2: в одном все маленькие элементы, в другом все большие. А также объединять 2 таких дерева в одно.
Это идеальная структура для неявного ключа, когда у вас операции не добавить ключ x, а вставить вот это значение на k-ую позицию, удалить k-ый ключ, или даже удалить/вставить кучу элементов после k-ого.
Treap-дерево попадалось на глаза, когда изучал научные работы по сбалансированным BST. Но мне запомнилось, что оно в бенчмарках заметно проигрывало AVL и красно-чёрному. Вероятно, коэффициенты при логарифме у treap-дерева больше.
И всё-таки логарифм там обеспечен с высокой вероятностью, но не гарантирован, как у AVL или красно-чёрного. У treap может и O(N) быть в маловероятном случае.
Вообще, для таких задач часто подходят splay-деревья. Они не обладают гарантиями реального времени, но зато они очень хорошо оптимизируются под нагрузку.
Касательно работы с несколькими значениями для одного ключа, классически это решается курсора и:
Разрешаете дублирование ключей
Вместо операции search вводите операции lower_bound и upper_bound (ну или search_first и search_last)
При этом, результаты поиска возвращают не значения, а курсоры: специальные объекты, которые могут перемещаться вперёд-назад (и получать значения)
Справиться с линейным поиском по значениям без наложения ограничений на сами значения нельзя. Но я не очень понял зачем Вам искать по значениям (только как деталь реализации с координатами - но это решается курсорами).
Но зато можно делать дерево поиска по составному ключу. В качестве ключа мы используем пары (K1, K2). Порядок сравнения в них лексикографический. Тогда с одной стороны, у нас есть дерево поиска по (K1, K2) без повторяющихся ключей, а с другой стороны - дерево поиска по K1, но уже с повторяющимися ключами.
P. S. Имхо, делать обобщенные(в смысле дженериков) структуры данных не очень полезно. Гораздо важнее делать структуры данных под конкретные применения — там можно гораздо лучше использовать специфику задачи.
Но я не очень понял зачем Вам искать по значениям
Как было сказано в статье, API позволяет менять воспроизводимые объекты на лету. Это значит, что пользователь может захотеть изменить, например, силу нажатия (velocity) какой-то ноты. А чтобы отразить это в плейбеке, нужно найти эту ноту во внутренней коллекции (в дереве) и поменять параметры (я делаю сейчас изменение просто: удаляю ноту и добавляю её с новыми данными).
Спасибо за полезную информацию про splay-дерево.
Тогда можно просто вставить ссылку на узел дерева прямо в саму ноту. Это гораздо эффективнее получится.
То есть, классически это решается так. Вы используете дерево для поиска по данным (интервалам времени) - возвращают эти поиски узлы (условно NoteNode). Далее операции удаления, обновления и прочего принимают напрямую эту NoteNode - в ней есть ссылки на узлы дерева. Поэтому у Вас пропадает операция поиска по объекту.
На моей практике, такой подход кратно упрощает реализацию.
Красно-чёрное дерево: полная реализация на C#