Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Dufrenite, Вы писали:
D>>Очевидно, O(log(N)). D>>По лишним веткам не ходим.
PD>А, черт! Понял.
PD>Видимо, samius решил , что я прошу алгоритм поиска минимального элемента в двоичном дереве поиска. Там действительно проще, и намного — есть путь, его можно в виде набора итераторов представить. А я имел в виду произвольное двоичное дерево, то есть полный разветвляющийся обход. В нем лучше O(N) не может быть никак.
Да, я действительно решил что речь о BST
PD>Да, должен был я на этом акцентировать внимание. То-то я удивился с этим его Left, но списал на свое незнание LinQ Но вина моя небольшая — я же не написал, что это дерево поиска, так что и оснований предполагать не было.
PD>Жду от специалистов решения задачи — заново.
Заново не потребуется. Изменение будет лишь в селекторе, правда он станет немного сложнее. Оставлю в качестве упражнения.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>У меня вопрос к тем, кто считает, что он LinQ знает.
Вот это хороший подход. Одобряю!
PD>Сформулируйте, когда LinQ стоит применять и когда его применение нецелесообразно.
Введение: LINQ — это общее название используемое для весьма разных вещей. Посему я буду говорить о LINQ to Object, LINQ to DB (последнего не существует — это некий собирательный образ подразумевающий использование LINQ-провайдеров предоставляющий доступ к удаленным данным) и синтаксическом расширении (синтаксисе запросов).
LINQ to Object следует использовать в проектах на дотнет-языках для обработки списков. То есть, буквально, заменяя тонны циклов и невнятного кода на весьма компактный и легко читаемый код использующий LINQ-функции всшего порядка (т.п. функции параметризуемые функциями позволяющие уточнить или задать действия).
LINQ to Object не следует применять в редких случаях когда очень важна производительность, так как циклы все же несколько эффективнее LINQ to Object, и они лучше оптимизируеютя.
Иногда LINQ to Object не имеет нужных функций и кажется, что проще обойтись без него, но обычно более продуктивным подходом является расширение LINQ to Object собственными функциями высшего порядка упрощающими решение конкретных задач.
LINQ to DB имеет смысл использовать там где требуется создавать приложения плотно общающиеся с БД или другими внешними источниками информации для которых есть качественные LINQ-провайдеры.
LINQ to DB может быть заменен неким другим решением обеспечивающим такой же или более высокий уровень, например, собственный DSL-движок напрямую генерирующий SQL.
Синтаксическое расширение можно использовать, а можно не использовать. От этого мало что зависит. Некоторый код выигрывает от применения синтаксиса, некоторый — нет. Обычно мелкие "запросы" выгоднее писать в виде прямого использования функций высшего порядка предоставляемых LINQ-ом, а большие "запросы" лучше выглядят с использованием синтаксиса.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, 0x7be, Вы писали:
0>А что делать сессии, если у нее алгоритм обработки запроса частично последовательный, а частично параллельный? 0>Самой обращаться к пулу потоков и ручками в этих потоках запускать свои куски?
Мы получили достаточно специфическую задачу.
M>>Или, например, при написании шахматной прораммы, нет никакого смысла делать генератор ходов многопоточным, потому что распараллеливание естественным образом возникает при переборе вариантов на верхнем уровне.
0>Запустить несколько генераторов в отдельных потоках, отрезав каждому по ломтику задачи?
Если честно, то в шахматах будет даже модификация алгоритма перебора alpha-beta, облегчающая многопоточность. В однопоточном случае мы рассматриваем первый ход 1. e2-e4 (и белые выигрывают! Раузер) и вычисляем коэффициенты отсечения alpha и beta, которые затем используются при анализе второго хода 1. d2-d4 (и белые выигрывают! Боголюбов). В двухпоточном случае 1. e2-e4 и 1. d2-d4 будут анализировать одновременно, а результаты alpha и beta будуи применяться уже к третьему ходу. Есть еще эвристика ходов-киллеров, которые меняют порядок перебора в продолжении 1.d2-d4 после анализа 1. e2-e4. Уже этот пример может показать всякие тонкости, которые могут возникнуть в практической жизни.
int Position.AlphaBeta(int color, int depth, int alpha, int beta)
{
if (depth == 0) return Evaluate(color);
// В этом цикле запустить параллельное выполнение AlphaBeta в цикле мы не можем,
// так как формально значение alpha может изменитьсяforeach (move in GenerateAllMoves())
{
if (alpha >= beta) break;
DoMove(move); // Второй ньюанс: быстрее выполняется do/undo, чем создание новой позицииint temp = -AlphaBeta(Toggle(color), depth-1, -beta, -alpha);
UndoMove(move);
if (tmp > alpha) alpha = tmp;
}
return alpha;
}
0>Сложно сказать. В принципе, сейчас я тоже к параллелизму прихожу как к крайнему средству. Но это происходит не в последнюю очередь потому, что средства распараллеливания сейчас очень неуклюжи. Их применение обфусцирует предметный алгоритм. Однако многоядерность твердой поступью входит в нашу жизнь, появляются новые средства обеспечения параллельных вычислений, так что приоритеты оптимизации меняются. По-этому я активно интересуюсь прогрессом в этой области.
Есть правило крутого поворота: крутой поворот в жизни происходит или намного раньше, или намного позже ожидаемого срока и ведет обычно в совсем неожидаемом направлении.
На сегодня мы не часто упираемся в вычислительную мощь процессора. Если брать игры, и особенно, математические расчеты, то зачастую это большое колиество однотипных действий. Поэтому тут развитие может пойти в сторону параллельных процессоров (NVIDIA CUDA — неграфические вычисления на графических процессорах и Часть 2 — Примеры внедрения NVIDIA CUDA. А это уже специальное программирование. В случае серверов опять же чаще всего проблема в том, чтобы распараллелить работу многих пользователей, а вычислений для конкретного пользователя не так уж и много. Остаются еще задачи типа шахмат, но там свои приколы, затрудняющие общий подход. Так что средства вроде PLINQ и ФЯ, применительно к многопоточной оптимизации, по моему мнению, помогут решить некоторый узкий круг задач, а в остальном просто видоизменят проблему: вместо того, чтобы параллелить вычисления самому, мы будем думать о том, каким образом донести до компилятора идею о том, как лучше параллелить, где это можно а где нельзя, где можно отойти от алгоритма и как.
Здравствуйте, Mystic, Вы писали:
0>>А что делать сессии, если у нее алгоритм обработки запроса частично последовательный, а частично параллельный? 0>>Самой обращаться к пулу потоков и ручками в этих потоках запускать свои куски? M>Мы получили достаточно специфическую задачу.
Ну да. Многопоточный сервер — это тоже задача, обладающая своей спецификой
M>Есть правило крутого поворота: крутой поворот в жизни происходит или намного раньше, или намного позже ожидаемого срока и ведет обычно в совсем неожидаемом направлении.
+1
M>На сегодня мы не часто...
[skip] M>...где можно отойти от алгоритма и как.
Я согласен с такой точкой зрения. Предлагаю некоторую сумму, как итоговый консенсус: "больше средств для параллелизма, хороших и разных". Я не выступал за PLINQ и подобные ему средства, как за панацею. Безусловно, у них своя ниша, так же как и у "серверо-ориентированных" и у GPU и MAPI и прочих.
Здравствуйте, samius, Вы писали:
S>У вновь созданного метода будет параметр типа Stream. Соответственно для того чтобы использовать его как FileStream, нужен будет даункаст.
Вот ты чего. Хорошо, это решает вопрос, только во-первых решение это является пальбой из пушки по воробьям, если других причин для выделения метода нет, а во-вторых оно может оказаться не вполне тривиальным, если нужно передавать в выделяемый метод несколько локальных переменных.
Здравствуйте, igna, Вы писали:
I>Здравствуйте, samius, Вы писали:
S>>У вновь созданного метода будет параметр типа Stream. Соответственно для того чтобы использовать его как FileStream, нужен будет даункаст.
I>Вот ты чего. Хорошо, это решает вопрос, только во-первых решение это является пальбой из пушки по воробьям, если других причин для выделения метода нет, а во-вторых оно может оказаться не вполне тривиальным, если нужно передавать в выделяемый метод несколько локальных переменных.
Если есть возможность абстрагироваться от FileStream-а при записи в файл (а это можно сделать в 98% случаев), то это следует сделать, и перегруженный метод для записи в стрим должен быть. Пусть он будет приватным, но именно он будет содержать основную логику и локальные переменные тоже. Метод, создающий непосредственно FileStream будет лишь делегировать и не должен содержать никакой логики и локальных переменных кроме самого стрима.
По поводу причин — выделение абстракции для тестирования — довольно уважительная причина для Extract method рефакторинга.
Здравствуйте, 0x7be, Вы писали:
0>Добрый день.
0>По опыту своих бесед с программистами, не знакомыми с linq, я собрал ряд стереотипных заблуждений и проблем с пониманеим linq, которые у них встречаются. В целом среди них преобладает такое мнение "это убогий SQL в С#, зачем он нужен?". Все попытки объяснить, что linq является воплощением аппарата операций над множествами, который ортогонален языку, и с необходимостью которого никто не спорит, сталкиваются с такой стеной непонимания. Это приводит меня к мысли, что linq подан неудачно. Его SQL-подобный синтаксис вызывает затруднения и у тех кто не знаком с SQL (выглядит больно непривычно) и у тех, кто знаком (не совсем понимают, что SQL делает в языке и сталкиваются с тем, что синтаксис всего лишь похож, а не повторяет SQL). Мое мнение по этому поводу: Linq — хорошая штука, но неудачно подан. Ваши мнения?
А мне больше понравились новшества, которые появились из-за LINQ. Вот их бы совершенствовать, а LINQ как LINQ — есть и хорошо.
Здравствуйте, mukhomor, Вы писали:
M>А мне больше понравились новшества, которые появились из-за LINQ. Вот их бы совершенствовать, а LINQ как LINQ — есть и хорошо.
Какие именно новшества ты имеешь в виду?
Здравствуйте, igna, Вы писали:
I>Здравствуйте, samius, Вы писали:
S>>Оставлю в качестве упражнения.
I>Оставь. Только когда поупражняешься, не забудь запостить результат.
Полагаю что любой, кому интересен результат, сможет получить его самостоятельно.
Здравствуйте, 0x7be, Вы писали:
0>Здравствуйте, mukhomor, Вы писали:
M>>А мне больше понравились новшества, которые появились из-за LINQ. Вот их бы совершенствовать, а LINQ как LINQ — есть и хорошо. 0>Какие именно новшества ты имеешь в виду?
Расширяющие методы, лямбда-выражения, анонимные типы. На мой взгляд, это добавляет некоторое изящество в код. Что касается самого LINQ, то, опять-таки, на мой взгляд, он немного меняет мировозрение в отношении работы с данными. Может поэтому сразу и не прижился. Нужно попривыкнуть.
S>Заново не потребуется. Изменение будет лишь в селекторе, правда он станет немного сложнее. Оставлю в качестве упражнения.
И все же, если не очень сложно — напиши. Моих знаний LinQ для решения этого упражнения не хватает
Я не могу одно понять. В BST фактически поиск минимального элемента есть работа не с деревом, а со списком из .Left. Это понятно, и твой итератор тоже. Но в просто дереве идея .Last ИМХО попросту не работает, поскольку тут Last нет. Отсортировать и взять Last — такое не надо. А иначе что ?
Здравствуйте, Dufrenite, Вы писали:
D>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Жду от специалистов решения задачи — заново.
D>Эта задача совсем тривиальна:
Может, я что-то не понимаю, но
D>[c#] D> class Node D> { D> public int Value; D> public Node Right; D> public Node Left; D> }
D> static IEnumerable<int> Values(Node root) D> { D> if (!ReferenceEquals(root, null)) D> { D> yield return root.Value; D> var childValues = Values(root.Left).Concat(Values(root.Right));
Enumerable.Concat<(Of <(TSource>)>) — метод
Объект IEnumerable<(Of <(T>)>), содержащий объединенные элементы двух входных последовательностей.
Я правильно понял, что здесь создается новый объект, содержащий элементы двух последовательностей ? Не итератор или что-то еще, а именно объект ?
Если да — это не решение. Задача должна быть решена без создания новых "массовых "объектов. Иными словами, на памяти O(1). Алгоритм это позволяет.
Если я неправильно понял — объясни, пожалуйста.
Для справки — императивный алгоритм. Сорри, С++ (привычнее
#include"stdafx.h"#include"algorithm"struct TreeElem{
int Value;
TreeElem* Left, *Right;
TreeElem(int _Value, TreeElem* _Left, TreeElem* _Right) :
Value(_Value), Left(_Left),Right(_Right) {}
};
int MinElem(TreeElem* pElement)
{
int temp = pElement->Value;
if(pElement->Left)
temp = std::min(temp,MinElem(pElement->Left));
if(pElement->Right)
temp = std::min(temp,MinElem(pElement->Right));
return temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
TreeElem* t1 = new TreeElem(1, NULL, NULL);
TreeElem* t2 = new TreeElem(2,t1, NULL);
TreeElem* t3 = new TreeElem(4,NULL, NULL);
TreeElem* root = new TreeElem(3,t2,t3);
int m = MinElem(root);
// уничтожение опущеноreturn 0;
}
VD>LINQ to Object следует использовать в проектах на дотнет-языках для обработки списков. То есть, буквально, заменяя тонны циклов и невнятного кода на весьма компактный и легко читаемый код использующий LINQ-функции всшего порядка (т.п. функции параметризуемые функциями позволяющие уточнить или задать действия).
Спасибо. Вот именно это я и хотел узнать — выделено выше. У меня было то же ощущение — что LinQ (как и его духовный предок SQL) предназначен для обработки линейных структур (в общем понимании этого слова). Для структур нелинейного характера (деревья, графы и т.д.) он, как мне кажется, не слишком подходит. Хотя samius и Dufrenite пытаются меня убедить в обратном. Почитай эту часть дискуссии, она еще не кончена, можешь там высказаться.
И второе, это уже вопрос. Если речь идет о запросе — ладно. А если не о запросе ? Я, может, ошибаюсь опять, но вроде бы LinQ — это функциональное программирование. А оно позиционируется как альтернатива императивному. Если альтернатива — будьте добры обеспечить мне возможность сделать все, что я там могу сделать, иначе что же это за альтернатива! А если это только добавление — тогда уж так и будем говорить.
VD>LINQ to Object не следует применять в редких случаях когда очень важна производительность, так как циклы все же несколько эффективнее LINQ to Object, и они лучше оптимизируеютя.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
S>>Заново не потребуется. Изменение будет лишь в селекторе, правда он станет немного сложнее. Оставлю в качестве упражнения.
PD>И все же, если не очень сложно — напиши. Моих знаний LinQ для решения этого упражнения не хватает PD>Я не могу одно понять. В BST фактически поиск минимального элемента есть работа не с деревом, а со списком из .Left. Это понятно, и твой итератор тоже. Но в просто дереве идея .Last ИМХО попросту не работает, поскольку тут Last нет. Отсортировать и взять Last — такое не надо. А иначе что ?
Пройти по всему дереву (а не по Left) и взять минимальный элемент.
Проход по всему дереву от прохода по .Left отличается лишь селектором.
Вместо
n => n.Left != null? new[] {n.Left} : new Node<int>[]{}
или
public static IEnumerable<Node<T>> NextLeft<T>(this Node<T> root)
{
if (root.Left != null)
yield return root.Left;
}
указываем селектор такой
public static IEnumerable<Node<T>> SubNodes<T>(this Node<T> root)
{
return root.NextLeft().Concat(root.NextRight());
}
Тогда поиск минимума будет
var min = Walk(root, SubNodes).Select(n => n.Value).Min();
Вообще Dufrenite написал верный алгоритм. Но он написал новую функцию обхода значений элемента, в то время как я заюзал ФВП Walk лишь изменив селектор.
S>Вообще Dufrenite написал верный алгоритм. Но он написал новую функцию обхода значений элемента, в то время как я заюзал ФВП Walk лишь изменив селектор.
В сущности, меня вот что интересует.
Императивный алгоритм приведен там же. Он имеет O(N) по времени (больше просто незачем), однопроходной, копирование чего бы то ни было отсутствует (кроме, впрочем, адресов возврата в стеке — рекурсия!) и O(1) по дополнительной памяти (опять же не учитывая место в стеке)
Какова зависимость твоего алгоритма от времени ?
Сколько проходов ?
Копируются данные или нет ? Создается ли какой-то дополнительный контейнер какого бы то ни было вида (хоть из одних ссылок на элементы дерева) или нет ?
Объем дополнительной памяти как функция от N ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Dufrenite, Вы писали:
PD>Enumerable.Concat<(Of <(TSource>)>) — метод PD>Объект IEnumerable<(Of <(T>)>), содержащий объединенные элементы двух входных последовательностей.
PD>Я правильно понял, что здесь создается новый объект, содержащий элементы двух последовательностей ? Не итератор или что-то еще, а именно объект ?
Да, это объект-итератор, котрый пройдет по элементам двух последовательностей, но он не содержит их элементов, а только лишь умеет ходить по ним аки итератор из STL.
PD>Если да — это не решение. Задача должна быть решена без создания новых "массовых "объектов. Иными словами, на памяти O(1). Алгоритм это позволяет.
Ниже прикинем
PD>Если я неправильно понял — объясни, пожалуйста.
Правильно
PD>Для справки — императивный алгоритм. Сорри, С++ (привычнее
PD>
Этот алгоритм не может работать на памяти O(1), т.к. он юзает рекурсию, которая не приводима к хвостовой оптимизации. В точности ему потребуется память соразмерная высоте дерева, т.е. O(log N) в среднем и O(N) в худшем случае. Разница лишь в том, что этот вариант работает лишь на стэке, а вариант с объектами-итераторами просит еще и выделений в куче. Впрочем, возможно переписать реализацию IEnumerable в структурах и итераторы лягут полностью на стэк (потребуется немного другая форма метода Walk с двумя дженерик параметрами).
Самое важное отличие от реализации с функцией высшего порядка в том, что для MaxElem, SearchElem и т.п. придется писать новый метод обхода дерева каждый раз. В то время как обход дерева через ФВП Walk позволяет привести его к линейному виду и применить стандартный набор LINQ методов для работы с последовательностями.
Открою секрет, LINQ здесь используется только как набор высокоуровневых методов Select + Min из нэймспейса System.Linq. Т.е. сказать что обойти дерево можно на LINQ = немного слукавить. Более уместно здесь сказать что выделение паттерна обхода дерева в высокоуровневый метод высшего порядка позволяет свести задачу обхода дерева к обходу последовательности и применить Min из LINQ-а.
Полагаю что этот же подход можно реализовать в итераторах на C++ (к сожалению, STL не помню, а boost не знаю).
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
S>> return root.NextLeft().Concat(root.NextRight());
PD>Вопрос задан здесь (по Concat)
PD>http://www.rsdn.ru/forum/philosophy/3714968.1.aspx
S>>Вообще Dufrenite написал верный алгоритм. Но он написал новую функцию обхода значений элемента, в то время как я заюзал ФВП Walk лишь изменив селектор.
PD>В сущности, меня вот что интересует.
PD>Императивный алгоритм приведен там же. Он имеет O(N) по времени (больше просто незачем), однопроходной, копирование чего бы то ни было отсутствует (кроме, впрочем, адресов возврата в стеке — рекурсия!) и O(1) по дополнительной памяти (опять же не учитывая место в стеке)
PD>Какова зависимость твоего алгоритма от времени ?
Такая же
PD>Сколько проходов ?
1
PD>Копируются данные или нет ? Создается ли какой-то дополнительный контейнер какого бы то ни было вида (хоть из одних ссылок на элементы дерева) или нет ?
Я итератор не считаю контейнером, потому — нет.
PD>Объем дополнительной памяти как функция от N ?
Учитывая стек и созданные итераторы — по высоте дерева (log N при сбалансированном дереве и N в худшем случае).