В предыдущей загадке было предложено написать код, который вычислял бы длину последовательности. На самом деле, эта задачка была взята не из головы, а с замечательного сайта http://projecteuler.net. Он посвящен решению математических задач на различных языках программирования. У каждого пользователя на сайте есть свой рейтинг, как и у каждого языка программирования(кстати, большинство задач решается например на c/c++, а большинство «решающих задачи» из США).
Про этот сайт я узнал из статьи Билла Вагнера. В ней он предлагает свой способ решения задачи.
Для начала Билл предлагает решить задачу с помощью одной рекурсивной функции:
private static long Generate(long n)
{
if (n == 1) { return 1; }
var next = (n % 2 == 0) ? n / 2 : 3 * n + 1;
return Generate(next) + 1;
}
и обычного LINQ-запроса:
var answer = (from StartingValue in Enumerable.Range(1, 999999)
let SequenceSize = Generate(StartingValue)
orderby SequenceSize descending
select new { StartingValue, SequenceSize }).First();
Это работает и дает правильный ответ, но Билл этим решением не слишком удовлетворен, т.к. этот процесс занимает примерно 15 секунд на его портативном коммуникаторе.
Как сделать это быстрей? Билл предлагает метод, названым Memoization. Мы же на русский манер будем его называть «Меморизацией». В основе этого метода лежит сохранение результата подсчетов и последующий возврат к сохраненному результату, а не повторный подсчет. Это может обеспечить выигрыш в нашей рекурентной функции «Generate». К примеру меморизация результата для числа 64 означает сохранение подсчетов для чисел 64, 32, 16, 8, 4, 2 и 1.
Можно изменить метод «Generate», чтобы обеспечить хранение для подсчитанных ранее результатов:
private static Dictionary<long, long> StoredResults = new Dictionary<long, long>();
private static long Generate(long n)
{
if (StoredResults.ContainsKey(n))
return StoredResults[n];
if (n == 1)
{
StoredResults[n] = 1;
return 1;
}
var next = (n % 2 == 0) ? n / 2 : 3 * n + 1;
var answer = Generate(next) + 1;
StoredResults[n] = answer;
return answer;
}
Но в чем смысл? Здесь нет повторного использования ранее полученных значений.
Далее, Билл предлагает написать Generic функцию для меморизации, которая запоминала бы какую угодно функцию с одной переменной. Пост Вэса Дайера объясняет эту технологию в деталях.
Меморизация – это Generic метод, который абстрагируется как от типа параметра, так и от типа результата.
// Что такое Func?
// Это делегат из пространства System:
// public delegate TResult Func<T, TResult>(T arg);
// Добавляем метод Memoize классу Func<T, TResult>
// RTFM: Методы расширения (http://msdn.microsoft.com/ru-ru/library/bb383977.aspx)
public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
{
// Это кеш. Он статический.
var previousResults = new Dictionary<T, TResult>();
// Заменяем функцию function новой функцией, которая дергает
// function() только тогда, когда результата для конкретного
// аргумента еще нет в кеше.
return arg =>
{
if (previousResults.ContainsKey(arg))
return previousResults[arg];
else
{
TResult result = function(arg);
previousResults.Add(arg, result);
return result;
}
};
}
Первый вопрос, который может у вас возникнуть: как на самом деле работают предыдущие результаты(previousResults). Это локальная переменная, а не статическая. Как она может существовать вне пределов метода?
Вот это и является волшебством «замыкания«. Memoize не возвращает значения, она возвращает некоторую функцию, которая позволяет вам найти это значение поздней.
Далее осталось объявить и определить функцию вычисления длины последовательности и заменить ее на наш «кеширующий» метод:
static void Main()
{
// Обявляем функцию вычисления длины последовательнсоти.
Func<long, long> GenerateSequenceSize = null;
// Определяем ее (она рекурсинвая и трудоемкая).
GenerateSequenceSize = (long n) =>
{
if (n == 1)
{
return 1;
}
var next = (n % 2 == 0) ? n / 2 : 3 * n + 1;
return GenerateSequenceSize(next) + 1;
};
// Заменяем эту функцию ее "кеширующим" заместителем.
GenerateSequenceSize = GenerateSequenceSize.Memoize();
// Перебор чисел с использованием чудо-функции и LINQ.
var answer = (from StartingValue in Enumerable.Range(1, 999999)
let SequenceSize = GenerateSequenceSize(StartingValue)
orderby SequenceSize descending
select new { StartingValue, SequenceSize }).First();
// Вывод результата, занавес.
Console.WriteLine(answer);
Console.ReadLine();
}
Надеюсь, вам этот пост поможет сократить время выполнения многих ваших программ.
P.S. Спасибо Ляпину Дмитрию за комментирование кода.
Recent Comments