Здравствуйте, Nick_, Вы писали:
N_>В этой программе четыре пути исполнения, так как в ней два условных оператора. При этом один из путей неосуществим. Так как если x < 10, то также x < 20.
Честно говоря меня совершенно не напрягают лишние пути если я могу четко понять алгоритм. Приведенный упрощенный вариант мне тоже больше нравится. Но не из-за меньшего количества путей, а из-за того что он более четко выражен. В нем выделена общая процедура (reparent).
Так что я не стал бы все сваливать на избегание путей. Скорее при более четком выражении алгоритма нормализуется и количество путей.
Для сравнить я создал две реализации функции бинарного описка. Одну итеративную/императивную. Другую рекурсивную/функциональную:
using System;
using System.Collections.Generic;
class Program
{
public static int BinarySearchImperative<T>(T[] array, int lo, int hi, T value, IComparer<T> comparer)
{
while (lo <= hi)
{
int i = (lo + hi) >> 1;
int cmpResult = comparer.Compare(array[i], value);
if (cmpResult == 0)
return i;
else if (cmpResult < 0)
lo = i + 1;
else
hi = i - 1;
}
return ~lo;
}
public static int BinarySearchRecursive<T>(T[] array, int lo, int hi, T value, IComparer<T> comparer)
{
if (lo > hi)
return ~lo;
int i = (lo + hi) >> 1;
int cmpResult = comparer.Compare(array[i], value);
if (cmpResult < 0)
return BinarySearchRecursive(array, i + 1, hi, value, comparer);
else if (cmpResult > 0)
return BinarySearchRecursive(array, lo, i - 1, value, comparer);
else
return i;
}
static void Main(string[] args)
{
int[] array = new int[] { 2, 4, 7, 8, 10, 20, 22, 23, 24, 26 };
int ir = BinarySearchImperative(array, 0, array.Length - 1, 9, Comparer<int>.Default);
int rr = BinarySearchRecursive(array, 0, array.Length - 1, 9, Comparer<int>.Default);
Console.WriteLine("ir = {0} (~ir = {1})", ir, ~ir);
Console.WriteLine("rr = {0} (~rr = {1})", rr, ~rr);
}
}
По-моему, итеративный вариант проще в понимании. Так же он явно быстрее, так как нет затрат времени на передачу "баластных" параметров через параметры.
Так что подобные примеры яряд ли можно считать доказательством приемущества функционального стиля. Это скорее доказательство того, что есть более оптимальные пути реализации и люди умеющие их находить.
Кстати, интересно было бы глянуть на этот алгоритм на Хаскеле, Окамле и т.п. Интересно как без физического разрезания списка или поэлементного перебора получить середину...
... << RSDN@Home 1.1.4 beta 3 rev. 206>>