Так как F# 2.0 стал частью VS2010, я интересуюсь F#. Я задался вопросом какой смысл того, чтобы использовать его. Я читал немного, и я сделал сравнительный тест для измерения вызова функций. Я использовал функцию Ackermann :)
C#
sealed class Program
{
public static int ackermann(int m, int n)
{
if (m == 0)
return n + 1;
if (m > 0 && n == 0)
{
return ackermann(m - 1, 1);
}
if (m > 0 && n > 0)
{
return ackermann(m - 1, ackermann(m, n - 1));
}
return 0;
}
static void Main(string[] args)
{
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
Console.WriteLine("C# ackermann(3,10) = " + Program.ackermann(3, 10));
stopWatch.Stop();
Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");
Console.ReadLine();
}
}
C++
class Program{
public:
static inline int ackermann(int m, int n)
{
if(m == 0)
return n + 1;
if (m > 0 && n == 0)
{
return ackermann(m - 1, 1);
}
if (m > 0 && n > 0)
{
return ackermann(m - 1, ackermann(m, n - 1));
}
return 0;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
clock_t start, end;
start = clock();
std::cout << "CPP: ackermann(3,10) = " << Program::ackermann(3, 10) << std::endl;
end = clock();
std::cout << "Time required for execution: " << (end-start) << " ms." << "\n\n";
int i;
std::cin >> i;
return 0;
}
F#
// Ackermann
let rec ackermann m n =
if m = 0 then n + 1
elif m > 0 && n = 0 then ackermann (m - 1) 1
elif m > 0 && n > 0 then ackermann (m - 1) (ackermann m (n - 1))
else 0
open System.Diagnostics;
let stopWatch = Stopwatch.StartNew()
let x = ackermann 3 10
stopWatch.Stop();
printfn "F# ackermann(3,10) = %d" x
printfn "Time required for execution: %f" stopWatch.Elapsed.TotalMilliseconds
Java
public class Main
{
public static int ackermann(int m, int n)
{
if (m==0)
return n + 1;
if (m>0 && n==0)
{
return ackermann(m - 1,1);
}
if (m>0 && n>0)
{
return ackermann(m - 1,ackermann(m,n - 1));
}
return 0;
}
public static void main(String[] args)
{
System.out.println(Main.ackermann(3,10));
}
}
Затем
C# = 510 мс
C++ = 130 мс
F# = 185 мс
Java = Stackoverflow :)
Действительно ли это - питание F# (кроме небольшого объема кода), Если мы хотим использовать .NET и получить немного более быстрое выполнение? Я могу оптимизировать какой-либо из этих кодов (особенно F#)?
ОБНОВЛЕНИЕ. Я избавился от Консоли. WriteLine и выполненный C# кодируют без отладчика: C# = 400 мс
Я считаю, что в данном случае разница между C # и F # заключается в оптимизации хвостового вызова.
Хвостовой вызов - это когда у вас есть рекурсивный вызов, который выполняется "последним" в функции. В этом случае F # фактически не генерирует инструкцию вызова, а вместо этого компилирует код в цикл (поскольку вызов является «последним делом», мы можем повторно использовать текущий кадр стека и просто перейти к началу метода) .
В вашей реализации ackermann
два вызова являются хвостовыми вызовами, и только один из них нет (тот, где результат передается в качестве аргумента другому ackermann
вызов). Это означает, что версия F # на самом деле вызывает инструкцию «вызова» (намного?) Реже.
В целом профиль производительности примерно такой же, как профиль производительности C #. Здесь довольно много сообщений, связанных с производительностью F # и C #:
Это вроде как связано с вызовом функций, поскольку это обычный метод сокращения вызовов функций.
Вы можете сделать этот тип рекурсивной функции быстрее с помощью мемоизации (кэширования). Вы также можете сделать это в C# (пример.) Я получил 18 мс.
open System.Collections.Generic
let memoize2 f =
let cache = Dictionary<_, _>()
fun x y ->
if cache.ContainsKey (x, y) then
cache.[(x, y)]
else
let res = f x y
cache.[(x, y)] <- res
res
// Ackermann
let rec ackermann =
memoize2 (fun m n ->
if m = 0 then n + 1
elif m > 0 && n = 0 then ackermann (m - 1) 1
elif m > 0 && n > 0 then ackermann (m - 1) (ackermann m (n - 1))
else 0
)
Для F # вы можете попробовать встроенное ключевое слово.
Кроме того, как упоминалось на предыдущем плакате, версии C # и F # различаются из-за операторов Console.WriteLine.
Не имеет прямого отношения к вопросу, но достаточно интересен, чтобы упомянуть: попробуйте эту версию
let rec ackermann2 m n =
match m,n with
| 0,0 -> 0
| 0,n -> n+1
| m,0 -> ackermann2 (m-1) 1
| m,n -> ackermann2 (m-1) (ackermann2 m (n-1))
На моем ПК (VS2010, F# interactive) она почти на 50% быстрее, чем ваша версия при вычислении Аккермана 3 12.
Я не могу точно объяснить, почему такая разница в производительности. Думаю, это связано с тем, что компилятор F# переводит выражение match в оператор switch вместо серии операторов if. Возможно, также помогло размещение теста (m=0,n=0) первым.