Комментарии 25
Странно, что нет библиотеки нормальной
Шарп богат всякими прикладными библиотеками
А в других языках пробовали искать а потом подключить как-то?
Тоже был удивлён отсутствием либы. В других языках не искал.
В конце концов я не жалею о проделанной работе, для реализации дерева интервалов всё равно потребовалось бы вникать в работу красно-чёрного. Ну и сам факт, что запрограммировал что-то интересное (и невероятно полезное для моего проекта), радует.
спасибо интересно очень
В стандартной библиотеке есть 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 и "утрамбовку" памяти для списка могут стать гораздо дешевле, чем для связного списка.
Не знаю как в вашем случае, а для какого-нибудь хайлоада/хай срупута я бы предпочел список (если быть до конца точным - структуру, основанную на массивах и не допускающую попадания в ЛОХ)
Спасибо за статью. Хотел уточнить про добавление в дерево элементов с одинаковым ключем - почему нельзя было бы использовать сложный ключ - что-то типа время+номер трека?
Интересное предложение. Теоретически, наверное, так сработает. Только второй компонент не номер трека, а 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). Я в алгоритмах не особый специалист и всякие хитрые штуки изучить хотелось бы.
Вы в начале статьи упоминали о баге в "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.
Красно-чёрное дерево: полная реализация на C#