Здравствуйте, Dufrenite, Вы писали:

D>Создается, безусловно. Что создается конкретно можно увидеть декомпилировав код.

Так я и жду от знающих LinQ объяснения, что именно там создается.


PD>>Потому что я не понимаю, как можно Last делать в дереве — ну нет там Last.

D>Last, это extension-метод IEnumerable<T> — результата запроса.

Все это замечательно, но вопрос совсем не в этом.

PD>>А сами элементы копируются или нет ?

D>Только как возвращаемое значение свойства IEnumerator<T>.Current.

И не в этом.

PD>>Если нет — то как это все же работает ? Лежат они как попало в памяти, а тут вдруг оказались выложенными в линию. Одно из двух — либо в памяти создан контейнер со ссылками на них, либо их скопировали в другой контейнер и там они подряд лежат.

PD>>Не согласен ? Тогда объясни, что там под спудом. Что там делается, какие данные и куда создаются или копируются.

D>Там все намного проще. Надеюсь с концепцией итераторов знакомы? Так вот енумератор, это такой продвинутый, генерируемый компилятором (или написанный вручную) итератор.

Замечательно. Давай отвлечемся от итераторов, энумераторов и т.д. Не надо мне объяснять, что это такое. Меня другое интересует.

Есть дерево. У него есть узлы. В узлах есть поле данных. Узлы лежат в куче в произвольном порядке. Поля ссылок узлов показывают на другие узлы (или равны nul)

Что там LinQ делает, какие там запросы и т.д. — об этом я сейчас не спрашиваю.

Мой вопрос достаточно четкий.

В алгоритме, представленнос samius, какие и в каком объеме промежуточные данные создаются в куче ? Хоть в результате создания контейнера, хоть в результате исполнения запроса, хоть итератором, хоть трансформатором ? Какие и в каком объеме ?

Или по крайней мере оцени их порядок. Сколько их — O(N), O(log(N), O(1) ?

Вот и все. Если можешь ответить — жду.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Мой вопрос достаточно четкий.

PD>В алгоритме, представленнос samius, какие и в каком объеме промежуточные данные создаются в куче ? Хоть в результате создания контейнера, хоть в результате исполнения запроса, хоть итератором, хоть трансформатором ? Какие и в каком объеме ?

Никаких промежуточных данных не создается, в том-то и фан. Linq-запросы — это по сути способ комбинирования энумераторов.

Здравствуйте, Lloyd, Вы писали:

L>Никаких промежуточных данных не создается, в том-то и фан. Linq-запросы — это по сути способ комбинирования энумераторов.

Ладно, пусть. Но вот сказано — Last. Что там реально делается, когда выполняется этот Last ? Ведь нельзя же в дереве выполнить Last физически, потому что нет в дереве информации, позволяющей пройти его таким способом. Да и Last нет вообще.
Список можно и массив можно. Сделал энумератор , а он внутри себя имеет способ перехода к следующемму элементу (t=t.next или i++), а дерево нельзя и граф нельзя. Чудес-то не бывает.

Если не согласен — тогда объясни, как это делается. Ну вот есть запрос, или комбинация энумераторов, или что хочешь. Что там в конечном счете делается в этом дереве, как этот минимальный элемент находится ? Бог с ним, с линком, но какие действия там процессор выполняет ? Он же линк выполнять не может!

И еще вопрос, если можешь ответить. Императивный алгоритм обхода дерева, естественно, O(N) и однопроходной. Здесь что ?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Или по крайней мере оцени их порядок. Сколько их — O(N), O(log(N), O(1) ?
PD>Вот и все. Если можешь ответить — жду.

Очевидно, O(log(N)).
По лишним веткам не ходим.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Список можно и массив можно. Сделал энумератор , а он внутри себя имеет способ перехода к следующемму элементу (t=t.next или i++), а дерево нельзя и граф нельзя. Чудес-то не бывает.

Это не чудеса. И даже не новое изобретение. Поинтересуйтесь на досуге, как работает итератор std::map.

Здравствуйте, Dufrenite, Вы писали:

D>Очевидно, O(log(N)).
D>По лишним веткам не ходим.

А, черт! Понял.

Видимо, samius решил , что я прошу алгоритм поиска минимального элемента в двоичном дереве поиска. Там действительно проще, и намного — есть путь, его можно в виде набора итераторов представить. А я имел в виду произвольное двоичное дерево, то есть полный разветвляющийся обход. В нем лучше O(N) не может быть никак.
Да, должен был я на этом акцентировать внимание. То-то я удивился с этим его Left, но списал на свое незнание LinQ Но вина моя небольшая — я же не написал, что это дерево поиска, так что и оснований предполагать не было.


Жду от специалистов решения задачи — заново.

Здравствуйте, Dufrenite, Вы писали:


D>Это не чудеса. И даже не новое изобретение. Поинтересуйтесь на досуге, как работает итератор std::map.

Поинтересовался. Честно говоря, до сих пор лишь предполагал, как он устроен.

Начнем с этого

iterator operator++(int)
{ // postincrement
iterator _Tmp = *this;
++*this;
return (_Tmp);
}

Далее через промежуточные методы (опущены) придем к

void _Inc()
{ // move to node with next larger value


Внутри него есть

while (!_Isnil(_Pnode = _Parent(_Ptr))
&& _Ptr == _Right(_Pnode))
_Ptr = _Pnode; // ==> parent while right subtree

В общем, все как обычно. Для map это вполне нормально — реализация на базе дерева, как еще возьмешь ключи.

Но я-то имел в виду не дерево поиска. Собственно говоря, меня интересует, как реализуется разветвляющийся алгоритм.

Здравствуйте, Pavel Dvorkin, Вы писали:

L>>Никаких промежуточных данных не создается, в том-то и фан. Linq-запросы — это по сути способ комбинирования энумераторов.

PD>Ладно, пусть. Но вот сказано — Last. Что там реально делается, когда выполняется этот Last ? Ведь нельзя же в дереве выполнить Last физически, потому что нет в дереве информации, позволяющей пройти его таким способом. Да и Last нет вообще.
PD>Список можно и массив можно. Сделал энумератор , а он внутри себя имеет способ перехода к следующемму элементу (t=t.next или i++), а дерево нельзя и граф нельзя. Чудес-то не бывает.

Бывают разные варианты обхода дерева. Который реализуешь, так и будет обходиться.

PD>Если не согласен — тогда объясни, как это делается. Ну вот есть запрос, или комбинация энумераторов, или что хочешь. Что там в конечном счете делается в этом дереве, как этот минимальный элемент находится ? Бог с ним, с линком, но какие действия там процессор выполняет ? Он же линк выполнять не может!

Ты концепцию итератора понимаешь? Значит и как линк работает понимаешь.

PD>И еще вопрос, если можешь ответить. Императивный алгоритм обхода дерева, естественно, O(N) и однопроходной. Здесь что ?

Ровно то же самое.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Жду от специалистов решения задачи — заново.

Эта задача совсем тривиальна:

        class Node
        {
            public int Value;
            public Node Right;
            public Node Left;
        }

        static IEnumerable<int> Values(Node root)
        {
            if (!ReferenceEquals(root, null))
            {
                yield return root.Value;
                var childValues = Values(root.Left).Concat(Values(root.Right));
                foreach (var value in childValues)
                {
                    yield return value;
                }
            }
        }

        static int Min(Node root)
        {
            return Values(root).Aggregate(int.MaxValue, (min, value) => value < min ? value : min);
        }

        static void Main(string[] args)
        {
            var root = new Node
                {
                    Value = 3,
                    Left = new Node
                        {
                            Value = 2,
                            Left = new Node { Value = 1 }
                        },
                    Right = new Node { Value = 4 }
                };

            Console.WriteLine(Min(root));
        }

Здравствуйте, Dufrenite, Вы писали:

Маленькое дополнение. При таком обходе скорее всего сложность Aggregate() будет не 0(N), а O(N * log(N)).

Но это издержки приведения дерева к линейному виду.
Если отказаться от приведения к линейному виду функцией Values(), а искать минимальный элемент прямо при обходе дерева, то алгоритм будет гарантировано линейным.

Здравствуйте, Lloyd, Вы писали:

L>Правильно, тормоза придумали трусы.
Тормозов я отсеиваю на собеседовании.

Здравствуйте, olegkr, Вы писали:

L>>Правильно, тормоза придумали трусы.
O>Тормозов я отсеиваю на собеседовании.

О да, детка.

Здравствуйте, Dufrenite, Вы писали:

D>Маленькое дополнение. При таком обходе скорее всего сложность Aggregate() будет не 0(N), а O(N * log(N)).

D>Но это издержки приведения дерева к линейному виду.

А откуда "* log(N)" берется?

Здравствуйте, Lloyd, Вы писали:

L>А откуда "* log(N)" берется?

Здесь тонкий момент, я сам не сразу заметил.
Фактически, енумератор, возвращающий листовой элемент, представляет собой связный список енумераторов (это можно увидеть декомпилировав код), длиной с глубину просмотра, а это log(N). Поэтому, при перемещении к следующему элементу, приходится проходить весь список енумераторов.
Отсюда и получаем N * log(N).

Здравствуйте, igna, Вы писали:

AVK>>Отсутствие возможности воспользоваться максимально полным контрактом.

I>Ну что это за аргумент?

Отличный аргумент.

I> Почему он относится к локальным переменным и не относится к параметрам?

Потому что тип параметра это уже контракт. Как следствие, от него зависит не только локальный код, но и код снаружи. Соотв. расширяя контракт внутри ты его автоматом и снаружи расширяешь, что, очевидно. неправильно. Тип же локальной переменной используется только внутри метода.

AVK>>А теперь встречный вопрос — а зачем обобщать тип локальной переменной?

I>Затем же, зачем обобщают тип параметра.

Параметр — часть контракта, локальная переменная — нет. Так что не катит.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, samius, Вы писали:


S>> foreach (var node in q)
S>> {
S>> yield return node;
S>> }

PD>Может, я не так понимаю, но ИМХО ты здесь еще один контейнер создал, q. Пусть временный, но создал.

Нет, в широком понимании контейнер здесь я не создавал. q — это запрос, который возвращает элементы из существующего дерева, не копируя и не выстраивая их в новую структуру. Разверну его:

        static IEnumerable<T> Walk<T>(T root, Func<T, IEnumerable<T>> next)
        {
            yield return root;

            //var q = from node in next(root)
            //        from n in Walk(node, next)
            //        select n;
            //foreach (var node in q)
            //{
            //    yield return node;
            //}

            foreach(var node in next(root))
            {
                foreach (var n in Walk(node, next))
                {
                    yield return n;
                }
            }
        }

Надеюсь, что так понятнее.


S>> var minNode = Walk(
S>> root,
S>> n => n.Left != null? new[] {n.Left} : new Node<int>[]{})
S>> .Last();

Вот здесь внимательный читатель найдет по новому контейнеру (пустому либо с одним элементом) на пройденный узел.

PD>И вот это мне совсем не по душе. Задача — найти минимальный элемент в дереве, а не выложить его куда-то упорядоченным и взять последний элемент. Задача нахождения минимального элемента в дереве алгоритмически не требует ни одного копирования элементов.

Минимальный — да, копирования элементов — нет. Дело в том, что я предположил что двоичное дерево есть BST и прошел от корня по левым поддеревьям. А если BST, то искать в нем минимальный элемент можно лишь полным перебором.

PD>Я не спорю, но ты решил иную задачу Реюз-то реюз, но... как бы объяснить без ссылок на производительность. Попробую так. Вот есть алгоритмы сортировки. И все договорились — отсортировать надо исходный массив без дополнительной памяти O(N). Иными словами, решения с еще одним массивом не рассматриваются. А для обхода деревьев не рассматриваются алгоритмы, которые копируют элементы деревьев — куда бы то ни было.
PD>Такое можно ?

Во-первыйх, не вижу никаких оговорок по дополнительной памяти:

Можно пример функции, скажем, нахождения минимального элемента в двоичном дереве ?

Во-вторых, новые контейнеры создаются только для того чтобы содержать единичные элементы и выкидываются сразу после того как по ним завершится обход. Эти контейнеры нужны для обхода стандартными методами линка, так что они скорее технологические чем алгоритмические. Всегда можно от одноэлементных и пустых массивов перейти к одноэлементным оберткам вроде

IEnumerable<T> Wrap(T value)
{
   if(EqualityComparer<T>.Equals(value, default(T)))
       yield return value;
}

Это можно назвать контейнером весьма условно.
Однако да, глубина рекурсии будет соответствовать глубине дерева.

S>>Insert — это не запрос. Здесь нужно либо модификация существующего дерева, либо построение нового дерева.

PD>Зачем же новое ? Но это к слову.
PD>А вот что не к слову — здесь не чистый запрос, да.
PD>Но вначале чистый запрос — есть ли элемент. Если не SearchAndInsert, а просто Search — это уж точно запрос. И если ты собираешься его реализовать чем-то вроде выкладывания как в прошлом примере и поиском там — извини, но что это за алгоритм поиска в двоичном дереве, который требует его выкладывания в последовательность ? На кой мне черт такое дерево ? Мне log(N) подайте и без копирования!

Итак, чистый запрос на наличие элемента в BST получается из моего примера лишь небольшим изменением метода-селектора. В этом случае нужно будет выбирать не левое поддерево, а то, что ближе к искомому элементу.
Алгоритм не требует копирования или создания новых контейнеров. Его сложность в худшем случае будет соответствовать высоте дерева. log(N) — это только для сбалансированных деревьев.

PD>А во вторых, тут очень показательный момент. Без Linq SearchAndInsert отличается от Search 2 строчками (либо return nul, либо return new node(...)) А так получится, что допустим, предполагал я , что вставки не понадобятся, написал на LinQ, а они потом понадобились, и что теперь ?

Тут варианты:
а) Дерево модифицируемое. Тогда мы поиском находим узел для вставки и потом отдельным методом модифицируем дерево.
б) Дерево иммутабельное. В этом случае придется написать 8 строчек вставки с нуля.
Ведь формально обход и обновление — разные вещи.

Здравствуйте, igna, Вы писали:

I>Здравствуйте, samius, Вы писали:

I>>>Кроме того внутри вновь созданного метода получим ту же ситуацию, что имели: чтобы узнать, что при использовании созданного FileStream используются только методы Stream, нужно будет просмотреть код. Так зачем тогда?

S>>Можно будет посмотреть только на сигнатуру метода и убедиться что внутри нет даункаста.

I>"Внутри вновь созданного метода" у тебя переменная и так будет типа FileStream, какой даункаст?
У вновь созданного метода будет параметр типа Stream. Соответственно для того чтобы использовать его как FileStream, нужен будет даункаст.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, Dufrenite, Вы писали:

D>>Все остальные рассуждения на изначально неверном предположении.

PD>Допустим, я не прав, но ... какая-то еще структура создается в памяти или или нет ? Запросом, контейнером, чертом лысым — но да или нет ? Потому что я не понимаю, как можно Last делать в дереве — ну нет там Last. А сами элементы копируются или нет ? Если нет — то как это все же работает ? Лежат они как попало в памяти, а тут вдруг оказались выложенными в линию. Одно из двух — либо в памяти создан контейнер со ссылками на них, либо их скопировали в другой контейнер и там они подряд лежат.

PD>Не согласен ? Тогда объясни, что там под спудом. Что там делается, какие данные и куда создаются или копируются.

Предполагалось что дерево BST. Создаются IEnumerable-ы и IEnumerator-ы по одному на шаг. Шагов в худшем случае по глубине дерева.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>В алгоритме, представленнос samius, какие и в каком объеме промежуточные данные создаются в куче ? Хоть в результате создания контейнера, хоть в результате исполнения запроса, хоть итератором, хоть трансформатором ? Какие и в каком объеме ?
IEnumerable-ы и IEnumerator-ы по одному за шаг.

PD>Или по крайней мере оцени их порядок. Сколько их — O(N), O(log(N), O(1) ?
Выделил

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ладно, пусть. Но вот сказано — Last. Что там реально делается, когда выполняется этот Last ? Ведь нельзя же в дереве выполнить Last физически, потому что нет в дереве информации, позволяющей пройти его таким способом. Да и Last нет вообще.
PD>Список можно и массив можно. Сделал энумератор , а он внутри себя имеет способ перехода к следующемму элементу (t=t.next или i++), а дерево нельзя и граф нельзя. Чудес-то не бывает.

Те енумераторы имеют в себе только узел, от которого они идут + способ перехода. Но способ перехода памяти не просит.

PD>Если не согласен — тогда объясни, как это делается. Ну вот есть запрос, или комбинация энумераторов, или что хочешь. Что там в конечном счете делается в этом дереве, как этот минимальный элемент находится ? Бог с ним, с линком, но какие действия там процессор выполняет ? Он же линк выполнять не может!

PD>И еще вопрос, если можешь ответить. Императивный алгоритм обхода дерева, естественно, O(N) и однопроходной. Здесь что ?

Здесь был O(log N), обход по BST.