c# - 迭代存储在集合中的无序元素对

Question

在 C# 中，我有一组独特的元素，我想为每个无序对高效地执行一些代码。例如，如果我的容器包含 {a,b,c}，则无序对为 (a,b)、(a,c) 和 (b,c)。问题出现在执行 2-opt 优化的范围内，因此效率是一个问题。

• 我目前的解决方案如下:

  foreach(var a in container) 
  {
      foreach(var b in container)
      {
          if (a < b)
          {
               // execute code    
          }
      }
   }
  

  显然，如果运算符 [] 可用于获取第 i 个元素(即，如果底层数据结构是列表)，则可以轻松修改此方法。但是对于所有其他容器，解决方案取决于是否存在一些比较功能，效率不高。

• 我还尝试了一种基于 LINQ 语句的公式，它只生成每个所需的对一次。然而，正如预期的那样，这比第一种方法慢得多。这也适用于使用 ElementAt 的解决方案。

编辑:这里是使用的(改进的)LINQ 代码:

var x = from a in container
        from b in container
        where a < b 
        select new KeyValuePair<int,int>(a,b);

与其他解决方案相比，执行速度仍然慢了 3-5 倍。

• 这是我在 C++ 中的实现方式(获得良好的效率):

  for(auto it1 = container.begin(); it1!=container.end(); ++it1) 
  {
      auto it2 = it1;
      for(++it2; it2!=container.end(); ++it2) 
      {
          // execute code    
      }
   }
  

  不幸的是，要将其转换为 C#，需要克隆(内部使用的)枚举器，而语言本身不支持它。

有没有人有更好的想法/解决方案？

Answer 1

您是否尝试先将元素复制到列表中，然后使用索引器 ( [i]) 运算符执行算法？由于该算法无论如何都具有二次运行时间，因此在其前面进行线性复制操作可能可以忽略不计。您必须自己找出小型、中型和大型容器的实际运行时间...

我认为这可能值得一试，这可能比每次都使用比较运算符要快得多。

您还可以检查容器的类型是否为 IList<T>并跳过复制操作。