Здравствуйте, Codealot, Вы писали:
S>>Правда, в случае C/C++/Rust для списков (особенно интрузивных) применимость может быть найдена, и как раз об этом было бы интересно побеседовать.
C>Вместо rope? А зачем?
На этот вопрос у меня есть заготовленный ответ
Там даже есть про богомерзкий разворот односвязного списка
Здравствуйте, Codealot, Вы писали:
S>>Правда, в случае C/C++/Rust для списков (особенно интрузивных) применимость может быть найдена, и как раз об этом было бы интересно побеседовать.
C>Вместо rope? А зачем?
Про rope я наслышан только в контексте строк (т.е. последовательностей байт или символов). Тогда как связный список иногда может рассматриваться как замена контейнерам вроде vector или deque для любых T. Применительно к языкам вроде C++ у связных списков есть такие достоинства как:
— ссылки на содержимое не инвалидируются при модификации контейнера;
— в случае интрузивных списков и использования преаллоцированных элементов списка можно делать операции вставки в контейнер действительно noexcept.
Так же списки позволяют собирать в контейнер объекты, которые в принципе не Copyable и не Moveable. Тут, правда, все равно остается вопрос о том, на не будет ли vector<unique_ptr<T>> эффективнее, чем list<T>. Но это уже от условий зависит.
В общем, интрузивный список где-то раз в год, раз в полгода приходится применять.
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>На этот вопрос у меня есть заготовленный ответ SVZ>Там даже есть про богомерзкий разворот односвязного списка
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>и восстановление недостающих/кривых данных.
Это точно обычно не входит в парсинг.
SVZ>А просто парсер накарябать — это задача уровня курсовика для студента.
Как показывает практика, современные эксперты по сортировке гномов не в состоянии сделать даже окно, не налажав при этом. Так что это, кхм-кхм, крайне оптимистично.
Здравствуйте, Codealot, Вы писали:
SVZ>>На этот вопрос у меня есть заготовленный ответ SVZ>>Там даже есть про богомерзкий разворот односвязного списка
C>А что мешает использовать в этой задаче веревку?
Чем она лучше односвязного списка в приведённом примере?
Даже не так, как rope вообще применима в приведённом примере?
Список использовался, потому что нужно хранить упорядоченный набор элементов (вершин). Над каждым элементом можно производить манипуляции (изменение координат, добавление, удаление), не затрагивая соседние. Каждый элемент должен быть идентифицируемым. Списки делятся, объединяются очень легко.
Наконец, все операции должны поддерживать Undo/Redo.
Ну и как тут поможет rope, у которой очень специфичная область применения?
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Codealot, Вы писали:
SVZ>>и восстановление недостающих/кривых данных.
C>Это точно обычно не входит в парсинг.
У нас это называлось "Импорт данных".
SVZ>>А просто парсер накарябать — это задача уровня курсовика для студента.
C>Как показывает практика, современные эксперты по сортировке гномов не в состоянии сделать даже окно, не налажав при этом. Так что это, кхм-кхм, крайне оптимистично.
Ну я слышал от своего быв. коллеги, что сейчас с молодыми программистами дело плохо. Ну что же, зато у нас всё хорошо.
Предложений хватает, зарплаты платят хорошие. Будем работать, пока не издохнем
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Чем она лучше односвязного списка в приведённом примере?
Как минимум, расход памяти намного меньше. Возможно, также и быстрее.
SVZ>Даже не так, как rope вообще применима в приведённом примере?
Список с эффективной вставкой и/или удалением. В чем разница?
SVZ>Список использовался, потому что нужно хранить упорядоченный набор элементов (вершин).
Упорядоченный в смысле отсортированный, или просто с известной позицией элементов?
Здравствуйте, Codealot, Вы писали:
S>>Про rope я наслышан только в контексте строк (т.е. последовательностей байт или символов).
C>Ничто не мешает использовать его с любым типом элементов.
Но зачем?
Фокус rope string в том, что это дерево, в листах которого расположены непрерывные блоки с CharT произвольного размера. И понятно откуда эти блоки берутся (как и понятно почему они могут быть сильно разными).
Тогда как в случае замены CharT на произвольный T смысл этой кухни теряется.
И непонятно в чем преимущество rope для T перед каким-нибудь условным списком чанков одинаковой емкости.
Как бы то ни было в контексте C++ rope вряд ли может дать те гарантии, какие дает список (они перечислялись выше).
Здравствуйте, Codealot, Вы писали:
SVZ>>Чем она лучше односвязного списка в приведённом примере?
C>Как минимум, расход памяти намного меньше. Возможно, также и быстрее.
Касательно расхода памяти дерево не будет эффективнее списка.
Для больших элементов, когда накладные расходы пренебрежимо малы, по-сравнению с полезными данными, это роли не играет.
Но в данном случае получается слишком жирно.
SVZ>>Даже не так, как rope вообще применима в приведённом примере? C>Список с эффективной вставкой и/или удалением. В чем разница?
Логарифм в верёвке против константы в списке? Я всё-таки за список
SVZ>>Список использовался, потому что нужно хранить упорядоченный набор элементов (вершин).
C>Упорядоченный в смысле отсортированный, или просто с известной позицией элементов?
Упорядоченный в смысле фиксированный порядок элементов. В частности, вершины полигона или полилинии имеют определенный порядок. Т.е. ты можешь изменить координаты вершины, но взаимный порядок вершин при этом не меняется.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Касательно расхода памяти дерево не будет эффективнее списка.
Если у тебя несколько элементов в каждом сегменте и маленькая глубина в дереве (а здесь большая глубина не нужна), то будет.
SVZ>Для больших элементов, когда накладные расходы пренебрежимо малы, по-сравнению с полезными данными, это роли не играет.
Это может быть, если они очень большие.
SVZ>Логарифм в верёвке против константы в списке? Я всё-таки за список
Меньше расход памяти, и может быть быстрее.
S>И непонятно в чем преимущество rope для T перед каким-нибудь условным списком чанков одинаковой емкости.
А это не частный случай веревки?
S>Как бы то ни было в контексте C++ rope вряд ли может дать те гарантии, какие дает список (они перечислялись выше).
Веревка позволяет реализовать даже доступ по индексу, и использовать пул заранее выделенных сегментов никто не запрещает.
"ссылки на содержимое не инвалидируются при модификации контейнера" — ну гипотетически может быть полезно, но я не помню ни одного примера, когда мне это понадобилось бы.
Здравствуйте, Codealot, Вы писали:
S>>Но зачем?
C>Меньше расход памяти, и может быть быстрее.
На первый взгляд сомнительно. А есть какие-то примеры применения rope-структуры не для строк, а для чего-то другого?
S>>И непонятно в чем преимущество rope для T перед каким-нибудь условным списком чанков одинаковой емкости.
C>А это не частный случай веревки?
rope -- это дерево, причем желательно, чтобы оно было сбалансированным, т.е. при большом количестве кусочков оно должно быть "высоким". Тогда как список чанков -- это "плоская" структура.
Тут более актуален вопрос: а не является ли rope с листами фиксированной емкости (да еще и в которых есть пустоты) частным случаем какого-нибудь B-дерева?
S>>Как бы то ни было в контексте C++ rope вряд ли может дать те гарантии, какие дает список (они перечислялись выше).
C>Веревка позволяет реализовать даже доступ по индексу
Если нужен доступ по индексу, то список изначально мимо кассы.
C>и использовать пул заранее выделенных сегментов никто не запрещает.
Могу предположить, что геморра больше, т.к. rope гораздо более сложная структура, ее на коленке не сделаешь. В отличии от интрузивного списка.
C>"ссылки на содержимое не инвалидируются при модификации контейнера" — ну гипотетически может быть полезно, но я не помню ни одного примера, когда мне это понадобилось бы.
Здравствуйте, so5team, Вы писали:
S>На первый взгляд сомнительно. А есть какие-то примеры применения rope-структуры не для строк, а для чего-то другого?
Если взять, к примеру, связный список, но с несколькими элементами в каждом узле — что помешает ему работать?
S>Тут более актуален вопрос: а не является ли rope с листами фиксированной емкости (да еще и в которых есть пустоты) частным случаем какого-нибудь B-дерева?
Здравствуйте, Codealot, Вы писали:
S>>На первый взгляд сомнительно. А есть какие-то примеры применения rope-структуры не для строк, а для чего-то другого?
C>Если взять, к примеру, связный список, но с несколькими элементами в каждом узле — что помешает ему работать?
Интересны примеры использования rope для чего-то отличного от строк. Ибо если это не строки, то смысл rope от меня ускользает.
Так что если вам известны примеры, то поделитесь ссылками, плз. Реально любопытно.
Рассуждать же вокруг да около не интересно. Так-то можно и multimap в качестве priority_queue использовать. Смысл, правда, сложно найти.
S>>Тут более актуален вопрос: а не является ли rope с листами фиксированной емкости (да еще и в которых есть пустоты) частным случаем какого-нибудь B-дерева?
C>B-дерево отсортировано.
Дерево в rope (по сути) тоже отсортировано (по порядковым номерам фрагментов). Тут суть в структуре, когда есть дерево в котором промежуточные узлы просто ведут вниз, а данные находятся в листьях.
Здравствуйте, so5team, Вы писали:
S>Интересны примеры использования rope для чего-то отличного от строк. Ибо если это не строки, то смысл rope от меня ускользает. S>Так что если вам известны примеры, то поделитесь ссылками, плз. Реально любопытно.
Ладно, видимо это все же не rope, а что-то похожее. Самое близкое, что я нашел, это https://en.wikipedia.org/wiki/Unrolled_linked_list
Можно сделать эффективнее, но как это называется я не знаю
Мой пойнт был, что делать связный список из чисел, как это часто любят делать в задачах — это пример того, как делать ни в коем случае не надо.
Здравствуйте, Codealot, Вы писали:
S>>Интересны примеры использования rope для чего-то отличного от строк. Ибо если это не строки, то смысл rope от меня ускользает. S>>Так что если вам известны примеры, то поделитесь ссылками, плз. Реально любопытно.
C>Ладно, видимо это все же не rope, а что-то похожее. Самое близкое, что я нашел, это https://en.wikipedia.org/wiki/Unrolled_linked_list
Я привык называть эту штуку chunked list.
C>Можно сделать эффективнее, но как это называется я не знаю
Возвращаясь к вопросу собеседований: имхо, вот такие вот разговоры (спором это сложно назвать) на собеседовании могут дать гораздо лучшее представление о возможностях программиста, чем online-кодинг около-олимпийских задач. Но именно разговоры в смысле рассуждений о применимости тех или иных структур данных (или алгоритмов) в разных условиях, с перечислением достоинств и недостатков, выяснением граничных случаев. Сильно сомневаюсь, что вероятность найти человека, который понимает, где лучше list, где лучше deque, где лучше vector, но при этом не умеет программировать, настолько велика, что с ней нужно считаться на собеседовании. Гораздо вероятнее встретить того, кто зазубрил решения для первых N задачек с leetcode или из какой-нибудь книги типа "Grokking the Coding Interview Patterns".
C>Мой пойнт был, что делать связный список из чисел, как это часто любят делать в задачах — это пример того, как делать ни в коем случае не надо.
Здравствуйте, so5team, Вы писали:
S>Сильно сомневаюсь, что вероятность найти человека, который понимает, где лучше list, где лучше deque, где лучше vector, но при этом не умеет программировать, настолько велика, что с ней нужно считаться на собеседовании.
