Здравствуйте, VladD2, Вы писали:
К>>Почему же? Зачем мне создавать подсписки? К>>Собственно быстрая сортировка не требует произвольного доступа.
VD>Не батенька. Это у тебя очередной пример использования указателей. Да еще и с явными ошибками (хотя бы ++i два раза за проход вызваются). А все эти (m+1) и обновления значений в итераторах...
Да ладно тебе придираться... Ну если хочешь, iterator m1 = m; ++m1; — так лучше?
Кроме прочего, я просто не стал расписывать фокусы с перестановкой узлов списка (там нужно тщательно последить за граничными условиями).
VD>К тому же ты попробуй ради хохмы отлать это дело и сравни скорость с классической быстрой сортировкой.
И пробовать не буду — слишком много приколов есть в реализации быстрой сортировки. Кстати, "классическая" — это самая тупая, т.е. в каком виде она была изобретена. А дальше начинаются моддинги и тюнинги.
Опять же, я показал контрпример к утверждению "для алгоритма быстрой сортировки нужен произвольный доступ". Не нужен. Точка.
К>> выбор точки разделителя как средней между минимумом и максимумом — не нуждаются в адресной арифметике; вполне можно обойтись ++.
VD>Да? И как ты себе это представляшь? Легкий перебор списка с целью вычисления его длинны и еще один ненавязчивый для поиска нужного значения? Или наш итератор все же позволяет произвольный доступ и предоставляет информацию о количестве элементов?
А какая разница, если мне на стадии выбора медианы или при разбиении всё равно нужно пробежаться по всем элементам. Глубоко фиолетово, произвольный там доступ или последовательный. Заодно и пересчитаю.
Выигрыш может быть (и будет) только за счёт дешевизны последовательного доступа (инкремент индекса/указателя вместо косвенностей).
К>>Другое дело, что для двусвязных списков есть более эффективные алгоритмы.
VD>Ага. Причем самый эффективный копирование в массив. Ну, если конечно объемы позволяют коллекцию в память поднять. Иначе конечно мердж-сортировка является самым правильным выбором.
VD>Кстати, о связанных саписках. Напдо признать, что с точки зрения скорости приложения они почему-то почти всегда проигрывают другим средствам. Не даром до второго фрэймворка МС даже не ввела такой примитив в состав коллекций. Да и с появлением этого дела как-то не тянет его писпользовать.
Это ты, наверное, на C# крепко подсел. Конечно, если коллекция указателей, то перетасовать её как нефиг делать. А массивы структур (с глубоким копированием) идут лесом.
В С++, напомню, это далеко не всегда так.
P.S.
Только не говори мне, что заниматься сортировкой тяжеловесных структур — дурное занятие.
Разумеется, дурное. Нужно вводить индексную коллекцию и сортировать уже её.
Тем не менее, тем не менее...
Здравствуйте, Павел Кузнецов, Вы писали:
>> Я вот пришел с С++.
ПК>Ты не считаешься, т.к. STL не использовал.
Ясно. Не кошерный значичь.
Вообще-то использовал. Но мало. В основном как основу для КОМ-мовских колекций. Но большую часть времени откровенно говоря я особо о ней и не знал. (Видмо к лучшему. Так как это дело сильно портит треминологию и дает друные привычки.) Учил С++ я по Страупотровской книжке 1991-года выпуска. Тогда только-только о шаблонах речь зашла. А уж о бусте и метапрограммировании речь даже и не шала. Самый навороченный компилятор Зортечь и то тянул их очень слабенько. А МС в то время вообще С клепал.
ПК>
Какаяр разница почему что-то появилось? Тут утверждалось что дескать дотнетные коллекции не тем боком проектировались. Как видишь они не помешали создать все что нужно и в довольно приличном виде.
Алгоритмы СТЛ тоже были навеяны функциональными языками. В которых, кстати, они реализуются намного чище и красивее. Просто кто-то был больше знаком с плюсами. Ну, тебе это знакомо.
Кстати, функциональный подход во втором Шарпе реализуется довольно прозрачно. Что нельзя сказать о плюсах. Так что еще бабушка на двое сказала на чем алгоритмы будут выглядеть естественнее и проще. Хотя честно сказать, мне больше нравится идея засовывания алгоритмов в итераторы нежели чисто функциональный подход.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Если человек признает свои ошибки, когда он неправ, – значит, он мудр.
Если человек признает свои ошибки, даже когда он прав, – значит, он
женат.
Народная мудрость
Просто, имхо, интересно.
> Тут утверждалось что дескать дотнетные коллекции не тем боком проектировались.
Не это утверждалось, а то, что при проектировании итераторов STL и энумераторов .Net преследовались различные цели, соответственно, и результаты различны. В частности, одним из выводов было, что энумераторы .Net мало для чего пригодны, кроме как для последовательного перебора элементов коллекции.
> Как видишь они не помешали создать все что нужно и в довольно приличном виде.
Мы все еще об итераторах/энумераторах? В Power Collections чаще используются сами коллекции, чем их энумераторы. Что как раз и подтверждает то, что энумераторы мало для чего подходят.
> Алгоритмы СТЛ тоже были навеяны функциональными языками. В которых, кстати, они реализуются намного чище и красивее. Просто кто-то был больше знаком с плюсами. Ну, тебе это знакомо.
Уф-ф-ф... Тебе бы все на личности переходить, да авторов концепций как-нибудь "опускать, вместо того чтобы по существу аргументы приводить. Исключительно просвещения для: Степанов сначала реализовал библиотеку алгоритмов и структур данных на Схеме, затем на Аде, и уж потом — на C++.
> Кстати, функциональный подход во втором Шарпе реализуется довольно прозрачно. Что нельзя сказать о плюсах.
Благодаря поддержке лямбда-функций (aka "анонимные делегаты"). Если введут что-нибудь в таком духе в C++, будет и в C++ с этим все хорошо. Так или иначе, чтобы была возможность писать алгоритмы обобщенно, без привязки к контейнеру, нужны некоторые абстракции, аналогичные итераторам STL. Можно их заменить на диапазоны, можно уточнить, разделяя индексацию и доступ к элементу и т.п. — суть от этого не меняется.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
VladD2,
> CS> Причем здесь индекс и итератор? Весь сыр бор как раз о том что итератор не должен иметь ничего общего с индексом. > > Общего не должен, но при реализации индекс там появится с очень большой вероятностью. Мы же ведь не про сфероконей речь ведем?
А в списке (связном)?
> CS>Загадка: в Java справедливо следующее: > > CS>Object a = Enum.next(); > CS>Object b = Enum.prev(); > CS>assert(a == b); // это true. > > CS>Так где находился Enum после next? > > Перешел вперед. Вернулся назад. Что же ты еще хотел получить? Хотя по мне так prev совершенно лишний.
c-smile в своем ответе выразился в некоторой степени иносказательно. Я спрошу конкретнее: ты уверен, что вопрос понял? Если Enum ходил вперед—назад, то почему значение, которое мы получали, одинаково на шаге 1 и 2? Значение индекса здесь, имхо, совершенно несущественно. Вопрос о том, на какой из элементов указывает энумератор в каждый из моментов времени.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
VladD2,
> ПК> В STL — именно набор концепций. Просто что-то назвать недостаточно, чтобы это что-то стало концепцией. Нужно это что-то еще и точно специфицировать. Без привязки к конкретном описанию "итератор" концепцией не является, а является просто неоднозначным словом. А вот, скажем, ForwardIterator — одна из таких концепций. Реализации — соответственно, в конкретных реализациях STL.
> Пашь, McSeem2 павильно сказал. Само название "итератор" подразумевает последовательный доступ (перебор). А итератор произвольного доступа — это глупость.
Это условности. Потоки (stream) тоже предполагают последовательный доступ, да еще и (потенциально) разрушающий. Что не мешает вводить в большинство классов, имеющих в названии слово stream, функции seek. Суть не в названиях, а в обозначаемых ими понятиях, и связи между ними. Естественно, удачное название лучше неудачного, если его удается подобрать.
> Как в прочем глупо использовать какие-то навороченные конструкции для произвольного доступа.
Причем здесь навороченные конструкции? Речь идет о введении абстракции, позволяющей описывать алгоритмы без привязки к контейнерам. Этой абстракцией и являются итераторы STL. Более простой в использовании конструкцией, обладающей более-менее теми же возможностями, вероятно, является (полу-)диапазон. "Более-менее" т.к. итераторы позволяют задать не только диапазон значений, но и позицию.
> Для этого достаточно одного оператора/метода и свойства/метода для того чтобы узнать длинну списка.
Задача определения длины списка в итераторах не нуждается. Речь идет о возможности однократной реализации алгоритмов (например, fill, find, count_if, sort, sort_heap, stable_sort, unique и т.п.). Если нет абстракции, позволяющей абстрагироваться от конкретного контейнера, то для каждого нового представления все эти алгоритмы нужно будет реализовывать заново.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, VladD2, Вы писали:
КЕ>>Во-1х имо выделенное неверно. Ты понимаешь под итератором вообще лишь некий минимальный интерфейс итератора. Думаю возникнет меньше терминологических споров, если называть эту сущность энумератором. А итератор — более широкое понятие.
VD>Итератор — это давно и хорошо известный паттерн проектирования. Называть его можно по разному суть от этого не меняется. А вот в С++ этот термин применен некорректно.
Единственное отличие кроме имен методов — STL-итератор не несет в себе знание о конце последовательности, но может быть сравнен с другим итератором, отмечающим конец. Мне это кажется разумным.
VD>Как впрочем и в C# 2.0. Там зачем-то итератором назвали реализацию того что в языке называется энумератором.
КЕ>>Во-2х имо логичнее такая иерархия: итератор потока — forward iterator — bidirectional iterator — random access iterator.
VD>Вот это и есть извращение. Ты iteration — это перебор, повторение и т.п. И само понятие перебора не допускает произвольный доступ.
Если понимать iteration как перебор в неопределенном порядке, то да, произвольный доступ будет извращением понятия iteration. Но на практике порядок перебора настолько часто имеет значение, что произвольный доступ совсем не кажется извращением iteration.
VD>Что да двунаправленных итераторов и т.п. тут не все так просто. Но можно точно сказать, что для самого паттерна и его применения это все не нужно.
Ничего сложного тут нет. Да и в святых Паттернах двунаправленность указана как возможное расширение.
Здравствуйте, VladD2, Вы писали:
К>>>В том-то и дело, что вот такая "аксиоматика" STL-итераторов с головой выдаёт в них указатели.
КЕ>>Это плохо?
VD>Естественно. Иначе давай называть телефон патефонном с возможностью разговора на растонянии.
Итератор произвольного доступа is a итератор, т.к. поддерживает все операции итератора. А телефон is not a патефон — он не принимает патефонные пластинки
VD>Да и сама концепия довольно непонятна, громоздка и требует кучи лишних действий (неудобна).
Наоборот, концепция очень наглядна для знакомых с указателями. Про кучу действий отчасти верно, но есть способы ее уменьшить.
Здравствуйте, alexeiz, Вы писали:
A>А вот по терминологии у тебя задвиг, это точно. Внушил себе, что итераторы могут быть только одного типа. Не видишь, что набор задач, в которых могут быть применены итераторы, гораздо шире, чем простое перечисление. http://en.wikipedia.org/wiki/Iterator_pattern
In object-oriented programming, an iterator is an object allowing one to sequence through all of the elements or parts contained in some other object, typically a container or list. An iterator is sometimes called a cursor, especially within the context of a database.
P.S.
Демагогия идет лесом. Попробуйте сосредоточиться на обсуждении предмета, а не личности собеседника.
И что тогда "дык"?
>> Тут утверждалось что дескать дотнетные коллекции не тем боком проектировались.
ПК>Не это утверждалось, а то, что при проектировании итераторов STL и энумераторов .Net преследовались различные цели, соответственно, и результаты различны.
А ну, да в дотнете цель была использование в фориче. А в СТЛ виликие дальновидные цели.
ПК>В частности, одним из выводов было, что энумераторы .Net мало для чего пригодны, кроме как для последовательного перебора элементов коллекции.
Вот именно. Выполняют свою роль. Чистая и логичная реализация паттерна итератор. Использовать удобно. Нет гор грязного кода... Ясен пень этого не достаточно.
ПК>Мы все еще об итераторах/энумераторах? В Power Collections чаще используются сами коллекции, чем их энумераторы. Что как раз и подтверждает то, что энумераторы мало для чего подходят.
Ерунду то не лепи. Там IEnumerable<T> — это самое часто используемый интерфейс. А остальные появляются только по мере необходимости, когда решаемая задача требует не итератора, а, например, индесного доступа. Ну, глупо, к примеру, озвращать индекс для IEnumerable<T>.
>> Алгоритмы СТЛ тоже были навеяны функциональными языками. В которых, кстати, они реализуются намного чище и красивее. Просто кто-то был больше знаком с плюсами. Ну, тебе это знакомо.
ПК>Уф-ф-ф... Тебе бы все на личности переходить,
Тебе в очередной раз мерешится.
ПК> да авторов концепций как-нибудь "опускать, вместо того чтобы по существу аргументы приводить. Исключительно просвещения для: Степанов сначала реализовал библиотеку алгоритмов и структур данных на Схеме, затем на Аде, и уж потом — на C++.
Я вообще-то говорил об авторе этих "Power Collections". "кто-то" — это про него. А намек как раз был именно на Степанова, который черпал вдохновение в ФЯ. Так что надо быть менее подозрительным.
>> Кстати, функциональный подход во втором Шарпе реализуется довольно прозрачно. Что нельзя сказать о плюсах.
ПК>Благодаря поддержке лямбда-функций (aka "анонимные делегаты").
Да, им. Но не только. Сами делегаты тоже важны. Да и без параметризации типов все это было бы не очень эффектно. А так получилось очень неплохо. Еще бы нечто вроде кортежей, выода типов, паттерн-матчинга, встроенной работы с диапазонами и было бы совсе клево.
ПК> Если введут что-нибудь в таком духе в C++, будет и в C++ с этим все хорошо.
Согласен. Но следующий стандарт в 2008 вроде? И похоже в него так ничего хорошешо и не введут. А ведь всего то нужно признать ошибки и ввести ссылку на методы и возможность обявлять анонимные методы.
ПК> Так или иначе, чтобы была возможность писать алгоритмы обобщенно, без привязки к контейнеру, нужны некоторые абстракции, аналогичные итераторам STL.
Согласен. Но выглядеть они могли бы и по рпиличнее. Хотя... Мне вот идеи встраивания в язык фич проде конструкторов списков больше нравится. При их наличии многие алгоритмы пишутся на раз самостоятельно.
ПК> Можно их заменить на диапазоны, можно уточнить, разделяя индексацию и доступ к элементу и т.п. — суть от этого не меняется.
Их нужно четко структурировать для начала. И дать нормальные названия. А то "радном эксес итератор" — это уже смешно. Ну, и очень не мешало бы устранить неверотяно длинный код появлящийся при их использовании и упростить их реалализацию. Это любому языку не помешало бы.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Кодт, Вы писали:
VD>>Кстати, о связанных саписках. Напдо признать, что с точки зрения скорости приложения они почему-то почти всегда проигрывают другим средствам. Не даром до второго фрэймворка МС даже не ввела такой примитив в состав коллекций. Да и с появлением этого дела как-то не тянет его писпользовать.
К>Это ты, наверное, на C# крепко подсел. Конечно, если коллекция указателей, то перетасовать её как нефиг делать. А массивы структур (с глубоким копированием) идут лесом. К>В С++, напомню, это далеко не всегда так.
Да нет, в чем то он прав. Во-первых действительно очень часто все равно приходится делать доступ по индексу (иногда, что самое неприятное, не сразу, а в процессе развития системы). И этот доступ по индексу мигом съедает все преимущества связанных списков. Во-вторых работа со связанными списками с точки зрения современных процессоров не очень удобна из-за существенно более высокой вероятности промаха в кеше данных.
> In object-oriented programming, an iterator is an object allowing one to sequence through all of the elements or parts contained in some other object, typically a container or list. An iterator is sometimes called a cursor, especially within the context of a database.
Это всего лишь википедия. Предлагаю сойтись на том, что СТЛ-итераторы не вполне объектно-ориентированные.
Также в контексте соседнего спора о дотнетных терминах, интересно, что они различают контейнер и список.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>O(n) при переборе элементов любого дерева (если порядок обхода не важен) получается элементарно, если в качестве представления выбрать классический список смежности.
Я незнаю, что ты имешь в виду под "список смежности". Но в любом случае это дополнительные расширения.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>А в списке (связном)?
Нет. Но он не один.
ПК>c-smile в своем ответе выразился в некоторой степени иносказательно. Я спрошу конкретнее: ты уверен, что вопрос понял? Если Enum ходил вперед—назад, то почему значение, которое мы получали, одинаково на шаге 1 и 2? Значение индекса здесь, имхо, совершенно несущественно. Вопрос о том, на какой из элементов указывает энумератор в каждый из моментов времени.
Понял. Не уверен. Я как-то с prev не связывался. Но с точки зрения next там именно переход, скажем так, c -1 и далее.
Я, как ты понимашь, больше с дотнетом вожусь. А в нем вообще нет prev. И все ОК. В остальном подходы схожи.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ну, то есть все же O(2 * n — 2). Я собственно об этом речь и вел.
Не понял, о чём ты вёл речь?
Ты сказал "переборе элементов дерева O(n) получить сложно (хотя в принципе можно...)".
Это значило, что "перебор дерева — как правило, больше O(n)" или, "как правило, меньше"? Или что-то совсем иное?
Я не представляю, как это может быть, чтобы перебор n элементов занимал меньше, чем O(n). Значит, больше.
Но это утверждение неверно: для многих реализаций деревьев перебор занимает гарантированно O(n). И алгоритмы там простейшие.
Здравствуйте, VladD2, Вы писали:
ПК>>O(n) при переборе элементов любого дерева (если порядок обхода не важен) получается элементарно, если в качестве представления выбрать классический список смежности.
VD>Я незнаю, что ты имешь в виду под "список смежности". Но в любом случае это дополнительные расширения.
Мы опять начали смешивать абстракции?
Если дерево как иерархическая структура (вложенные списки) — то за линейное время рекурсивно обходим.
Если дерево как граф — то опять линейное время.
Но для этого нам потребуется подходящая реализация этих абстракций.
Придумать заведомо хреновую реализацию — это мы завсегда успеем. А хорошие очевидны.
— для бинарного дерева — в каждом узле есть ссылки
— — вверх,вниз-влево,вниз-вправо (getParent, getLeft, getRight)
— для дерева произвольной арности
— — вверх,вниз,вправо (getParent, getFirstChild, getNextSibling)
Здравствуйте, Кодт, Вы писали:
К>Ты сказал "переборе элементов дерева O(n) получить сложно (хотя в принципе можно...)". К>Это значило, что "перебор дерева — как правило, больше O(n)" или, "как правило, меньше"? Или что-то совсем иное?
Больше естественно. Если нет оптимизаций, то приходится лазить вверх-вниз.
К>Я не представляю, как это может быть, чтобы перебор n элементов занимал меньше, чем O(n). Значит, больше. К>Но это утверждение неверно: для многих реализаций деревьев перебор занимает гарантированно O(n). И алгоритмы там простейшие.
Не для многих, а только для тех в которых где этого специально добивались. Самый быстрый вариант вообще сортированный массив.
И вообще, кроме скоростных характеристик еще есть время доступа. И для деревьев основанных на ссылках оно выше чем для массивов.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Или наш итератор все же позволяет произвольный доступ и предоставляет информацию о количестве элементов?
Перекуём баги на фичи!
