Работающий программист
Забавы с C#. Часть 2
.png)
С возвращением! В своей прошлой статье (msdn.microsoft.com/magazine/dn754595) я кратко рассказал о том, как знакомство с другими языками программирования помогает яснее представить задачу проектирования, которая в ином случае показалась бы трудноразрешимой. Сделал я это на примере задачи, с которой мне довелось столкнуться много лет назад, когда я занимался консалтингом. От меня требовалось сверять список транзакций, хранящийся локально, с предположительно эквивалентным списком транзакций, хранящимся удаленно. Я должен был либо подтверждать совпадение по сумме транзакции (совпадение всего остального не гарантировалось даже для одной и той же транзакции), либо помечать несовпадающие элементы в конечном списке.
Я решил использовать F# для этого упражнения, так как это язык, с которым я хорошо знаком. Но, если честно, им мог бы быть другой язык вроде Scala, Clojure или Haskell. Любой функциональный язык сработал бы примерно так же. Здесь ключ не в самом языке или платформе, на которой он работает, а в концепциях функционального языка. Задача как раз хорошо решалась в функциональном стиле.
Решение на F#
Просто для того, чтобы освежить память, взгляните на F#-решение на рис. 1, прежде чем думать, как преобразовать его под C#.
Рис. 1. F#-решение для разрешения различающихся транзакций
type Transaction =
{
amount : float32;
date : DateTime;
comment : string
}
type Register =
| RegEntry of Transaction * Transaction
| MissingRemote of Transaction
| MissingLocal of Transaction
let reconcile (local : Transaction list)
(remote : Transaction list) : Register list =
let rec reconcileInternal outputSoFar local remote =
match (local, remote) with
| [], _
| _, [] -> outputSoFar
| loc :: locTail, rem :: remTail ->
match (loc.amount, rem.amount) with
| (locAmt, remAmt) when locAmt = remAmt ->
reconcileInternal (RegEntry(loc, rem) ::
outputSoFar) locTail remTail
| (locAmt, remAmt) when locAmt < remAmt ->
reconcileInternal (MissingRemote(loc) ::
outputSoFar) locTail remote
| (locAmt, remAmt) when locAmt > remAmt ->
reconcileInternal (MissingLocal(rem) ::
outputSoFar) local remTail
| _ ->
failwith "How is this possible?"
reconcileInternal [] local remote
Советую вернуться к моей прошлой статье, чтобы вспомнить синтаксис F#, используемый на рис. 1, особенно если вы мало знакомы с F#. Я тоже намерен возвращаться к нему по мере преобразования этого кода под C#.
Решение на C#
Для начала вам потребуются типы Transaction и Register. Тип Transaction прост. Это структурный тип с тремя именованными элементами, облегчающими моделирование этого типа как C#-класса:
class Transaction
{
public float Amount { get; set; }
public DateTime Date { get; set; }
public String Comment { get; set; }
}
Эти автоматические свойства делают этот класс почти таким же коротким, как и его эквивалент на F#. Откровенно говоря, если бы я намеревался сделать его точной копией того, что делает F#-версия, я должен был бы ввести переопределенные методы Equals и GetHashCode. Но для целей этой статьи сойдет и так.
С типом Register размеченного объединения (discriminated union) возникают сложности. Как и перечисление в C#, экземпляр типа Register может принимать одно из трех возможных значений (RegEntry, MissingLocal или MissingRemote). Но в отличие от перечисления в C# каждое из этих значений в свою очередь может содержать данные (два Transaction, совпадающие по RegEntry, или недостающий Transaction либо для MissingLocal, либо для MissingRemote). Хотя в C# было бы несложно создать три разных класса, эти три класса должны быть в какой-то мере связаны. Нам нужен List, который может содержать любой из этой троицы (но только из этой троицы) для возвращаемого вывода, как показано на рис. 2. Здравствуй, наследование.
Рис. 2. Применение наследования для включения трех разных классов
class Register { }
class RegEntry : Register
{
public Transaction Local { get; set; }
public Transaction Remote { get; set; }
}
class MissingLocal : Register
{
public Transaction Transaction { get; set; }
}
class MissingRemote : Register
{
public Transaction Transaction { get; set; }
}
Он не слишком сложен, просто не лаконичен. И если бы это был производственный код, я должен был бы добавить еще больше методов: Equals, GetHashCode и почти точно ToString. Хотя, возможно, есть способы сделать это более изящно для C#, я буду писать метод Reconcile довольно близко к его F#-оригиналу. По поводу оптимизаций будем переживать потом.
В F#-версии была «внешняя» открытая функция, рекурсивно вызывающая внутреннюю инкапсулированную функцию. Однако в C# нет концепции вложенных методов. Самое близкое, что могу написать, — два метода: один объявляется открытым, а другой — закрытым. Даже тогда это не совсем то же самое. В F#-версии вложенная функция инкапсулируется ото всех, даже от других функций в том же модуле. Но это максимум, чего мы можем добиться, так что смотрим на рис. 3.
Рис. 3. Вложенная функция инкапсулируется здесь
class Program
{
static List<Register> ReconcileInternal(List<Register> Output,
List<Transaction> local,
List<Transaction> remote)
{
// . . .
}
static List<Register> Reconcile(List<Transaction> local,
List<Transaction> remote)
{
return ReconcileInternal(new List<Register>(), local, remote);
}
}
В качестве отступления замечу, что теперь можно добиться рекурсивного подхода, «скрытого ото всех», написав внутреннюю функцию полностью как лямбда-выражение, на которое Reconcile ссылается как на локальную переменную. Однако, по-видимому, это будет чересчур раболепное следование оригиналу и не совсем уместным в C#.
Это не то, что станет делать большинство программистов на C#, но это дало бы примерно тот же результат, что и F#-версия. Внутри ReconcileInternal я должен явным образом извлекать используемые элементы данных. Затем явно расписать это в дереве if/else-if в противоположность более лаконичному и выразительному сравнению по шаблону (pattern match) в F#. Однако на самом деле это один и тот же код. Если локальный или удаленный список окажется пуст, я прекращаю рекурсию. Просто возвращаю результат и считаю дело сделанным:
static List<Register> ReconcileInternal(List<Register> Output,
List<Transaction> local,
List<Transaction> remote)
{
if (local.Count == 0)
return Output;
if (remote.Count == 0)
return Output;
Затем мне нужно извлечь «верхушки» каждого списка. И хранить ссылку на остаток каждого списка («хвостовую часть»):
Transaction loc = local.First();
List<Transaction> locTail = local.GetRange(1, local.Count - 1);
Transaction rem = remote.First();
List<Transaction> remTail = remote.GetRange(1, remote.Count - 1);
Это одно из мест, где я могу получить колоссальный проигрыш в производительности, если не буду внимателен. В F# списки неизменяемы, поэтому получение хвостовой части списка заключается в простом получении ссылки на второй элемент в списке. Никаких копий не делается.
Но в C# таких гарантий нет. А значит, я мог бы в итоге каждый раз создавать полные копии списка. Метод GetRange сообщает, что он создает поверхностные копии (shallow copies), подразумевая, что он создаст новый List. Но он будет указывать на элементы исходного Transaction. Это, вероятно, лучшее, на что я могу надеяться, не углубляясь в слишком экзотические конструкции. Если же этот код станет узким местом, используйте экзотику лишь в минимально необходимых дозах.
Вновь посмотрев на F#-версию, видно, что во втором сравнении по шаблону я на самом деле анализирую суммы в локальной и удаленной транзакциях, как показано на рис. 4. Поэтому я извлекаю и эти значения, а затем сравниваю их.
Рис. 4. F#-версия анализирует суммы в локальных и удаленных транзакциях
float locAmt = loc.Amount;
float remAmt = rem.Amount;
if (locAmt == remAmt)
{
Output.Add(new RegEntry() { Local = loc, Remote = rem });
return ReconcileInternal(Output, locTail, remTail);
}
else if (locAmt < remAmt)
{
Output.Add(new MissingRemote() { Transaction = loc });
return ReconcileInternal(Output, locTail, remote);
}
else if (locAmt > remAmt)
{
Output.Add(new MissingLocal() { Transaction = rem });
return ReconcileInternal(Output, local, remTail);
}
else
throw new Exception("How is this possible?");
}
К этому моменту довольно легко понять, что делает каждая ветвь дерева. Я добавляю новый элемент в список Output, затем рекурсивно прохожу по необработанным элементам локального и удаленного списков.
Заключение
Если решение на C# действительно такое элегантное, то зачем нужно было создавать его сначала на F#? Это трудно объяснить, пока вы сами не пройдете тот же процесс. В основном мне это понадобилось для выработки алгоритма. Моя первая попытка кончилась полной катастрофой. Я начинал с итераций по двум спискам, используя двойные циклы foreach. Попутно я пытался отслеживать состояние и, в конце концов, получил такую мешанину, которую не сумел бы отладить и за миллион лет.
Когда вы учитесь «думать по-другому» («think differently») (если одолжить знаменитый рекламный слоган одной знаменитой компьютерной компании, использовавшийся несколько десятилетий назад), это дает результаты — выбор самого языка здесь ни причем. Я мог бы легко проделать то же самое на Scala, Haskell или Clojure. Смысл не в наборе языковых средств, а в концепциях большинства функциональных языков, в частности рекурсии. Вот что помогло мне проломить мысленный тупик.
Отчасти это является причиной того, почему разработчики должны каждый год изучать новый язык программирования, как было впервые предложено одним из «прагматичных программистов», Дэйвом Томасом (Dave Thomas), получившим известность своими книгами по Ruby. Идеи витают в воздухе. И они проявляются, когда программисты проводят некоторое время со Scheme, Lisp, каким-то языком на основе стека вроде Forth или даже с языком на основе прототипов, таким как Io.
Если вы хотите почитать облегченное введение в целый ряд других языков вне платформы Microsoft .NET Framework, настоятельно рекомендую книгу Брюса Тейта (Bruce Tate) «Seven Languages in Seven Weeks» (Pragmatic Bookshelf, 2010). Вряд ли вы станете использовать их непосредственно на платформе .NET. Но иногда победа заключается в том, как мы думаем о задаче и структурируем решение, а вовсе не в создании повторно используемого кода.
Удачи в кодировании!
Тэд Ньюард (Ted Neward) — директор iTrellis по технологиям (эта компания предоставляет консалтинговые услуги). Автор и соавтор многочисленных книг, в том числе «Professional F# 2.0» (Wrox, 2010), более сотни статей, часто выступает на многих конференциях по всему миру; кроме того, имеет звание Microsoft MVP в области C#. С ним можно связаться по адресу ted@tedneward.com или ted@itrellis.com, если вы заинтересованы в сотрудничестве. Также читайте его блог blogs.tedneward.com.
Выражаю благодарность за рецензирование статьи эксперту Microsoft Линкольну Аткинсону (Lincoln Atkinson).