Поэтому недавно я приступил к проекту кодирования, чтобы попытаться создать некоторый код для математического создания способа изобразить, насколько похожи две строки. В своем исследовании я нашел множество примеров в Интернете, которые помогли мне создать код, который я хотел. У меня есть ошибка с одной, которую я обнаружил, которая при ее запуске создает то, что я называю, экспоненциальные циклы. Это не бесконечный цикл, он работает и решает проблемы, но чем длиннее строки, которые я передаю в метод, тем экспоненциально дольше работает метод. Код здесь ниже
public static int LevenshteinDistance(this string source, string target)
{
Console.WriteLine("Start of method");
if (source.Length == 0) { return target.Length; }
if (target.Length == 0) { return source.Length; }
int distance = 0;
Console.WriteLine("Distance creation");
if (source[source.Length - 1] == target[target.Length - 1]) { distance = 0; }
else { distance = 1; }
Console.WriteLine("Recursive MethodCall");
return Math.Min(Math.Min(LevenshteinDistance(source.Substring(0, source.Length - 1), target) + 1,
LevenshteinDistance(source, target.Substring(0, target.Length - 1))) + 1,
LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
}
Таким образом, для меньших строк этот метод работает просто отлично, однако, когда я начинаю передавать такие вещи, как адреса или длинные имена, это занимает много времени. На самом деле, пока я полностью распустил этот метод и написал другой (я предоставлю его, если кто-то захочет, но это не важно для вопроса), который служит моей цели, но в интересах решения проблем и обучения, я попытался выяснить именно поэтому это заняло так много времени при рекурсивном кодировании. Я прошел свой код с ручкой и бумагой в режиме отладки, и когда я дошел до рекурсивного вызова здесь
return Math.Min(Math.Min(LevenshteinDistance(source.Substring(0, source.Length - 1), target) + 1,
LevenshteinDistance(source, target.Substring(0, target.Length - 1))) + 1,
LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
}
И я могу четко определить, что происходит для этих частей
return Math.Min(***Math.Min(LevenshteinDistance(source.Substring(0, source.Length - 1), target) + 1,
LevenshteinDistance(source, target.Substring(0, target.Length - 1))) + 1,***
LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
}
Я попытался выделить жирным шрифтом и курсивом ту часть, которую я имею в виду, ту часть, вокруг которой стоит «***». Приступая к этой части, я понимаю, но затем в следующей части, третьем вызове LevenshteinDistance и его первой итерации, я начинаю терять фокус на рекурсии, как она работает и где начинается мое замешательство. Эта часть
LevenshteinDistance(source.Substring(0, source.Length - 1), target.Substring(0, target.Length - 1)) + distance);
}
Код из того, что я собрал, как только он достигает этого вызова, затем снова начинает выполнять первый вызов LevenshteinDistance и повторяет вызовы, которые он только что выполнил. Вот это я путаюсь. Почему он снова вызывает первую часть рекурсивного вызова, а затем вторую, и что заставляет время завершения кода увеличиваться в геометрической прогрессии?
Примечание. Время может не быть экспоненциальным в буквальном смысле, время для выполнения сравнения коротких строк составляло доли секунды, и как только строки стали немного длиннее, перемычка с доли секунды -> ~ 15 секунд -> 2:30 мин. -> 35 минут
2-е примечание: помечен как бесконечный цикл, поскольку экспоненциальный цикл не существует, и это несколько близко к нему.