Здравствуйте, gandjustas, Вы писали:
I>>Соответсвенно эту же корректировку нужно делать и в твоем случае, иначе обход никогда не завершится. G> G>Нафига мне за твоими изменениями гоняться? Ты так можешь в каждом посте ченить придумывать и будешь делать вид что всегда прав.
Это не изменения, hashset был изначально.
I>>Ты и читать похоже разучился: I>>"Назначение функции — вычислить подграф c определенным порядком следования вертексов, для чего используется модифицированый dfs" G>"вычислить подграф c определенным порядком следования вертексов" вот это сформулируй в проверяемом виде. А то я тебе ченить напишу, а ты опять 30 раз условие поменяешь.
уже был даден скорректированый код, а тебе всё чего то неймется.
I>>С визиторами я не промахнулся, кстати говоря. G>Очень промахнулся. Ты даже не можешь толково объяснить где у тебя в коде визитор. Потому что под определение GOF он не подходит,
Не валяй дурака, вот после чего появился тот код
G>>Обходы и визиторы — не одно и то же.
G>>Я тоже часто пишу обходы, мне хватает IEnumerable<T> и Linq.
I>Вот,сильно упрощенный пример. Покажи, как тут Linq поможет
Очевидно, речь про обход. Я и привел тебе пример обхода, что бы ты показал куда там Linq приспособить.
А вот паттерн визитор в этом коде захотел углядеть НС, а не я.
Здравствуйте, gandjustas, Вы писали:
G>Далее как будет выглядеть обход. Так как нет общего предка, то будет две точки входа: функции VisitA и VisitB. При обходе каждая из них будет вызывать isitA и VisitB при необходимости.
G>Ну вот и нету двойной диспетчеризации, даже одинарной нет. Если конечно воспользоваться статическим полиморфизмом, то вполне можно сделать статическую одинарную диспетчеризацию, но это совершенно необязательно.
В частном случае это так. А если, скажем, будет нечто вроде коллекции List<object> которая будет хранить и A и B ?
Итого — в частных случаях двойная диспетчеризация не нужна. В общем — нужна.
Здравствуйте, Ikemefula, Вы писали:
I>>>Ты и читать похоже разучился: I>>>"Назначение функции — вычислить подграф c определенным порядком следования вертексов, для чего используется модифицированый dfs" G>>"вычислить подграф c определенным порядком следования вертексов" вот это сформулируй в проверяемом виде. А то я тебе ченить напишу, а ты опять 30 раз условие поменяешь.
I>уже был даден скорректированый код, а тебе всё чего то неймется.
То есть ты не хочешь рассказать что он делает (как он что-то делает я уже вижу)?
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, gandjustas, Вы писали:
G>>Далее как будет выглядеть обход. Так как нет общего предка, то будет две точки входа: функции VisitA и VisitB. При обходе каждая из них будет вызывать isitA и VisitB при необходимости.
G>>Ну вот и нету двойной диспетчеризации, даже одинарной нет. Если конечно воспользоваться статическим полиморфизмом, то вполне можно сделать статическую одинарную диспетчеризацию, но это совершенно необязательно.
I>В частном случае это так. А если, скажем, будет нечто вроде коллекции List<object> которая будет хранить и A и B ?
То есть ты ввел общего предка "object". Но у тебя также будет одинарная диспетчеризация через type testing будет, а не двойная.
Ты создал частный случай, я как раз описал более общий случай.
I>Итого — в частных случаях двойная диспетчеризация не нужна. В общем — нужна.
Это ты приводишь частный случай Ведь в C++ такого не напишешь, там нет общего предка.
I>Иди читай дальше
Это ты иди со своими заказчиками так общайся, тут "приседание на умняк" не помогает. Ты аргументов не приводишь, только увиливаешь.
Здравствуйте, gandjustas, Вы писали:
I>>уже был даден скорректированый код, а тебе всё чего то неймется. G>То есть ты не хочешь рассказать что он делает (как он что-то делает я уже вижу)?
Это ж очевидно — находит и возвращает все вертексы достижимые из заданного.
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, gandjustas, Вы писали:
I>>>уже был даден скорректированый код, а тебе всё чего то неймется. G>>То есть ты не хочешь рассказать что он делает (как он что-то делает я уже вижу)?
I>Это ж очевидно — находит и возвращает все вертексы достижимые из заданного.
Ну держи:
public static IEnumerable<T> BreadthFirst<T>(T item, Func<T, IEnumerable<T>> ajancedNodes)
{
return BreadthFirstImpl(ajancedNodes(item), ajancedNodes, new HashSet<T>());
}
private static IEnumerable<T> BreadthFirstImpl<T>(IEnumerable<T> nodes, Func<T, IEnumerable<T>> ajancedNodes, HashSet<T> visited)
{
var l = nodes.Where(visited.Add).ToList();
if (!l.Any())
{
return Enumerable.Empty<T>();
}
var seq = l.SelectMany(ajancedNodes);
return l.Concat(EnumerableEx.Defer(() => BreadthFirstImpl(seq, ajancedNodes, visited)));
}
IEnumerable<Vertex> Reachable(Vertex vertex)
{
return BreadthFirst(vertex, v => v.Childs ?? new Vertex[0]);
}
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, gandjustas, Вы писали:
G>>Ну держи:
I>Т.е. количество кода у тебя тупо увеличилось в полтора раза
А мне студия говорит что у меня 11 строк против твоих 16
Я ей больше верю.
I>При этом I>вместо dfs ты взял bfs, я понимаю, что ты специально "забыл", ну да хрен с ним
Опять ты за свое...
I>>находит и возвращает все вертексы достижимые из заданного.
Это условие выполняется.
I>перформанс падает ниже плинтуса в BreadthFirstImpl
А как ты померил? Покажи тестовые данные, результаты забегов итп.
I>ЧТД — на JS том же задача решается в 5 строк, у тебя — 18 из за Linq. Вобщем, ты показал, что на динамике и код короче и прозрачнее
См выше. Ты не те строки считаешь.
Кстати покажи код на js, я тебе не верю что 5 строк будет. Хотя смотря какие строки ты считаешь в js.
I>P.S. А теперь попробуй решить вторую задачу, для которой я привел свое решение, — поиск всех роутов начиная с заданного вертекса.
Нивопрос, выбирай
public static IEnumerable<IEnumerable<T>> BreadthFirst<T>(T item, Func<T, IEnumerable<T>> adjacentNodes)
{
var p = EnumerableEx.Return(item);
var visited = new HashSet<T>(p);
return EnumerableEx.Generate(EnumerableEx.Return(p),
s => s.Any(),
s => (from ss in s
from n in adjacentNodes(ss.First())
where visited.Add(n)
select ss.StartWith(n)).MemoizeAll(),
s => s
).SelectMany(s => s);
}
public static IEnumerable<IEnumerable<T>> DepthFirst<T>(T item, Func<T, IEnumerable<T>> adjacentNodes)
{
var p = EnumerableEx.Return(item);
var visited = new HashSet<T>(p);
return DepthFirstImpl(p, adjacentNodes, visited).MemoizeAll();
}
private static IEnumerable<IEnumerable<T>> DepthFirstImpl<T>(IEnumerable<T> path, Func<T, IEnumerable<T>> adjacentNodes, HashSet<T> visited)
{
return adjacentNodes(path.First())
.Where(visited.Add)
.SelectMany(n => DepthFirstImpl(path.StartWith(n), adjacentNodes, visited))
.StartWith(path);
}
IEnumerable<Route> AllRoutes1(Vertex root)
{
return BreadthFirst(root, v => v.Childs ?? new Vertex[0])
.Select(r => new Route(r.Reverse()));
}
IEnumerable<Route> AllRoutes2(Vertex root)
{
return DepthFirst(root, v => v.Childs ?? new Vertex[0])
.Select(r => new Route(r.Reverse()));
}
I>P.P.S. фунцыя в JS V8 походу порвёт твой _шедевр_ по перформансу.
Нивопрос, приведи реальную задачу и тестовые данные.
Я специально сделал поиск максимально ленивым, чтобы мог при желании ограничить перебор и даже не искать все пути на графе.
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Визитор — вполне конкретный паттерн, описанный изначально в GoF.
За это минус, ибо ни в какие ворота... Все "трюки", описанные в GOF были известны задолго до. GOF известен тем, что обобщил и что дал терминологию трюкам, ну и дохочиво, "на пальцах", разъяснил подходящие условия для применения упомянутых паттернов.
Визитор — это трюк всегда известный под названием двойной диспетчеризации. Кто бы что ни говорил, утверждая, что это "другая точка зрения на происходящее". Словесная муть это, а не "другая точка зрения".
НС>При этом может существует несколько видов задач диспетчеризации и несколько методов решения этих задач, но визиторами они от этого не становятся.
Мде... Если правый аргумент называется visitor, то это, понятное дело, одноименный паттерн, а если этот же аргумент назвать callMeBack, то уже совсем другое дело, ага, это уже разновидность диспетчеризации.
ИМХО, это от непонимания концепции мультиметодов (частный случай которых в 2-х аргументах веселая четверка обозвала визитором, хотя суть паттерна "визитор" может быть расширена на любое кол-во аргументов, ибо это позволяют мультиметоды).
НС>Как не может статическая перегрузка методов быть заменой мультиметодов.
Да мы уже поняли, что кто-то ничего не понял. Речь не о статической перегрузке сигнатур ф-ий или методов. Именно как в "классическом" визиторе речь о диспатчинге в рантайм, например в boost::variant конкретный метод обратного вызова зависит от текущего хранимого типа. Вся разница в том, что при этом вызываемые методы визитора не обязаны быть виртуальными, потому как идет кодогенерация на шаблонах прямо в конкретном месте обратного вызова (кода посетителя) с уточненным типом-визитором. Сравни с неуточненным в случае интерфейсов. В "неуточненном" варианте исполнения предполагается только одна реализация визитора, которая абстрагируется от конкретного посещаемого через интерфейс. А в С++ имеем кодогенерацию на шаблонах произвольного кол-ва этих методов под конкретные типы. И да, классический интерфейс с виртуальными ф-иями тоже можно подавать. В этом случае будет сгенерен тот же код, который может быть написан в необобщенном виде, на абстрактных классах/интерфейсах, например на Джаве времен GOF.
Посмотри на этот boost::variant, должно стать понятней, что имеют ввиду, когда говорят про "статического визитора" в С++. В C# такого на генериках не получить, там потребуется именно некий интерфейс, требующий последующего переопределения, то бишь потребуется техника виртуальных ф-ий. А вот в современной Джаве, скорее всего, уже можно.
Здравствуйте, Sinix, Вы писали:
НС>>Откуда вообще эта стратсть натягивать презерватив на ежика? S>Так оно круче звучит и создаёт иллюзию безопасного ёжика понимания предмета.
Дык, вроде статическая типобезопасность круче динамической?
Здравствуйте, Ikemefula, Вы писали:
НС>>Под это определение подходят чуть болеечем все поведенческие паттерны
I>Чушь.
Веско
НС>>Ну да цитату в студию. Лучше всего из банды, первоисточник все таки.
I>Там кривое изложение.
Давай источник с прямым.
НС>>С точностью до наоборот.
I>В некоторых источниках визитор вообще сводится к двойной диспетчеризации.
В языках с отсутствующей перегрузкой допустимо использование рукопашного разнесения по нужным методам. Да и в языках с онной иногда, для улучшения читаемости, от двойной диспетчеризации отказываются. Главное, это никак не меняет логику самого паттерна, всего лишь определяет, какую часть работы возьмет на себя компилятор.
I>Виртуальный метод необязателен Утиной типизации может быть достаточно
Что в лоб, что по лбу. Но пример то у тебя на шарпе, там никакой утиной типизации в статически типизированном контексте нет.
I>Отвечаешь мне, а пишешь не мне
Такое иногда бывает, да. Тут все таки не личная переписка, а публичный форум.
Здравствуйте, gandjustas, Вы писали:
G>Кстати для визитора в определении GOF двойная диспетчеризация — не цель, а средство. Цель — отвязать операции со структурой от самой структуры, чтобы операции можно было менять произвольно.
Важный момент — полиморфные операции. Потому что если нет динамического полиморфизма, то и визитор не нужен.
Здравствуйте, vdimas, Вы писали:
V>За это минус, ибо ни в какие ворота... Все "трюки", описанные в GOF были известны задолго до.
Приводи ссылку на первоисточник. Не забудь только, что речь не о трюках вообще, а о конкретном паттерне, названом конкретным термином.
V> GOF известен тем, что обобщил и что дал терминологию трюкам, ну и дохочиво, "на пальцах", разъяснил подходящие условия для применения упомянутых паттернов.
А речь здесь именно о терминологии, о том что называется словом "визитор". И для этого надо читать определения, а не заниматься фантазированием на тему. Считаешь что термин ввели не в банде? Возможно. Но тогда приводи первоисточник, будем смотреть что в нем написано.
V>Визитор — это трюк всегда известный под названием двойной диспетчеризации.
Ссылку на такое определение — в студию.
V> Словесная муть это, а не "другая точка зрения".
ПОка что словесная муть у тебя, потому что не подкреплена ни одной ссылкой.
V>ИМХО, это от непонимания концепции мультиметодов (частный случай которых в 2-х аргументах веселая четверка обозвала визитором, хотя суть паттерна "визитор" может быть расширена на любое кол-во аргументов, ибо это позволяют мультиметоды).
Это от того, что кое кто жонглирует терминами.
V>Посмотри на этот boost::variant, должно стать понятней, что имеют ввиду, когда говорят про "статического визитора" в С++.
Т.е. опять жонглирование терминами. Ссылку на определение "статического визитора" в студию.
V> В C# такого на генериках не получить, там потребуется именно некий интерфейс, требующий последующего переопределения, то бишь потребуется техника виртуальных ф-ий.
Виртуальные функции нужны не для интерфейса визитора, виртуальным (и объявленным в базовом классе) должен быть метод AcceptVisitor. Это принципиально. А сам визитор, конечно, же, может обходится и без виртуальных функций.
Здравствуйте, Ikemefula, Вы писали:
I>ФП-стиль это баззворд.
Под ФП-стилем обычно подразумевают ориентацию в дизайне на работу с функциональными объектами. Т.е. ср-ва для создания оных, и ожидание их же в кач-ве аргументов в публичном АПИ.
Здравствуйте, DelphiGuru, Вы писали:
DG>После недели детального изучения исходников STL я пришел к выводу, что ее можно реализовать при помощи чистого ООП. Что думают пишущие на Си++ об этом
Скажу тебе по секрету: пишущие на C++ такой хренью не заморачиваются.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Head Ache, Вы писали:
HA>Почему, когда другие языки имитируют (обычно с потерей эффективности) фичи C++, такие как метапрограммирование, переопределение операторов, HA>объекты STL — это "круто", а С++ "слишком сложный"? HA>Черт возьми, ну не для всех он "слишком сложный"...
Я начинаю понимать лисперов ведь у них действительно "все украли"
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, Head Ache, Вы писали:
HA>>Почему, когда другие языки имитируют (обычно с потерей эффективности) фичи C++, такие как метапрограммирование, переопределение операторов, HA>>объекты STL — это "круто", а С++ "слишком сложный"? HA>>Черт возьми, ну не для всех он "слишком сложный"...
FR>Я начинаю понимать лисперов ведь у них действительно "все украли"
Здравствуйте, Ночной Смотрящий, Вы писали:
V>>Посмотри на этот boost::variant, должно стать понятней, что имеют ввиду, когда говорят про "статического визитора" в С++.
НС>Т.е. опять жонглирование терминами. Ссылку на определение "статического визитора" в студию.
Но (использовал не раз на деревянных структурах boost::variant) я никаких противоречий GOF'скому определению визитора
не увидел. По сути это и есть визитор.
Здравствуйте, vdimas, Вы писали:
I>>ФП-стиль это баззворд.
V>Под ФП-стилем обычно подразумевают ориентацию в дизайне на работу с функциональными объектами. Т.е. ср-ва для создания оных, и ожидание их же в кач-ве аргументов в публичном АПИ.
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>>>Ну да цитату в студию. Лучше всего из банды, первоисточник все таки. I>>Там кривое изложение. НС>Давай источник с прямым.
Joshua Kerievsky
I>>В некоторых источниках визитор вообще сводится к двойной диспетчеризации.
НС>В языках с отсутствующей перегрузкой допустимо использование рукопашного разнесения по нужным методам. Да и в языках с онной иногда, для улучшения читаемости, от двойной диспетчеризации отказываются. Главное, это никак не меняет логику самого паттерна, всего лишь определяет, какую часть работы возьмет на себя компилятор.
Покажи мне решение для общего случая без двойной диспетчеризации.
I>>Виртуальный метод необязателен Утиной типизации может быть достаточно
НС>Что в лоб, что по лбу. Но пример то у тебя на шарпе, там никакой утиной типизации в статически типизированном контексте нет.
У меня пример на шарпе, но почему то только ты решил, будто я там какой то паттерн реализовал.
А там всего то тупой dfs чз лямбда-рекурсию, а визитор это вроде обфускации, что бы gandjustasа проверить.
Ведь в C++ такого не напишешь, там нет общего предка.
