Все существующие программы. Часть 9
Мы здесь, кажется, столкнулись с некоторой проблемой с производительностью. Мы можем напустить на этот код профайлер и в обычной ситуации я бы порекомендовал именно это. Но в этом случае давайте решим эту проблему аналитически. Предположим, что мы пытаемся решить эту задачу с нашей предыдущей грамматикой, скажем, S[6]. Помимо всего прочего, это требует от нас найти PARENEND[5], BRACKETEND[5] и т.д., каждое из которых требует найти S[4]. Короче говоря, мы находим S[4] четыре раза, каждый раз, когда мы определяем S[6]. При этом каждый раз мы находим S[2] четыре раза, т.е. в общем случае шестнадцать раз… и, скорее всего, вы начинаете понимать, в чем заключается проблема с производительностью.
Существует старое выражение, которое гласит, что выполнение одной и той же работы дважды, ожидая при этом одинаковых результатов, является признаком безумия. (Кстати, это не является настоящим определением термина безумие, просто так говорят.) Но LINQ проектировался для работы с базами данных, поэтому вы можете выполнить один и тот же запрос дважды и получить при этом разные результаты, если данные в базе данных будут изменены, и LINQ не знает, что «базой данных» в этом случае являются вычисления, результат которых каждый раз одинаков. Мы пессимистически предполагаем, что результаты будут каждый раз разными и в огромном объеме вычисляем повторно результаты, которые мы только что получили и отбросили.
Мы можем решить эту проблему пожертвовав памятью в обмен на производительность. Мы выполним вычисление S[4] один раз, и когда мы запросим это значение в следующий раз, то просто вернем предыдущий результат. Прежде всего, помните, что результатом выполнения запроса LINQ является объект, который представляет запрос, а не результат запроса; давайте, путем помещения результатов в List убедимся, что мы будем кэшировать результаты запроса, а не сам запрос. Мы можем написать маленький «запоминатель» (memoizer):
private Dictionary<Tuple<string, int>, List<string>> memoizer =
new Dictionary<Tuple<string, int>, List<string>>();
public IEnumerable<string> All(string symbol, int substitutions)
{
List<string> results;
var tuple = Tuple.Create(symbol, substitutions);
if (!memoizer.TryGetValue(tuple, out results))
{
results = AllCore(symbol, substitutions).ToList();
memoizer.Add(tuple, results);
}
return results;
}
private IEnumerable<string> AllCore(string symbol, int substitutions)
{
// тот же код, что и ранее.
}
и теперь мы заменили проблему со скоростью выполнения проблемой избыточного расхода памяти. :-)
Но этот вариант вполне подходит. Теперь я получил инструмент, который я могу использовать для генерации миллионов синтаксически корректных тестов для любой части компилятора, который я выберу для тестирования. Например, вот несколько строк результатов перечисления упрощенной грамматики объявления классов, о которой я говорил ранее:
public class a { }
public class b : a { }
public class a < a > { }
public class c < a , a > { }
Довольно гладко!
Мы зашли значительно дальше, чем я ожидал, когда начал писать о генерации всех двоичных деревьев пару месяцев назад. Я надеюсь, вам понравилось это небольшое путешествие в элементарную компьютерную лингвистику точно также, как и мне.