Здравствуйте, samius, Вы писали:
PD>>Я правильно понял, что здесь создается новый объект, содержащий элементы двух последовательностей ? Не итератор или что-то еще, а именно объект ?
S>Да, это объект-итератор, котрый пройдет по элементам двух последовательностей, но он не содержит их элементов, а только лишь умеет ходить по ним аки итератор из STL.
Гм. Итератор map из STL — это нечто иное, там BST. Это раз. А во-вторых, там цикл
Но дело не в этом. Я никак не могу понять, каким образом можно итерировать по дереву, не создав промежуточных структур, причем массовых. Ну хорошо, элементы не копируются. Но пройти дерево — надо или стек заводить, или рекурсию, других способов вроде нет. В любом случае это дополнительная память. Что именно здесь делается ?
S>Этот алгоритм не может работать на памяти O(1), т.к. он юзает рекурсию, которая не приводима к хвостовой оптимизации. В точности ему потребуется память соразмерная высоте дерева, т.е. O(log N) в среднем и O(N) в худшем случае.
Не совсем верно. Память, соразмерная высоте дерева, понадобится, само собой, но не из элементов дерева, а только из указателей (ссылок). Тут то же самое, что в QuickSort. Кстати, если дерево сбалансированное, то точно O(log N).
>Разница лишь в том, что этот вариант работает лишь на стэке, а вариант с объектами-итераторами просит еще и выделений в куче. Впрочем, возможно переписать реализацию IEnumerable в структурах и итераторы лягут полностью на стэк (потребуется немного другая форма метода Walk с двумя дженерик параметрами).
Резюмирую. Ты утверждаешь, что твой LinQ-вариант при его "ассемблерной" реализации делает обход дерева, создавая при этом не более чем log(N) элементов размером не более 4(8), не копируя данные и не проходя их дважды ? Иными словами, он логически эквивалентен императивному ?
S>Самое важное отличие от реализации с функцией высшего порядка в том, что для MaxElem, SearchElem и т.п. придется писать новый метод обхода дерева каждый раз. В то время как обход дерева через ФВП Walk позволяет привести его к линейному виду и применить стандартный набор LINQ методов для работы с последовательностями. S>Открою секрет, LINQ здесь используется только как набор высокоуровневых методов Select + Min из нэймспейса System.Linq. Т.е. сказать что обойти дерево можно на LINQ = немного слукавить. Более уместно здесь сказать что выделение паттерна обхода дерева в высокоуровневый метод высшего порядка позволяет свести задачу обхода дерева к обходу последовательности и применить Min из LINQ-а.
Так создается тут последовательность или нет ? Физически она есть или нет ? Что-то я уж совсем запутался.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>>>Я правильно понял, что здесь создается новый объект, содержащий элементы двух последовательностей ? Не итератор или что-то еще, а именно объект ?
S>>Да, это объект-итератор, котрый пройдет по элементам двух последовательностей, но он не содержит их элементов, а только лишь умеет ходить по ним аки итератор из STL.
PD>Гм. Итератор map из STL — это нечто иное, там BST. Это раз. А во-вторых, там цикл
Итератор map из STL — действительно нечто другое.
PD>Но дело не в этом. Я никак не могу понять, каким образом можно итерировать по дереву, не создав промежуточных структур, причем массовых. Ну хорошо, элементы не копируются. Но пройти дерево — надо или стек заводить, или рекурсию, других способов вроде нет. В любом случае это дополнительная память. Что именно здесь делается ?
Используется стек, как и в случае MinElem.
И немного используется куча для создания последовательности (об этом ниже).
S>>Этот алгоритм не может работать на памяти O(1), т.к. он юзает рекурсию, которая не приводима к хвостовой оптимизации. В точности ему потребуется память соразмерная высоте дерева, т.е. O(log N) в среднем и O(N) в худшем случае.
PD>Не совсем верно. Память, соразмерная высоте дерева, понадобится, само собой, но не из элементов дерева, а только из указателей (ссылок). Тут то же самое, что в QuickSort. Кстати, если дерево сбалансированное, то точно O(log N).
Про сбалансированное дерево мы не говорили, потому я все время оговариваюсь что мерию O(x) в высоте дерева.
Элементы дерева я не копирую, потому память под элементы дерева мне не нужна.
>>Разница лишь в том, что этот вариант работает лишь на стэке, а вариант с объектами-итераторами просит еще и выделений в куче. Впрочем, возможно переписать реализацию IEnumerable в структурах и итераторы лягут полностью на стэк (потребуется немного другая форма метода Walk с двумя дженерик параметрами).
PD>Резюмирую. Ты утверждаешь, что твой LinQ-вариант при его "ассемблерной" реализации делает обход дерева, создавая при этом не более чем log(N) элементов размером не более 4(8),
Элементы он не создает. Создаются лишь итераторы, которые при необходимости можно расположить в стеке. Размер итератора вот только побольше 4х байт, но абсолютно точно не зависит ни от размера дерева ни от размера элемента дерева, т.е. O(C).
PD>не копируя данные и не проходя их дважды ?
да, не копируя и не проходя их дважды
PD>Иными словами, он логически эквивалентен императивному ?
Абсолютно логически эквивалентен и устроен по тому же принципу — ПВГ. Только лишь абстрагирован от выбора следующего шага, так что я могу его параметризовать способом обхода (по левым детям, по правым, по n-ым, по всем, через 1 и как угодно)
PD>Так создается тут последовательность или нет ? Физически она есть или нет ? Что-то я уж совсем запутался.
Последовательность как контейнер НЕ создается. Последовательность как способ обхода — создается.
Мы можем по ней пройти через foreach — в этом случае это лишь проход с помощью итератора, мы можем ее фильтровать, преобразовывать, группировать и т.п. Но лишь когда мы сделаем new List<Node>(seq), вот тогда создастся новый контейнер список, который вберет в себя последовательность.
var array = new int[]{1, 2, 3} — контейнер и последовательность.
array.Where(n => n % 2 == 0) — последовательность но не контейнер. Да, она занимает место в памяти как объект, имеющий размер O(C), и при этом не содержит ни одного элемента из массива в своей памяти. Но мы можем итерировать через эту последовтельность и в ней будет 1 элемент. Так что она "содержит" элементы не содержа их физически.
D>> var childValues = Values(root.Left).Concat(Values(root.Right)); PD>Я правильно понял, что здесь создается новый объект, содержащий элементы двух последовательностей ? Не итератор или что-то еще, а именно объект ?
Нет. Здесь создается именно итератор. Какой-либо коллекции, содержащей объекты дерева или ссылки на них, не создается.
Как выглядит простейшая реализация Concat?
public IEnumerable<T> Concat<T>(this IEnumerable<T> first, IEnumerable<T> second)
{
foreach(var i in first) yield return i;
foreach(var i in second) yield return i;
}
Никакой новой коллекции не создается, итератор просто выдает сначала элементы одной последовательности, а потом — второй. У пользователя итератора есть полная иллюзия, что он работает с одной коллекцией, содержащей элементы обоих операндов. На самом деле он неявно опрашивает обе коллекции.
Здравствуйте, Dufrenite, Вы писали:
D>Здравствуйте, Lloyd, Вы писали:
L>>А откуда "* log(N)" берется?
D>Здесь тонкий момент, я сам не сразу заметил. D>Фактически, енумератор, возвращающий листовой элемент, представляет собой связный список енумераторов (это можно увидеть декомпилировав код), длиной с глубину просмотра, а это log(N). Поэтому, при перемещении к следующему элементу, приходится проходить весь список енумераторов. D>Отсюда и получаем N * log(N).
Енумераторы действительно выстраиваются в цепочку, и длина этой цепочки соответствует высоте дерва.
Однако, справедливо считать что сложность ПВГ O(N), хотя глубина рекурсии там тоже будет соответствовать высоте дерева. Предлагаю не учитывать стоимость вызова по цепочке енумераторов в алгоритмической оценке потому как его вклад будет соразмерен рекурсивному вызову, который не учитывается.
S>Элементы дерева я не копирую, потому память под элементы дерева мне не нужна.
OK, с этим ясно.
S>Элементы он не создает. Создаются лишь итераторы, которые при необходимости можно расположить в стеке. Размер итератора вот только побольше 4х байт, но абсолютно точно не зависит ни от размера дерева ни от размера элемента дерева, т.е. O(C).
Вот это я все же не понимаю. Ладно, оставим LinQ в покое. Проитерируй мне это несчастное дерево императивным путем.
Я-то, грешный, прошел его рекурсией. Мне не надо извне его уметь следующий элемент получить, я это только внутри него самого делаю. И итератора там нет. Я вообще понятие "следующий" явно не использую. А вот попроси ты меня
написать, и все будет хуже. Это не список и не массив, тут позицией или индексом не обойдешься. Тут мне придется внутри этого итератора стек хранить, да как бы не что-то еще. Скорее всего придется еще поле Parent добавить, иначе как к нему возвращаться ?
PD>>не копируя данные и не проходя их дважды ? S>да, не копируя и не проходя их дважды
PD>>Иными словами, он логически эквивалентен императивному ? S>Абсолютно логически эквивалентен и устроен по тому же принципу — ПВГ. Только лишь абстрагирован от выбора следующего шага, так что я могу его параметризовать способом обхода (по левым детям, по правым, по n-ым, по всем, через 1 и как угодно)
PD>>Так создается тут последовательность или нет ? Физически она есть или нет ? Что-то я уж совсем запутался.
S>Последовательность как контейнер НЕ создается. Последовательность как способ обхода — создается.
Вот это я и не понимаю. Можно создать последовательность как способ обхода для массива — i++. Для списка p=p.next. Тут никакие дополнительные структуры не требуются. А в дереве это не получится. Так что твоя последовательность как способ обхода есть по сути дела некая управляющая структура над эти деревом. И как тут может быть O(C) — не понимаю, если в императивном O(log N). К примеру, я мог бы обойти это дерево как написал и выложить все указатели в массив. После этого пройти итератором будет несложно, но это не решение.
S>Мы можем по ней пройти через foreach
Вот-вот. each что ? Управляющий элемент для каждого элемента дерева ?
>- в этом случае это лишь проход с помощью итератора, мы можем ее фильтровать, преобразовывать, группировать и т.п. Но лишь когда мы сделаем new List<Node>(seq), вот тогда создастся новый контейнер список, который вберет в себя последовательность.
S>var array = new int[]{1, 2, 3} — контейнер и последовательность. S>array.Where(n => n % 2 == 0) — последовательность но не контейнер. Да, она занимает место в памяти как объект, имеющий размер O(C), и при этом не содержит ни одного элемента из массива в своей памяти. Но мы можем итерировать через эту последовтельность и в ней будет 1 элемент. Так что она "содержит" элементы не содержа их физически.
Это все слова. Да, я понял, что Where тут не контейнер. Отлично. Но начнешь итерировать — будет там ++ где-то внутри какого-то регистра или индекса, и не надо никаких новых байт для этого. Но в дереве же такое невозможно!
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
S>>Элементы он не создает. Создаются лишь итераторы, которые при необходимости можно расположить в стеке. Размер итератора вот только побольше 4х байт, но абсолютно точно не зависит ни от размера дерева ни от размера элемента дерева, т.е. O(C).
PD>Вот это я все же не понимаю. Ладно, оставим LinQ в покое.
Да это не LINQ вовсе. Из LINQ-а там только Concat, который легко реализуется на yield return, который в свою очередь генерирует код конечного автомата для реализации IEnumerator<T>.
PD>Проитерируй мне это несчастное дерево императивным путем.
Да легко. Вместо yield return будет callback и всего лишь.
Здесь я слил специфичный для Node<T> селектор с обходом в единое целое чтобы полностью избавиться от IEnumerable. Алгоритм остался идентичным, только стал более низкоуровневый.
PD>Я-то, грешный, прошел его рекурсией. Мне не надо извне его уметь следующий элемент получить, я это только внутри него самого делаю. И итератора там нет. Я вообще понятие "следующий" явно не использую. А вот попроси ты меня
PD>root = BuildTree(); PD>tree_iterator te = tree_iterator(root); PD>for(t = te.begin; t!=t.end; t++)
PD>написать, и все будет хуже. Это не список и не массив, тут позицией или индексом не обойдешься. Тут мне придется внутри этого итератора стек хранить, да как бы не что-то еще. Скорее всего придется еще поле Parent добавить, иначе как к нему возвращаться ?
В случае C# (достаточно 2.0) это все на раз-два реализуется с помощью yield return. Стэк перетекает в цепочку связанных перечислителей, Parent не нужен. Можно было бы и на C# 1.0, но пришлось бы вместо yield return реализовывать IEnumerator вручную.
S>>Последовательность как контейнер НЕ создается. Последовательность как способ обхода — создается.
PD>Вот это я и не понимаю. Можно создать последовательность как способ обхода для массива — i++. Для списка p=p.next. Тут никакие дополнительные структуры не требуются.
IEnumerator/IEnumerable — высокоуровневая абстракция над i++ и p=p.next
PD>А в дереве это не получится.
Получится в виде комбинации перечислителей.
PD>Так что твоя последовательность как способ обхода есть по сути дела некая управляющая структура над эти деревом. И как тут может быть O(C) — не понимаю, если в императивном O(log N).
Каждый из перечислителей занимает O(C) места. Но их комбинация будет O(log N). Т.е. ровно как и в императиве. Просто стек перерождается в другую структуру, которая полностью ему соответствует с тем лишь отличием, что будет работать отложенно, а не сразу.
PD>К примеру, я мог бы обойти это дерево как написал и выложить все указатели в массив. После этого пройти итератором будет несложно, но это не решение.
Согласен, это другое решение. Вместо этого можно было воспользоваться callback-ом для поиска минимального элемента без копирования элементов в какой-либо контейнер.
S>>Мы можем по ней пройти через foreach
PD>Вот-вот. each что ? Управляющий элемент для каждого элемента дерева ?
Each — это подузлы. Но управляющая структура все-же создается при прохождении в foreach. См. IEnumerable/IEnumerator.
PD>Это все слова. Да, я понял, что Where тут не контейнер. Отлично. Но начнешь итерировать — будет там ++ где-то внутри какого-то регистра или индекса, и не надо никаких новых байт для этого. Но в дереве же такое невозможно!
В дереве во время итерации по внешней последовательности, полученной в результате Walk метода, будут создаваться новые итераторы по мере погружения в дерево.
Если виртуально собрать все итераторы, созданные и собранные сборщиком во время обхода дерева, то да, их структура повторит дерево полностью. Однако в каждый конкретный момент активны только те итераторы, которые выстроены вдоль текущего пути в дереве. Структура активных энумераторов будет абсолютно соответствовать стэку в императивном подходе, который в каждый момент времени хранит лишь узлы вдоль текущего пути, а за все время проходит дерево целиком.
Здравствуйте, samius, Вы писали: S>В дереве во время итерации по внешней последовательности, полученной в результате Walk метода, будут создаваться новые итераторы по мере погружения в дерево. S>Если виртуально собрать все итераторы, созданные и собранные сборщиком во время обхода дерева, то да, их структура повторит дерево полностью. Однако в каждый конкретный момент активны только те итераторы, которые выстроены вдоль текущего пути в дереве. Структура активных энумераторов будет абсолютно соответствовать стэку в императивном подходе, который в каждый момент времени хранит лишь узлы вдоль текущего пути, а за все время проходит дерево целиком.
В общем, если я тебя правильно понял, ты утверждаешь следующее. В ходе прохода по дереву при погружении будут создаваться новые экземпляры некоего класса под названием "итератор" (и уничтожались бы они тоже при подъеме, если бы мы не в .NET, а в C++ были). Логически набор этих экземпляров эквивалентен стеку в классическом алгоритме. Правильно ?
Остается один вопрос — а что это такое в данном случае — итератор ? Нет, я не спрашиваю, что такое итератор вообще, я хочу понять. что он есть в данном конкретном случае. Все же эффективнее стека найти структуру данных сложно.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>В общем, если я тебя правильно понял, ты утверждаешь следующее. В ходе прохода по дереву при погружении будут создаваться новые экземпляры некоего класса под названием "итератор" (и уничтожались бы они тоже при подъеме, если бы мы не в .NET, а в C++ были). Логически набор этих экземпляров эквивалентен стеку в классическом алгоритме. Правильно ?
Да, правильно и очень лаконично.
PD>Остается один вопрос — а что это такое в данном случае — итератор ? Нет, я не спрашиваю, что такое итератор вообще, я хочу понять. что он есть в данном конкретном случае.
В данном конкретном случае итератор (точнее их комбинирование) есть мост от дерева к методам, работающим с итераторами.
PD>Все же эффективнее стека найти структуру данных сложно.
В общем случае я не могу согласиться с таким утверждением, все зависит от задачи. Например, факториал можно посчитать с помощью стека (callstack), а можно с помощью аккумулятора.
Но в случае дерева — соглашусь. Реализация на стеке будет эффективнее чем на комбинировании итераторов (хоть и алгоритмически эквивалентна). Зато приведение дерева к последовательности позволяет задействовать весь арсенал методов LINQ-а (выборка/маппирование, фильтрация, группировка, упорядочивание, склеивание, теоретико-множественные операции Intersect+Union+Except и т.п.).
PD>>Остается один вопрос — а что это такое в данном случае — итератор ? Нет, я не спрашиваю, что такое итератор вообще, я хочу понять. что он есть в данном конкретном случае. S>В данном конкретном случае итератор (точнее их комбинирование) есть мост от дерева к методам, работающим с итераторами.
Не то. Я имел в виду, что он реально содержит. Ссылки на Left-Right или что-то еще ?
Кстати, дурацкий вопрос. А не существует ли компиляции с LinQ на императивный код ? . Я не прошу эффективно это сделать и не для productive. Пусть хоть псевдокод. Просто хочется понять, что же там делается. Я посмотрел ассемблер — там не скоро разберешься, сплошные call.
PD>>Все же эффективнее стека найти структуру данных сложно. S>В общем случае я не могу согласиться с таким утверждением, все зависит от задачи. Например, факториал можно посчитать с помощью стека (callstack), а можно с помощью аккумулятора.
Я неточно выразился. Я хотел сказать, что структуру данных "стек" заменить на более простую данных нелегко. Массив разве что. А ты привел пример, когда "массовую" структуру данных можно вообще выкинуть.
S>Но в случае дерева — соглашусь. Реализация на стеке будет эффективнее чем на комбинировании итераторов (хоть и алгоритмически эквивалентна). Зато приведение дерева к последовательности позволяет задействовать весь арсенал методов LINQ-а (выборка/маппирование, фильтрация, группировка, упорядочивание, склеивание, теоретико-множественные операции Intersect+Union+Except и т.п.).
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
S>>В данном конкретном случае итератор (точнее их комбинирование) есть мост от дерева к методам, работающим с итераторами.
PD>Не то. Я имел в виду, что он реально содержит. Ссылки на Left-Right или что-то еще ?
Итератор содержит физическую ссылку на узел дерева, потом во время работы щупает наличие Left/Right узлов и возвращает их (но хранит только один узел).
PD>Кстати, дурацкий вопрос. А не существует ли компиляции с LinQ на императивный код ? . Я не прошу эффективно это сделать и не для productive. Пусть хоть псевдокод.
Не думаю. У LINQ чисто функциональная природа.
PD>Просто хочется понять, что же там делается. Я посмотрел ассемблер — там не скоро разберешься, сплошные call.
Начать понимание лучше всего с интерфейсов IEnumerable/IEnumerator и ручной их реализации для примитивных коллекций типа ArrayList. Reflector поможет. Потом разобраться с конструкцией yield return и генерацией компилятором соответствующего конечного автомата в реализации IEnumerator<T>. MSDN + прототип на C# + Рефлектор.
После этого станет прозрачно устройство LINQ через Рефлектор.
PD>Спасибо за дискуссию.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Спасибо. Вот именно это я и хотел узнать — выделено выше. У меня было то же ощущение — что LinQ (как и его духовный предок SQL) предназначен для обработки линейных структур (в общем понимании этого слова).
Очень советую по ближе познакомиться с Лиспом. Там все типы данных — списки. И при этом есть и хэш-таблицы, и деревья.
PD>Для структур нелинейного характера (деревья, графы и т.д.) он, как мне кажется, не слишком подходит.
Любое дерево в конечном итоге — это набор элементов. Рано или поздно тебе понадобиться обработать их все. И тут линк будет к стати.
Кроме того для деревьев и хэш-таблиц можно определить методы-расширения и использовать линк извлекая выгоду из индексированного поиска.
PD>Хотя samius и Dufrenite пытаются меня убедить в обратном. Почитай эту часть дискуссии, она еще не кончена, можешь там высказаться.
У меня складывается впечатление, что ты все же не хочешь разобраться, а просто ищешь подтверждение уже имеющемуся убеждению. Увы расстрою тебя. Я так же как они считаю, что линк, как и функциональный стиль, удобен и при работе с хэш-таблицами и деревьями. Конечно не всегда линк тут будет уместен, но если при работе с деревом у тебя встречается цикл, ты смело можешь использовать вместо него линк.
PD>И второе, это уже вопрос. Если речь идет о запросе — ладно. А если не о запросе ? Я, может, ошибаюсь опять, но вроде бы LinQ — это функциональное программирование. А оно позиционируется как альтернатива императивному. Если альтернатива — будьте добры обеспечить мне возможность сделать все, что я там могу сделать, иначе что же это за альтернатива! А если это только добавление — тогда уж так и будем говорить.
Дело в том, что когда речь идет об обработке штучных объектов, то функциональное программирование мало отличается от императивного. В ФП предлагается вместо изменений уже существующих объектов вводить новые копируя в них информацию из старых и меняя нужные подэлементы. Но по сути тут ничего нового нет, так как операции и так минимальны.
По сути все преимущества ФП которые дает линк — это приемущества вызванные использованием функций высшего порядка. Другими словами — это возможность более детальной декомпозиции кода путем вынесения мелких алгоритмов в отдельные функции и настройки их с помощью лямбд (т.е. еще более мелких функций передаваемых в качестве параметров).
Линк — это в первую очередь библиотека таких фукнций высшего порядка. Они в основно предназначены для работы со последовательностями (т.е. наборами данных). Но деревья и хэш-таблицы — это тоже разновидность последовательности. Кроме того сам подход принятый в ФП позволяет точно так же создавать свои "мелкие алгоритмы". Это позволяет делать код более высокоуровневым и не содержащим дублирование мелких элементов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Очень советую по ближе познакомиться с Лиспом. Там все типы данных — списки. И при этом есть и хэш-таблицы, и деревья.
И без Лиспа можно сказать, что почти все структуры данных можно моделировать на базе других структур. Вопрос не в этом, а в том, насколько это рационально.
PD>>Для структур нелинейного характера (деревья, графы и т.д.) он, как мне кажется, не слишком подходит.
VD>Любое дерево в конечном итоге — это набор элементов. Рано или поздно тебе понадобиться обработать их все. И тут линк будет к стати.
Мне совсем не обязательно нужно обработать их все. Даже банальный Search в BST просматривает только Log N. Впрочем, его мы уже обсудили, там вообще проход по списку, а не по дереву. Но и в других случаях обработка всех не нужна. Впрочем, это не так важно.
VD>У меня складывается впечатление, что ты все же не хочешь разобраться, а просто ищешь подтверждение уже имеющемуся убеждению.
Да нет у меня насчет LinQ никаких убеждений, кроме того, что это в несколько раз медленнее. Но это я здесь не обсуждал.
>Увы расстрою тебя. Я так же как они считаю, что линк, как и функциональный стиль, удобен и при работе с хэш-таблицами и деревьями. Конечно не всегда линк тут будет уместен, но если при работе с деревом у тебя встречается цикл, ты смело можешь использовать вместо него линк.
VD>Дело в том, что когда речь идет об обработке штучных объектов, то функциональное программирование мало отличается от императивного. В ФП предлагается вместо изменений уже существующих объектов вводить новые копируя в них информацию из старых и меняя нужные подэлементы. Но по сути тут ничего нового нет, так как операции и так минимальны.
А все же, можешь что-то сказать насчет SearchAndInsert в BST ? То есть вроде как запрос, но в самый интересный момент он превращается во вставку, тут же, по ходу действия, а потом опять в запрос (при отсутствии вставить и вернуть) ? Вариант с, как ты пишешь, "вводить новые копируя в них информацию из старых и меняя нужные подэлементы", тут вроде как не проходит.
VD>По сути все преимущества ФП которые дает линк — это приемущества вызванные использованием функций высшего порядка. Другими словами — это возможность более детальной декомпозиции кода путем вынесения мелких алгоритмов в отдельные функции и настройки их с помощью лямбд (т.е. еще более мелких функций передаваемых в качестве параметров).
Хм... Ну ладно. Хотя вроде как выносить мелкие алгоритмы в отдельные функции мы и так умели давно. И даже передавать им в качестве параметров иные функции, хоть и не лямбды.
VD>Линк — это в первую очередь библиотека таких фукнций высшего порядка. Они в основно предназначены для работы со последовательностями (т.е. наборами данных). Но деревья и хэш-таблицы — это тоже разновидность последовательности.
ИМХО все же дерево — это дерево, а не последовательность. Линейный и разветвленные структуры — это все же не одно и то же, принципиально. Так следующим шагом ты и граф в последовательность превратишь Конечно, я говорю о самой структуре, а не о результате ее сериализации.
Здравствуйте, samius, Вы писали:
S>Однако, справедливо считать что сложность ПВГ O(N), хотя глубина рекурсии там тоже будет соответствовать высоте дерева. Предлагаю не учитывать стоимость вызова по цепочке енумераторов в алгоритмической оценке потому как его вклад будет соразмерен рекурсивному вызову, который не учитывается.
Мы можем учитывать или не учитывать проход по цепочке енумераторов, но я больше чем уверен, что время выполнения алгоритма будет расти по закону N * log(N), так как наиболее существенным в данном случае является вызов метода MoveNext(), а количество этих вызовов растет как раз по этому закону.
Этот факт как раз подтверждает тезис о том, что за удобство частенько приходится чем-то расплачиваться.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Но дело не в этом. Я никак не могу понять, каким образом можно итерировать по дереву, не создав промежуточных структур, причем массовых. Ну хорошо, элементы не копируются. Но пройти дерево — надо или стек заводить, или рекурсию, других способов вроде нет. В любом случае это дополнительная память. Что именно здесь делается ?
Для понимания того, что происходит в высокоуровневом коде удобно использовать Рефлектор.
Вот декомпилированный код класса, возвращаемого функцией Values():
[CompilerGenerated]
private sealed class <Values>d__0 : IEnumerable<int>, IEnumerable, IEnumerator<int>, IEnumerator, IDisposable
{
// Fieldsprivate int <>1__state;
private int <>2__current;
public Program.Node <>3__root;
public IEnumerator<int> <>7__wrap3;
private int <>l__initialThreadId;
public IEnumerable<int> <childValues>5__1;
public int <value>5__2;
public Program.Node root;
// Methods
[DebuggerHidden]
public <Values>d__0(int <>1__state)
{
this.<>1__state = <>1__state;
this.<>l__initialThreadId = Thread.CurrentThread.ManagedThreadId;
}
private void <>m__Finally4()
{
this.<>1__state = -1;
if (this.<>7__wrap3 != null)
{
this.<>7__wrap3.Dispose();
}
}
private bool MoveNext()
{
try
{
switch (this.<>1__state)
{
case 0:
this.<>1__state = -1;
if (object.ReferenceEquals(this.root, null))
{
break;
}
this.<>2__current = this.root.Value;
this.<>1__state = 1;
return true;
case 1:
this.<>1__state = -1;
this.<childValues>5__1 = Program.Values(this.root.Left).Concat<int>(Program.Values(this.root.Right));
this.<>7__wrap3 = this.<childValues>5__1.GetEnumerator();
this.<>1__state = 2;
while (this.<>7__wrap3.MoveNext())
{
this.<value>5__2 = this.<>7__wrap3.Current;
this.<>2__current = this.<value>5__2;
this.<>1__state = 3;
return true;
Label_00DE:
this.<>1__state = 2;
}
this.<>m__Finally4();
break;
case 3:
goto Label_00DE;
}
return false;
}
fault
{
this.System.IDisposable.Dispose();
}
}
[DebuggerHidden]
IEnumerator<int> IEnumerable<int>.GetEnumerator()
{
Program.<Values>d__0 d__;
if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
{
this.<>1__state = 0;
d__ = this;
}
else
{
d__ = new Program.<Values>d__0(0);
}
d__.root = this.<>3__root;
return d__;
}
[DebuggerHidden]
IEnumerator IEnumerable.GetEnumerator()
{
return this.System.Collections.Generic.IEnumerable<System.Int32>.GetEnumerator();
}
[DebuggerHidden]
void IEnumerator.Reset()
{
throw new NotSupportedException();
}
void IDisposable.Dispose()
{
switch (this.<>1__state)
{
case 2:
case 3:
break;
default:
break;
try
{
}
finally
{
this.<>m__Finally4();
}
break;
}
}
// Propertiesint IEnumerator<int>.Current
{
[DebuggerHidden]
get
{
return this.<>2__current;
}
}
object IEnumerator.Current
{
[DebuggerHidden]
get
{
return this.<>2__current;
}
}
}
Из этого кода видно, что енумератор содержит поле <>7__wrap3, которое фактически является ссылкой на енумератор следующего уровня. Получается, действительно, некая разновидность стека.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Мне совсем не обязательно нужно обработать их все.
Это вопрос взглядов на алгоритмы.
PD>Даже банальный Search в BST просматривает только Log N. Впрочем, его мы уже обсудили, там вообще проход по списку, а не по дереву. Но и в других случаях обработка всех не нужна. Впрочем, это не так важно.
Дык, а что нужно? Обычно нужно найти некоторые элементы отвечающие критерию. Для этого можно воспользоваться теми же методами Where или First. Ну, а чтобы они не делали полный перебор написать специализированную версию использующую поиск по ключу.
PD>А все же, можешь что-то сказать насчет SearchAndInsert в BST ?
Таких методов нет ни в одной дотной дотнетной коллекции, так что сказать про него я ничего не могу.
Но могу сказать, что ты мыслишь одной записью (так скажем). Ты не думаешь в терминах преобразований, а ФП рассчитан как раз на такое мышление.
Когда кто-то использует функциональный стиль, то он вместо возни с одним элементов отчирает их группу и вдет работу с ней. При этом отобранная группа обычно помещается в новую коллекцию.
PD> То есть вроде как запрос, но в самый интересный момент он превращается во вставку, тут же, по ходу действия, а потом опять в запрос (при отсутствии вставить и вернуть) ? Вариант с, как ты пишешь, "вводить новые копируя в них информацию из старых и меняя нужные подэлементы", тут вроде как не проходит.
Тут никаких запросов нет. Это вообще какой-то изврат — тандем двух методов. Причем методов (по всей видимости) работающих с отдельными элементами. А тут линк не к чему. Линк он нужен чтобы не возиться с отдельными элементами, а работать с их группами.
PD>Хм... Ну ладно. Хотя вроде как выносить мелкие алгоритмы в отдельные функции мы и так умели давно. И даже передавать им в качестве параметров иные функции, хоть и не лямбды.
Ну, значит ты давно пользовался ФП не подозревая об этом. Хотя более правдоподобным выглядит предположение о том, что ты преувеличиваешь.
Функцию ты может и мог передать, но без замыканий толку от этого не много. Ведь для вынесения алгоритма уровня цикла в отдельную функцию нужно в эту функцию передавать контекст вычислений. А без замыканий это сделать невозможно.
PD>ИМХО все же дерево — это дерево, а не последовательность. Линейный и разветвленные структуры — это все же не одно и то же, принципиально. Так следующим шагом ты и граф в последовательность превратишь Конечно, я говорю о самой структуре, а не о результате ее сериализации.
Ну, ты уж как-то давай сам решай. Или ты задаешь вопросы и получаешь ответы, или ты уже сам все решил, но тогда не стоит задавать вопросы.
Твое ИМПХО базируется на старых привычках. У меня было тоже самое, но я сумел перестроиться. Попробуй и ты. Не выйдет, значит и дальше ничего в линке не будешь видеть. В принципе не проблема. На циклах тоже можно программировать. Несколько медленнее конечно, но не смертельно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Dufrenite, Вы писали:
D>Мы можем учитывать или не учитывать проход по цепочке енумераторов, но я больше чем уверен, что время выполнения алгоритма будет расти по закону N * log(N), так как наиболее существенным в данном случае является вызов метода MoveNext(), а количество этих вызовов растет как раз по этому закону.
Возможно так и будет при ОЧЕНЬ большой глубине дерева порядка от нескольких миллионов элементов. А в таком случае имеет смысл задуматься а стоит ли вообще использовать LINQ, если время выполнения существенно...
D>Этот факт как раз подтверждает тезис о том, что за удобство частенько приходится чем-то расплачиваться.
В программировании довольно часто приходится расплачиваться производительностью за удобство и наоборот. Но гораздо лучше когда высокоуровневые средства есть под рукой, чем их нет. Тогда есть выбор, использовать их или нет в зависимости от ситуации.
Здравствуйте, samius, Вы писали:
S>А в таком случае имеет смысл задуматься а стоит ли вообще использовать LINQ, если время выполнения существенно...
В большинстве случаев такая сложность вполне приемлема. Например, если в последовательности преобразований есть сортировка, то сложность будет N * log(N).
S>В программировании довольно часто приходится расплачиваться производительностью за удобство и наоборот. Но гораздо лучше когда высокоуровневые средства есть под рукой, чем их нет. Тогда есть выбор, использовать их или нет в зависимости от ситуации.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Мне совсем не обязательно нужно обработать их все.
VD>Это вопрос взглядов на алгоритмы.
Я бы так сказал — это вопрос алгоритма. Поиск в BST, например, этого совсем не требует.
PD>>А все же, можешь что-то сказать насчет SearchAndInsert в BST ?
VD>Таких методов нет ни в одной дотной дотнетной коллекции, так что сказать про него я ничего не могу.
Хм... Ну а доведись тебе все же ее писать (алгоритм-то стандартный, школьный, можно сказать) — что напишешь ?
VD>Но могу сказать, что ты мыслишь одной записью (так скажем). Ты не думаешь в терминах преобразований, а ФП рассчитан как раз на такое мышление.
В общем-то верно. Добавляется одна запись. Но тогда ФП не есть замена императивному коду, а только дополнение. Так ?
Вот смотри. Мы тут с samius и Dufrenite пообсуждали деревья, и решение для всякого поиска они предложили на LinQ. Теперь представь себе, что есть у меня BST. Откуда взялось — не важно, но в данный момент сформировано окончательно и изменениям не подлежит (это мне так кажется). Я беру их код с поиском на LinQ и вставляю к себе. Все на ура. И тут выясняется, что я кое-что не учел, и если поиск неудачен, то надо этот ненайденный ключ вставить в BST. Что делать-то ? Выбросить весь код и переписать в императивном стиле ?
VD>Когда кто-то использует функциональный стиль, то он вместо возни с одним элементов отчирает их группу и вдет работу с ней. При этом отобранная группа обычно помещается в новую коллекцию.
Влад, я думаю, не стоит опять начинать дискуссию насчет объемов данных и осмысленности копирования, мы это уже не раз обсуждали, без толку. Но хочу отметить, что в моем примере чуть выше это просто не пройдет. Ну не предлагаешь же ты скопировать все BST ради вставки одного элемента — это же чепуха совсем получится! Да и как это сделать — все равно же вставлять придется ?
PD>> То есть вроде как запрос, но в самый интересный момент он превращается во вставку, тут же, по ходу действия, а потом опять в запрос (при отсутствии вставить и вернуть) ? Вариант с, как ты пишешь, "вводить новые копируя в них информацию из старых и меняя нужные подэлементы", тут вроде как не проходит.
VD>Тут никаких запросов нет. Это вообще какой-то изврат — тандем двух методов.
Побойся бога! Это один из классических алгоритмов! Более того, никакого другого способа строить BST я не знаю, его просто нет.
>Причем методов (по всей видимости) работающих с отдельными элементами. А тут линк не к чему. Линк он нужен чтобы не возиться с отдельными элементами, а работать с их группами.
Вот это я так и понимаю. Но мой вопрос остается. Сформулирую его точно.
Мне надо работать с BST. Делать BST буду сам
class TreeElem {
int key;
TreeElem Left, Right;
}
Операция, в сущности одна — SearchAndInsert. Иногда только Search, то есть вместо вставки вернуть null, если не найдено.
LinQ не пойдет ? Да или нет ?
PD>>Хм... Ну ладно. Хотя вроде как выносить мелкие алгоритмы в отдельные функции мы и так умели давно. И даже передавать им в качестве параметров иные функции, хоть и не лямбды.
VD>Ну, значит ты давно пользовался ФП не подозревая об этом. Хотя более правдоподобным выглядит предположение о том, что ты преувеличиваешь.
Что я преувеличиваю ? Вспомни нелюбимый тобой Win32, там функций с callback параметрами полным-полно. А это даже не С++, а чистый С.
VD>Функцию ты может и мог передать, но без замыканий толку от этого не много. Ведь для вынесения алгоритма уровня цикла в отдельную функцию нужно в эту функцию передавать контекст вычислений. А без замыканий это сделать невозможно.
Ну не знаю. Может, мы о разных вещах говорим.
PD>>ИМХО все же дерево — это дерево, а не последовательность. Линейный и разветвленные структуры — это все же не одно и то же, принципиально. Так следующим шагом ты и граф в последовательность превратишь Конечно, я говорю о самой структуре, а не о результате ее сериализации.
VD>Ну, ты уж как-то давай сам решай. Или ты задаешь вопросы и получаешь ответы, или ты уже сам все решил, но тогда не стоит задавать вопросы.
Опять ты на свой тон сбиваешься. Я не задаю вопросы и не получаю ответы, я веду дискуссию, и в ней могу высказать свое мнение, тем более, что здесь речь идет не о LinQ, которого я не знаю, а о структурах данных — разделе, где у меня есть некоторые основания высказывать свое мнение
VD>Твое ИМПХО базируется на старых привычках.
Если речь идет о дереве — то оно базируется все же на концепциях структур данных, которые опять же ИМХО ни от чего не зависят, ибо базис.
>У меня было тоже самое, но я сумел перестроиться. Попробуй и ты. Не выйдет, значит и дальше ничего в линке не будешь видеть. В принципе не проблема. На циклах тоже можно программировать. Несколько медленнее конечно, но не смертельно.
Да никакой проблемы нет. Для моих задач LinQ совершенно неуместен, и я его использовать не буду, там скорость критична. Мне просто интересно, с чего вы все так на него набросились при всех его недостатках. Вот и пытаюсь разобраться, что он может, а что нет. Из чисто познавательских целей.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>В общем-то верно. Добавляется одна запись. Но тогда ФП не есть замена императивному коду, а только дополнение. Так ?
Не замена, не дополнение, а альтернатива.
PD>Вот смотри. Мы тут с samius и Dufrenite пообсуждали деревья, и решение для всякого поиска они предложили на LinQ. Теперь представь себе, что есть у меня BST. Откуда взялось — не важно, но в данный момент сформировано окончательно и изменениям не подлежит (это мне так кажется). Я беру их код с поиском на LinQ и вставляю к себе. Все на ура. И тут выясняется, что я кое-что не учел, и если поиск неудачен, то надо этот ненайденный ключ вставить в BST. Что делать-то ? Выбросить весь код и переписать в императивном стиле ?
Нет, написать новых 10 строчек кода для вставки.
VD>>Когда кто-то использует функциональный стиль, то он вместо возни с одним элементов отчирает их группу и вдет работу с ней. При этом отобранная группа обычно помещается в новую коллекцию.
PD>Влад, я думаю, не стоит опять начинать дискуссию насчет объемов данных и осмысленности копирования, мы это уже не раз обсуждали, без толку. Но хочу отметить, что в моем примере чуть выше это просто не пройдет. Ну не предлагаешь же ты скопировать все BST ради вставки одного элемента — это же чепуха совсем получится! Да и как это сделать — все равно же вставлять придется ?
Не нужно копировать ВСЕ BST ради вставки одного элемента. Кол-во вновь созданных элементов при любом "изменении" не превышает высоту дерева (изменение в ковычках потому как дерево не меняется). И вставлять придется не в существующее дерево, а в новое дерево, которое будет в основном состоять из старых элементов.
Вот код, совместимый с предыдущими примерами:
static Node<T> Insert<T>(this Node<T> tree, T value)
{
if(tree == null)
return new Node<T>(value, null, null);
var eq = Comparer<T>.Default.Compare(tree.Value, value);
if (eq == 0)
return tree;
return eq > 0
? new Node<T>(tree.Value, Insert(tree.Left, value), tree.Right)
: new Node<T>(tree.Value, tree.Left, Insert(tree.Right, value));
}
PD>>> То есть вроде как запрос, но в самый интересный момент он превращается во вставку, тут же, по ходу действия, а потом опять в запрос (при отсутствии вставить и вернуть) ? Вариант с, как ты пишешь, "вводить новые копируя в них информацию из старых и меняя нужные подэлементы", тут вроде как не проходит.
VD>>Тут никаких запросов нет. Это вообще какой-то изврат — тандем двух методов.
PD>Побойся бога! Это один из классических алгоритмов! Более того, никакого другого способа строить BST я не знаю, его просто нет.
Есть, но он несколько отличается от запроса по дереву, потому делать из них гибрид нет никакого смысла.
>>Причем методов (по всей видимости) работающих с отдельными элементами. А тут линк не к чему. Линк он нужен чтобы не возиться с отдельными элементами, а работать с их группами.
PD>Вот это я так и понимаю. Но мой вопрос остается. Сформулирую его точно. PD>Мне надо работать с BST. Делать BST буду сам
PD>class TreeElem { PD> int key; PD> TreeElem Left, Right; PD>}
PD>Операция, в сущности одна — SearchAndInsert. Иногда только Search, то есть вместо вставки вернуть null, если не найдено.
PD>LinQ не пойдет ? Да или нет ?
Для модификации данных использовать LINQ однозначно зло! Но если дерево мутабельное, то можно сделать следующим образом: SearchAndInsert вызывает поиск узла с value и если его нет, то чтобы вернул узел, куда будем вставлять новый. Это делается линком. После того как узел получен, SearhAndInsert делает небольшой анализ и либо возвращает его, либо создает новый узел и модифицирует существующий. Т.е. мы не модифицируем Search->SearchAndInsert, а делегируем SearhAndInsert=>SearchForInsert.
Пойдет? И LINQ замешан и Insert есть, причем даже императивный/модифицирующий.
PD>Если речь идет о дереве — то оно базируется все же на концепциях структур данных, которые опять же ИМХО ни от чего не зависят, ибо базис.
Павел! Без обид, у Вас базис не полный. Изучите функциональные подходы для работы со структурами данных.
