Java vs C# 算法执行

Question

我有一个用 Java 和 C# 编写的 N 皇后问题。您可以找到有关 8 皇后问题的更多信息 here .

Java代码如下:

package nqueens;
import java.util.Arrays;
public class NQueens {
  public static void main(String args[]) {
    int n = 13;
    int[] ploca = new int[n];
    postaviKraljicuNaPlocu(0, ploca);
  }
  private static void postaviKraljicuNaPlocu(int Ki, int[] ploca) {
    int n = ploca.length;
    if (Ki == n) {
      System.out.println(Arrays.toString(ploca));
    } else {
      for (int kolona = 0; kolona < n; kolona++) {
        if (jeLiSigurnoMjesto(kolona, Ki, ploca)) {
          ploca[Ki] = kolona;
          postaviKraljicuNaPlocu(Ki + 1, ploca);
          ploca[Ki] = -1;
        }
      }
    }
  }
  private static boolean jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca) {
    for (int i = 0; i < Ki; i++) {
      if (ploca[i] == kolona) { 
        return false;
      }
      if (Math.abs(ploca[i] - kolona) == Math.abs(i - Ki)) {
        return false;
      }
    }
    return true;
  }
}

这是 C# 代码:

using System;
namespace nkraljica
{
    public class NKraljica
    {
        public static void Main(string[] args)
        {
            int n = 13;
            int[] ploca = new int[n];
            postaviKraljicuNaPlocu(0, ploca);
        }
        private static void postaviKraljicuNaPlocu(int Ki, int[] ploca)
        {
            int n = ploca.Length;
            if (Ki == n)
            {
                Console.WriteLine(string.Join("", ploca));
            }
            else
            {
                for (int kolona = 0; kolona < n; kolona++)
                {
                    if (jeLiSigurnoMjesto(kolona, Ki, ploca))
                    {
                        ploca[Ki] = kolona;
                        postaviKraljicuNaPlocu(Ki + 1, ploca);
                        ploca[Ki] = -1;
                    }
                }
            }
        }
        private static bool jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca)
        {
            for (int i = 0; i < Ki; i++)
            {
                if (ploca[i] == kolona)
                {
                    return false;
                }
                if (Math.Abs(ploca[i] - kolona) == Math.Abs(i - Ki))
                {
                    return false;
                }
            }
            return true;
        }
    }
}

对于 N=13，Java 代码在 1.7 秒内完成，但 C# 在 17.3 秒内完成。为什么差别这么大？

Answer 1

要真正弄清问题的根源，您需要分析 C# 代码以确定它在哪里花费时间。过去，我使用过 dotTrace profiler成功完成这样的任务； Visual Studio 也有一个 built-in profiler ;可以找到更多建议here .

为了让我们对时差给出更多意见，您需要详细描述您的构建和运行环境。您是在构建调试还是(希望)发布？您使用的是什么版本的 .Net 和 Visual Studio？什么版本的 Java，以及什么构建工具？

话虽这么说，我在 VS 2008/.Net 3.5/Release build 中对你的 c# 代码进行了一些试验，并发现了以下内容:

• 在附加 Visual Studio 的情况下运行:
  • 运行代码的总时间约为 10.7 秒，可重复。
  • 如果我将您对 Console.WriteLine() 的调用替换为将结果保存在 StringBuilder 中的调用，则时间会减少到 4.9 秒。显然 Console.WriteLine 非常慢!
  • 如果我简单地消除对 Console.WriteLine() 的调用并用虚拟对象替换它们，则时间几乎没有变化。所以 StringBuilder 非常快。
  • 如果我用内联检查替换对 Math.Abs​​() 的调用，则时间会减少到 4.0 秒。可能 .Net 没有优化或内联对 Math.Abs​​() 的调用，而 Java 确实这样做了。
• 从命令行运行，或者在没有附加 Visual Studio 的情况下运行:
  • 使用 Console.WriteLine() 的总时间:9-10 秒，可重复。
  • 使用 StringBuilder 记录的总时间:3.0 秒。
  • 使用虚拟日志记录的总时间:3.0 秒。
  • Math.Abs​​() 的内联版本的总时间:1.6 秒。

由此，我得出结论:

1. 在附加 Visual Studio 的情况下运行会显着降低运行速度，即使在 Release模式下也是如此。 (另请参阅 here。)确保在计时性能时从命令行运行 Java 和 c# 可执行文件。

2. Console.WriteLine() 很慢 -- 慢到足以控制算法所用的时间。 Java 等价物可能更快，如果是这样的话，这可以解释一些差异。

3. 可能 Java 在内联或优化对 Math.Abs​​() 的调用方面做得更好。手动内联调用的改进非常显着。

我的电脑上没有安装 Java，无法自己运行比较。

这是我用来做测试的代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Timers;
using System.Diagnostics;

namespace nkraljica
{
    public class NKraljicaMain
    {
        public static void Main(string[] args)
        {
            int n = 13;

            var stopwatch = new Stopwatch();

            stopwatch.Reset();
            stopwatch.Start();
            Abs.NKraljica.postaviKraljicuNaPlocu(n, Console.WriteLine);
            stopwatch.Stop();
            var consoleElapsed = stopwatch.Elapsed;

            stopwatch.Reset();
            stopwatch.Start();
            StringBuilder sb1 = new StringBuilder();
            Abs.NKraljica.postaviKraljicuNaPlocu(n, s => sb1.AppendLine(s));
            stopwatch.Stop();

            var sbElapsed = stopwatch.Elapsed;

            stopwatch.Reset();
            stopwatch.Start();
            string lastLine = null;
            Abs.NKraljica.postaviKraljicuNaPlocu(n, s => lastLine = s);
            stopwatch.Stop();

            var nologElapsed = stopwatch.Elapsed;

            stopwatch.Reset();
            stopwatch.Start();
            StringBuilder sb2 = new StringBuilder();
            Inline.NKraljica.postaviKraljicuNaPlocu(n, s => sb2.AppendLine(s));
            stopwatch.Stop();

            var inlineElapsed = stopwatch.Elapsed;

            Debug.Assert(sb1.ToString() == sb2.ToString());

            Console.WriteLine(string.Format("Console logging time = {0}", consoleElapsed));
            Console.WriteLine(string.Format("StringBuilder logging time = {0}", sbElapsed));
            Console.WriteLine(string.Format("Dummy logging time = {0}", nologElapsed));
            Console.WriteLine(string.Format("Inline Abs + StringBuilder logging time = {0}", inlineElapsed));

            Console.ReadLine();
        }
    }
}

namespace nkraljica.Abs
{
    public class NKraljica
    {
        public static void postaviKraljicuNaPlocu(int n, Action<string> reportFunc)
        {
            int[] ploca = new int[n];
            postaviKraljicuNaPlocu(0, ploca, reportFunc);
        }

        private static void postaviKraljicuNaPlocu(int Ki, int[] ploca, Action<string> reportFunc)
        {
            int n = ploca.Length;
            if (Ki == n)
            {
                reportFunc(ploca.Aggregate(new StringBuilder(), (sb, i) => sb.Append(i)).ToString());
            }
            else
            {
                for (int kolona = 0; kolona < n; kolona++)
                {
                    if (jeLiSigurnoMjesto(kolona, Ki, ploca))
                    {
                        ploca[Ki] = kolona;
                        postaviKraljicuNaPlocu(Ki + 1, ploca, reportFunc);
                        ploca[Ki] = -1;
                    }
                }
            }
        }
        private static bool jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca)
        {
            for (int i = 0; i < Ki; i++)
            {
                if (ploca[i] == kolona)
                {
                    return false;
                }
                if (Math.Abs(ploca[i] - kolona) == Math.Abs(i - Ki))
                {
                    return false;
                }
            }
            return true;
        }
    }
}

namespace nkraljica.Inline
{
    public class NKraljica
    {
        public static void postaviKraljicuNaPlocu(int n, Action<string> reportFunc)
        {
            int[] ploca = new int[n];
            postaviKraljicuNaPlocu(0, ploca, reportFunc);
        }

        private static void postaviKraljicuNaPlocu(int Ki, int[] ploca, Action<string> reportFunc)
        {
            int n = ploca.Length;
            if (Ki == n)
            {
                reportFunc(ploca.Aggregate(new StringBuilder(), (sb, i) => sb.Append(i)).ToString());
            }
            else
            {
                for (int kolona = 0; kolona < n; kolona++)
                {
                    if (jeLiSigurnoMjesto(kolona, Ki, ploca))
                    {
                        ploca[Ki] = kolona;
                        postaviKraljicuNaPlocu(Ki + 1, ploca, reportFunc);
                        ploca[Ki] = -1;
                    }
                }
            }
        }
        private static bool jeLiSigurnoMjesto(int kolona, int Ki, int[] ploca)
        {
            for (int i = 0; i < Ki; i++)
            {
                if (ploca[i] == kolona)
                {
                    return false;
                }
                int diff1 = ploca[i] - kolona;
                int diff2 = i - Ki;
                if (diff1 == diff2 || diff1 == checked(-diff2))
                {
                    return false;
                }
            }
            return true;
        }
    }
}