Johanan May 28 2015 at 19:09

Двойная диспетчеризация

8 min

26K

Entertaining tasksProgramming*C#*

From sandbox

+16

Comments 37

maxim_0_o May 28 2015 at 21:13

На сколько я понял, мы условились, что в интерфейсе не будет свойства Color. Однако в блоке кода под заголовком «Применение посетителя к задаче» это свойство в интерфейсе есть. Я что-то не правильно понял?

Johanan May 28 2015 at 21:21

Вы всё правильно поняли, Color в ICell действительно не нужен. Опечатку поправил.

dougrinch May 28 2015 at 21:35

А как же

private string Do(ICell a, ICell b)
{
    return a.Color + "\t-->\t" + b.Color;
}

?

Хотя в данной реализации и не уйти от свойства в интерфейсе. Разве что создавать метод Do на все варианты, благо апи позволяет. Действительно удобное получилось.

Johanan May 28 2015 at 21:45

А! Точно. Внимательно читаете — спасибо. Сперва у меня как раз был цвет в интерфейсе, а добыть нужно было, скажем, целое число, которым обладала только красная ячейка. На идее решения эта оплошность никак не скажется, но нужно подумать, как лучше поправить статью.
Что нам нужно в методе Do? Знать цвет первой и второй ячейки, причём обе им обладают независимо друг от друга. Значит, нам нужен простой («классический») визитёр, который цвет добудет.

lasalas May 28 2015 at 22:04

Зачем так много кода для такой тривиальной задачи?

Johanan May 28 2015 at 22:06

А как иначе вы её предлагаете решать, если отмести варианты с динамическим приведением типов?

lasalas May 28 2015 at 22:15

Как-то так, например

public static string Match(ICell t1, ICell t2) { return Patterns .Select(x => x(t1, t2)) .First(x => x != null) (); } private static readonly Func<ICell, ICell, Func<string>>[] Patterns = { (t1, t2) => Match<RedCell, RedCell>(t1, t2, () => "красное на красном"), (t1, t2) => Match<GreenCell, BlueCell>(t1, t2, () => "побережье"), (t1, t2) => (() => t1.Color + "\t-->\t" + t2.Color) }; private static Func<string> Match<T1, T2>(ICell t1, ICell t2, Func<string> f) where T1 : ICell where T2 : ICell { return t1 is T1 && t2 is T2 ? f : null; }

lasalas May 28 2015 at 22:22

Как-то так, например

public static string Match(ICell t1, ICell t2)
{
return Patterns
.Select(x => x(t1, t2))
.First(x => x != null)
();
}

private static readonly Func<ICell, ICell, Func>[] Patterns =
{
(t1, t2) => Match<RedCell, RedCell>(t1, t2, () => «красное на красном»),
(t1, t2) => Match<GreenCell, BlueCell>(t1, t2, () => «побережье»),
(t1, t2) => (() => t1.Color + "\t-->\t" + t2.Color)
};

private static Func Match<T1, T2>(ICell t1, ICell t2, Func f)
where T1: ICell
where T2: ICell
{
return t1 is T1 && t2 is T2? f: null;
}

PS: Похоже не работает форматирование

lasalas May 28 2015 at 22:29

Можно сделать еще компактнее, но более грубо

public static string Match(ICell a, ICell b)
{
return (Match<RedCell, RedCell>(a, b, () => «красное на красном»)
?? Match<GreenCell, BlueCell>(a, b, () => «побережье»)
?? (() => a.Color + "\t-->\t" + b.Color))
();
}

Johanan May 28 2015 at 23:11

Понял теперь вашу идею. Смотрите, вы всё равно не уходите от динамического приведения типов. Например, если я прошу вас вывести не «красное на красном», а что-нибудь из открытых свойств ячейки, вам всё равно придётся приводить тип. А если так, то наша беседа сводится к другому вопросу: что лучше — обычный посетитель или перебор типов через switch? Убийственного аргумента в пользу первого у меня нет. Но, например, если добавляем новый элемент, а использована динамическая типизация, уже куда сложнее найти все места, которые нужно обновить, чтобы поддержать его (предполагаем, что таких switch'ей у нас довольно много), легче что-то пропустить и получить потом runtime exception.
В нашем случае, когда обработка по умолчанию задана исключений не будет, но мы получим какой-то общий объект вместо интересующего нас частного случая. Узнаем об этом тоже, скорее всего, в runtime.

Проще всего, наверное, задачу вообще решить через dynamic, тогда не нужно даже делать явной проверки типов, а если мы укажем обработку по умолчанию, то, опять же, исключения не будет, но там свои сложности (см. например статью по ссылке, которую я приводил).

Обобщая вышесказанное: 1) при явном приведении типов больше вероятности получить ошибку на этапе исполнения 2) мне было интересно решить задачу без явного приведения типов, что тоже немаловажно.

lasalas May 29 2015 at 07:12

1. Не совсем понятно, почему надо бояться приведения типов и откуда должны взяться runtime exceptions, раз типизация статически проверяется компилятором.
2. То что я описал — тот же самый visitor, только в профиль и без макияжа.
3. Можно слегка доработать Match<>(), чтобы стали доступны фичи конкретных типов:

private static Func Match<T1, T2>(ICell t1, ICell t2, Func<T1, T2, string> f)
where T1: ICell
where T2: ICell
{
if (t1 is T1 && t2 is T2)
return () => f((T1)t1, (T2)t2);
return null;
}

…
(t1, t2) => Match<GreenCell, BlueCell>(t1, t2, (x,y) => «побережье: » + x.GreenFeature + ", " + y.BlueFeature),
…

DrReiz May 29 2015 at 15:30

Производительность! Производительность — основное преимущество двойной диспетчеризации по сравнению с pattern matching-ом.
Двойная диспетчеризация — это два virtcall-а на один вызов. Паттерн матчинг — это N проверок типов на каждый вызов.

lasalas May 29 2015 at 15:39

Зависит от реализации. Но особой разницы быть не должно.

DrReiz May 29 2015 at 17:07

Какие компиляторы умеют разворачивать паттерн матчинг по двум произвольным параметрам в C*O(1) и с C близкой к 1?

Lol4t0 May 29 2015 at 17:36

stackoverflow.com/questions/4767908/erlang-pattern-matching-performance

DrReiz May 29 2015 at 17:50

Цитата от туда «The internals usually have a pattern match compiler which turns an advanced pattern match into a simpler series of checks with the goal to minimize the number of checks».
Соответственно, это будет С*O(кол-во правил) с C меньше 1 (приблизительно: 0.3 — 0.7), а не O(1).

Lol4t0 May 29 2015 at 20:19

Ну, ортогонализация проверок все-таки позволяет сократить количество проверок в разы. Конечно, некоторое их колчество остается. Но дело в том, что в реальной жизни количество вариантов паттеронов не слишком велико. И хотя ассимптотически они будут медленнее двух виртуальных вызовов, не надо забывать, что virtual call является большим барьером оптимизации, чем сравнение.

Я бы устроил тестирование, но не могу придумать задачку под него

DrReiz May 29 2015 at 20:40

В трансляторах (особенно оптимизирующих) очень много паттерн матчинга.

lasalas May 29 2015 at 20:23

Можно представить (и реализовать) компилятор с любой степенью оптимизации сопоставления: со сбалансированныеми деревьями, хэшами, кэшами…

Но это скорей рассуждения из серии «может ли бог создать такой камень, который не сможет поднять?» :)

Что-то мне подсказывает, что если список сопоставления очень велик и разнообразен, то, видимо, имеются серьезные проблемы в архитектуре и решать надо именно их

Mrrl May 29 2015 at 06:52

А если ввести список пар (Match — обработчик), который можно пополнять снаружи, то и код функции Match(ICell,ICell) при добавлении нового цвета менять не придётся. Правда, от операции as внутри обработчиков избавиться не удастся.

Trueteller May 28 2015 at 23:16

На мой взгляд, показать выразительность языка не очень удалось. На F# с pattern matching получилось бы гораздо выразительные.
Обильное применение паттернов для решения задачи, которую можно было бы решить в несколько строк, свидетельствует скорее о нехватке языковых конструкций.
Плюс нарушение SOLID принципов, дупликация кода…
Возможно, это решение имело больше плюсов в вашей бизнес задаче из реальной жизни.
Спасибо за статью!

Johanan May 28 2015 at 23:43

Вам спасибо отзыв!
Не было цели доказать, что C# — самый выразительный язык. На F# match действительно куда проще решил бы эту задачу, ну так там и наследования не приветствуется, а вместо него Union.
Я хотел скорее показать, то такая задача на C# в принципе разрешима при условии, что мы не создаём (N + const) классов. Для меня, по крайней мере, это было не очевидно.

Про SOLID вы что именно имеете в виду? Что я смешал строителя и посетителя, или что-то другое?

Trueteller May 29 2015 at 00:01

В основном, Open-closed. Если надо будет добавить класс YellowCell, придется менять все вспомогательные классы.

Johanan May 29 2015 at 00:08

А, ну тут иначе не совладать с задачей. И я бы даже не сказал, что это так уж плохо. Да, мне придётся менять вспомогательные классы, но, меняя их, я хотя бы задумаюсь, какими именно правилами должны пользоваться все мои конкретные обработчики для жёлтой клетки.
Раз речь зашла о F# — что будет если мы добавим новый тип в unit? Нам придётся обновить все использования его и указать, что делать функции в случае жёлтой клетки. И так ли это плохо?

Trueteller May 29 2015 at 00:15

Если новый тип не требует специального поведения, F# код или реализация «в лоб» (как у lasalas) не изменятся.
Если требует специального поведения — изменится в одном месте, а не 3х связаных классах.

Johanan May 29 2015 at 18:54

Тут мне остаётся вам поверить — я не так хорошо знаю F#. Или, может, вы пример приведёте? Любопытно разобраться.

Lol4t0 May 29 2015 at 00:06

И ТУТ В ТРЕД ВРЫВАЕТСЯ HASKELL

-- цвета (кто же рабоатет со строками)
data Color = Red | Blue | Green deriving (Show)

-- интерфес
class Colored a where
	getColor :: a -> Color

--- проверка
process :: Colored a => a -> a -> String
process a b = process' (getColor a) (getColor b)

process' Red Red = "Red on Red"
process' Green Blue = "Coast"
process' a b = show a ++ " --> " ++ show b


data MyColor = MyRed | MyGreen | MyBlue deriving (Read)

-- имплементация интерфейса
instance Colored MyColor where
	getColor MyRed = Red
	getColor MyGreen = Green
	getColor MyBlue = Blue


main = interact $ unlines . map ((\[a, b] -> process (read a::MyColor) (read b)) . words) . lines

Извините

UFO just landed and posted this here

Johanan May 29 2015 at 18:57

Ну, да. Кто бы спорил, что функциональные языке с такой задачкой на раз справляются. Но за пример спасибо, хороший!

michael_v89 May 29 2015 at 08:02

Мне почему-то кажется, что наследовать красную ячейку от ячейки — это примерно то же самое, как наследовать квадрат от прямоугольника. Если не секрет, какая была реальная задача?

Johanan May 29 2015 at 18:59

Было дерево, где элементы — узлы. Наружу выставлены потомки списком и только. А в значении своя логика, вот с ней и нужно было разбираться.

middle May 29 2015 at 11:50

А вот как это выглядит в языке с нормальной множественной диспетчеризацией. Common Lisp:

(defclass icell ()
  ())

(defclass red-cell (icell)
  ())

(defclass blue-cell (icell)
  ())

(defclass green-cell (icell)
  ())


(defgeneric colors (arg1 arg2)
  )

(defmethod colors ((a icell) (b icell))
  (format nil "~S --> ~S" a b))

(defmethod colors ((a green-cell) (b blue-cell))
  "побережье")

(defmethod colors ((a red-cell) (b red-cell))
  "красное на красном")

Johanan May 29 2015 at 19:03

А если определить, кроме generic только два метода с такой сигнатурой (icell, red-cell) и (red-cell, icell), а потом вызвать с двумя красными, то какой вызовется метод?

middle May 29 2015 at 19:45

В стандартном способе топологической сортировки методов вызовется (red-cell, icell). Можно сделать свой, если надо по-другому.

lasalas May 29 2015 at 13:36

match(red, red, «красное на красном» ).
match(green, blue, «побережье»).
match(X,Y, S) :- concat([X,' --> ', Y], S).

:- match(green, white, S), write(S).

(Prolog)

middle May 29 2015 at 19:51

Провокационный вопрос: а можно сделать подкласс от атома red? ;) Насколько это гибко и расширяемо?

lasalas May 29 2015 at 20:14

Разумеется, Prolog (классический) не поддерживает ООП. Но извратиться всегда можно ;)

expands(X, X).
expands(dark_red, red).
expands(light_green, green).
…

match(X, Y, «красное на красном» ) :- expands(X, red), expands(Y, red).
match(X, Y, «побережье» ) :- expands(X, green), expands(Y, blue).
…

:- match(dark_red, red, S), write(S).

Show the best of all time