сравнение стандартных библиотек
Плюс STL - относительная простота и весьма неплохая эффективность реализации.rb-деревья просасывают в сравнении с avl-деревьями
>rb-деревья просасывают в сравнении с avl-деревьями
Как-то очень категорично. Ссылочку?
Как-то очень категорично. Ссылочку?
rb-деревья просасывают в сравнении с avl-деревьями
Каждому свое.
У меня вот есть avl-дерево на шаблонах, вот только интератора там нет, только рекурсивный обход.
Как-то очень категорично. Ссылочку?Насколько я помню, 3/2 и 2. В наихудшем случае.
дисбаланс в два раза у rb не так и решает.
насколько я помню, в avl надо хранить в каждом узле глубину, а в rb — один бит.
да и реализация rb компактнее, хотя avl проще понять.
насколько я помню, в avl надо хранить в каждом узле глубину, а в rb — один бит.
да и реализация rb компактнее, хотя avl проще понять.
в avl надо хранить в каждом узле глубинуНет, достаточно хранить разность глубин левого и правого поддеревьев, то есть одно из трех чисел {-1, 0, 1}.
Плюс: понять гораздо проще, плюс: асимптотическая оценка количества операций лучше.
У меня вот есть avl-дерево на шаблонах, вот только интератора там нет, только рекурсивный обход.Легко сделать и итератор, и быстрый доступ к произвольному элементу; для этого надо знать мощность каждого поддерева. Кстати это так для любого дерева поиска.
Как-то очень категорично. Ссылочку?я проводил сравнение stl с собственной реализацией avl-деревьев.
А в википедии в статье про rb-деревья пишут, что они лучше, а в статье про avl-деревья — что лучше они
если мы обсуждаем стандартную библиотеку, то какая нам разница, что проще понять - авл или кч?
более того размер реализации тоже не так уж и важен.
важна только скорость работы и требуемая память. вот их и сравнивайте. как не небольших объемах данных, так и на огромных
более того размер реализации тоже не так уж и важен.
важна только скорость работы и требуемая память. вот их и сравнивайте. как не небольших объемах данных, так и на огромных
какая нам разница, что проще понять - авл или кчКакая вам разница, я не знаю, а мне разница есть — отсутствие доверия к реализации.
Например, документация по stl не отвечает на вопрос — используется ли копирование ключей
при вращениях КЧ-деревьев или нет, а это важно, то есть приходится смотреть код, не самый
приятный к тому же.
ну это уже недостататки библиотеки - отстутсвие нормальной документации. то что не написали о копировании ключей и из-за этого пришлось лезть в код это большой недостаток, но имхо в при реализации стандартных штучек (платформы-основы, на которой все будет держаться можно писать хоть сколь угодно невъебенно нечитаемый код, лишь бы он работал как можно быстрее, можно проводить самые ужасные оптимизации (по внешнему виду да хоть на ассемблере пусть пишут, лишь бы
1. работало правильно
2. работало быстро, кушало мало
3. все эффекты, включая побочные были бы отражены в документации
1. работало правильно
2. работало быстро, кушало мало
3. все эффекты, включая побочные были бы отражены в документации
Как правило приходится чем-то жертвовать. Я в своих проектах всегда предпочитаю чистоту кода скорости. Зато можно отыграться на лучших по асимптотике алгоритмах верхнего уровня (пример для СУБД — лучше добавить интеллекта подсистеме оптимизации запросов, чем сэкономить чуть-чуть на реализации контейнеров/подсистемы управления памятью и при переносе на новую машину переписывать всю библиотеку с нуля). Имхо, машину помощнее купить все же дешевле, чем с нуля все переписывать.
>я проводил сравнение stl с собственной реализацией avl-деревьев.
Зачот!
>А в википедии в статье про rb-деревья пишут, что они лучше, а в статье про avl-деревья — что лучше они
В правильных статьях вроде как пишут, что
a) зависит от сценария использования (чего больше - вставок или поисков). В той же википедии это написано.
б) зависит от данных
Зачот!
>А в википедии в статье про rb-деревья пишут, что они лучше, а в статье про avl-деревья — что лучше они
В правильных статьях вроде как пишут, что
a) зависит от сценария использования (чего больше - вставок или поисков). В той же википедии это написано.
б) зависит от данных
a) зависит от сценария использования (чего больше - вставок или поисков). В той же википедии это написано.к сожалению, такого описания сценария явно не достаточно. С чего вдруг в rb-деревьях быстрее поиск (или вставка если глубина его больше ?
Скорее поверю каким-то вероятностым оценкам, наподобие такого: при энном распределении удаляемых элементов матожидание количества вращений в rb-деревьях составляем k% от его максимальной глубины, ну и то же самое с avl. Ну или оценку частоты балансировки при случайном добавлении элементов. Таких статей не видел, хотя, это было бы интересно.
>С чего вдруг в rb-деревьях быстрее поиск (или вставка если глубина его больше ?
При вставке критерий перебалансировки мягче.
При вставке критерий перебалансировки мягче.
При вставке критерий перебалансировки мягче.да, ступил, и там, и там O(1) перебалансировка. Но все равно чтобы найти место, куда вставить требуется O(h) операций, где h — глубина.
В общем я себе представляю так: выигрыш в rb-деревьях возможен лишь за счет того, что редко требуется перебалансировка при вставке и удалении элементов. Хотя сама вставка и удаление — занимают в среднем больше времени. Так что имеем стандартное противоборство: ленивость в rb-деревьях против "трудолюбивости" avl.
Легко сделать и итератор, и быстрый доступ к произвольному элементу; для этого надо знать мощность каждого поддерева.Без дополнительных затрат памяти порядка числа узлов итератор я себе плохо представляю. И про произвольный доступ тоже можно поподробнее.
Если не смотреть в исходники, Qt, версии 4.3.2 - удобная и приятная. (В исходники не смотрел).
Имеет всепоглощающие классы QList и QVector, работающие, как мне почему-то кажется, быстрее STL'ных.
Ещё понятная и удобная система SLOT - SIGNAL, которая, скорее всего, довольно сложная внутри, но сильно упрощает жизнь.
Да и в целом, бодяжить интерфейс на ней крайне просто, даже без QtDesigner.
Имеет всепоглощающие классы QList и QVector, работающие, как мне почему-то кажется, быстрее STL'ных.
Ещё понятная и удобная система SLOT - SIGNAL, которая, скорее всего, довольно сложная внутри, но сильно упрощает жизнь.
Да и в целом, бодяжить интерфейс на ней крайне просто, даже без QtDesigner.
Да, QT идельно подходит для быстрого и относительно безгеморрного создания приложеньица, где не так критично быстродействие. Но вот один знакомый по поводу QT-шных контейнеров отзывался весьма нелестно: в сравнении с STL они яко бы просасывают чуть ли не в разы.
И объясняется это пренебрежением или даже намеренным нежеланием создателей QT инлайнить методы плюс еще вездесущие попытки сделать thread-safety код. В результате очень много операций (например, чтение и запись элемента контейнера, модификация итератора) оказались замьютексованы, типа чтобы избежать коллизий, хотя _между_ любыми двумя операциями объекты по-прежнему потенциально подвержены коллизиям.
ИМХО, QT очень удобна в использовании (не надо много думать но слишком смещена в сторону времени выполнения и тем самым обладает медлительностью, свойственной для Java и C# runtime-сред. Хотя библеотека C++ как раз должна использовать широкие возможности метапрограммирования (шаблоны, перегрузка чтобы как можно больше оставлять на стадии компиляции.
И объясняется это пренебрежением или даже намеренным нежеланием создателей QT инлайнить методы плюс еще вездесущие попытки сделать thread-safety код. В результате очень много операций (например, чтение и запись элемента контейнера, модификация итератора) оказались замьютексованы, типа чтобы избежать коллизий, хотя _между_ любыми двумя операциями объекты по-прежнему потенциально подвержены коллизиям.
ИМХО, QT очень удобна в использовании (не надо много думать но слишком смещена в сторону времени выполнения и тем самым обладает медлительностью, свойственной для Java и C# runtime-сред. Хотя библеотека C++ как раз должна использовать широкие возможности метапрограммирования (шаблоны, перегрузка чтобы как можно больше оставлять на стадии компиляции.
Оставить комментарий
Missi4ka
Кому что нравится использовать наряду (читай: вместо) STL под плюсами? Интересуют, главным образом, достойные замены контейнерам, итераторам и алгоритмам. Плюс еще полезные штуки типа smart_pointer, shared_pointer, mutex и т. п. Какие есть плюсы и минусы у разных библиотек?Например, к минусам STL можно отнести:
1) отсутствие hash_set в числе контейнеров
2) извращенность vector<bool>
3) разная семантика операции [] у вектора и ассоциативных контейнеров (последние в случае отсутствия ключа делают вставку, vector - нет разное поведение медодов find и алоритма find на ассоц. контейнерах.
4) слабые ограничения на реализацию string (иногда используется reference counting, метод resize не всегда уменьшает размер).
Плюс STL - относительная простота и весьма неплохая эффективность реализации.
Особо хотелось бы услышать отзывы про QT и GTK. Библиотеки объектных языков типа C#, Java, Python пока оставим в стороне.