我正在使用 c++、c# 和 java 实现 Floyd–Warshall 算法。在每种语言中，我在测试结果后都使用顺序和并行实现:
(消耗时间仅针对主要功能和读取文件，变量的 Inti 和...未测量。)
在这里下载源SourceCodes

C++

• IDE:Netbeans
• 编译器:MinGW-4.8.1
• 连续时间:9.333000
• 平行时间:2.539000
• 为 Pralel 使用 OpenMp

if NumOfThreads=1 then is Sequential else is Parallel

变量

#define n 1000 /* Then number of nodes */
double dist[n][n];

    void floyd_warshall(int NumOfThreads) {
    int i, j, k;
         omp_set_num_threads(NumOfThreads);
    for (k = 0; k < n; ++k)
       #pragma omp parallel for private(i,j)
        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
                    if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                     if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0))
                        dist[i][j] = dist[i][k] + dist[k][j];    }

Java

• IDE:Netbeans
• 编译器:Netbeans 默认
• 连续时间:11.632
• 平行时间:3.089
• -Xms512m -Xmx1024m
• 导入java.util.concurrent.Callable；
  导入 java.util.concurrent.ExecutionException;
  导入 java.util.concurrent.ExecutorService;
  导入 java.util.concurrent.Future;

Java 变量

 public final int numNodes =1000;

    public final double[][] costs= new double[numNodes][numNodes] ;

i did not put java code here because its working right ( i think )

c#

1. IDE:Visual Studio 2012
2. 编译器:Visual Studio 2012 默认
3. 连续时间:31.312
4. 平行时间:8.920
5. 使用 System.Threading.Tasks；

变量

  const int n = 1000;
    static double[,] dist = new double[n, n];

并行代码

   static  void floyd_warshall(ParallelOptions pOp)
    {
        int k;     
        for (k = 0; k < n; ++k)
            Parallel.For<int>(0, n, pOp, () => 0, (i, loop, j) =>
                {
              for (j = 0; j < n; ++j)
               if ((dist[i, k] * dist[k, j] != 0) && (i != j))
                  if ((dist[i, k] + dist[k, j] < dist[i, j]) || (dist[i, j] == 0))
                            dist[i, j] = dist[i, k] + dist[k, j];
                    return 0;
                }, (j) => { });

单一代码

 static void floyd_warshallSingle()
  {
      int i, j, k;
      for (k = 0; k < n; ++k)
          for (i = 0; i < n; ++i)
              for (j = 0; j < n; ++j)

                  if ((dist[i,k] * dist[k,j] != 0) && (i != j))

                      if ((dist[i,k] + dist[k,j] < dist[i,j]) || (dist[i,j] == 0))
                          dist[i,j] = dist[i,k] + dist[k,j];
  }

我的 C# 实现有什么问题？
都使用同一个文件
现在我的问题是为什么用 C# 解决这个算法需要更多时间？ Java 和 C++ 的运行时间几乎相同，但我认为我使用 C# 的实现是错误的，因为 C# 和 C++ 之间的差异很奇怪!
请帮助我改进我的 C# 实现或说出一些原因谢谢!

编辑1

我将数组更改为锯齿状数组，结果更改为:

• 连续时间:19.22
• 平行时间:4.903

C# 和 C++ 或 Java 之间仍然存在巨大差异!知道为什么吗？
新变量

const int n = 1000;
    static double[][] dist = new double[n][];

新代码:

static void floyd_warshallSingle()
  {
      int i, j, k;
      for (k = 0; k < n; ++k)
          for (i = 0; i < n; ++i)
              for (j = 0; j < n; ++j)

                  if ((dist[i][k] * dist[k][j] != 0) && (i != j))

                      if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0))
                          dist[i][j] = dist[i][k] + dist[k][j];
  }



   static  void floyd_warshall(ParallelOptions pOp)
    {
        int k;     
        for (k = 0; k < n; ++k)
            Parallel.For<int>(0, n, pOp, () => 0, (i, loop, j) =>
                {
                    for (j = 0; j < n; ++j)
                        if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                            if ((dist[i][ k] + dist[k][j] < dist[i][ j]) || (dist[i][j] == 0))
                                dist[i][ j] = dist[i][k] + dist[k][j];

                    return 0;
                }, (j) => { });
    }

最佳答案

确定是否是数组边界检查，或者至少确定数组边界检查是否是问题的部分的一种方法是删除一些索引计算。例如:

    static void floyd_warshallSingle()
    {
        int i, j, k;
        for (k = 0; k < n; ++k)
        {
            var distk = dist[k];
            for (i = 0; i < n; ++i)
            {
                var disti = dist[i];
                for (j = 0; j < n; ++j)
                    if ((i != j) && (disti[k] * distk[j] != 0))
                        if ((disti[j] == 0) || disti[k] + distk[j] < disti[j])
                            disti[j] = disti[k] + distk[j];
            }
        }
    }

这里我所做的就是使用 distk 作为对 dist[k] 的引用。我怀疑编译器已经在进行优化，这很可能是您如何实现从矩形数组到锯齿状数组时获得的性能提升。但值得一试。

另外，您说过您在没有附加调试器的情况下运行。我假设您也在运行发布版本？这三个程序(C++、Java 和 C#)是否都运行相同的位数？也就是说，它们都是 64 位可执行文件吗？所有 32 位可执行文件？使用 C# 时要小心，因为可以在项目选项中打开“首选 32 位”标志。这可能会导致您在使用“任何 CPU”进行编译时以 32 位模式运行，即使是在 64 位系统上也是如此。

关于java - 比较 c#、c++ 和 java 性能(c# 的奇怪行为)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27079644/