0

假设我有两个网格，每个网格包含 190000+ 条记录，名为 grid_A 和 grid_B，

对于 grid_A 中的每条记录，我想查找 grid_B 中是否有相同的记录。

grid_A 和 grid_B 具有相同的列，在我的情况下，它们的列是

col1 col2 col3 col4

他们的数据类型可能是

字符串数据时间双

到目前为止，我所做的是：

对于grid_A中的每一行，遍历grid_B中的所有行，并比较四个列

逐个。

代码显示如下：

        //loop grid_A
        foreach (UltraGridRow row in ultraGrid1.Rows)
        {
             List<object> lo = new List<object>();

             for (int i=0;i<4;i++)              //add col's value to ListA
             {
                  lo.Add(row.Cells[i].Value);
             }
             //loop grid_B
             foreach (UltraGridRow rowDist in ultraGrid2.Rows)
             {
                  List<object> loDist = new List<object>();
                  for (int ii=0;ii<4;ii++)              //add col's value to ListB
                  {
                       loDist.Add(rowDist.Cells[ii].Value);
                  }

                  if (CompareList(lo, loDist) == true)     //compare two List
                  {
                     break;
                  }
             }
        }




        //  the function compare two List
        private bool CompareList(List<object> a, List<object> b)
        {
             //Assert a.count==b.count
             for (int i=0;i<a.Count;i++)
             {
                   if (!CompareObject(a[i], b[i]))
                        return false;
             }

             return true;
        }


        //
        private bool CompareObject(object oa, object ob)
        {

              // object is string
              if (oa.GetType() == typeof(System.String))
              {
                    try
                    {
                            string strOb = Convert.ToString(ob);
                            if (oa.ToString() == strOb)
                                return true;
                            else
                                return false;
                     }
                     catch
                    {
                           return false;
                    }
                }
               // object is datetime
               if (oa.GetType() == typeof(System.DateTime))
               {
                      try
                      {
                         DateTime dtOb = Convert.ToDateTime(ob);
                         if ((DateTime)oa == dtOb)
                            return true;
                         else
                            return false;

                      }
                      catch
                      {
                         return false;
                      }
               }
               //object is double
               if (oa.GetType() == typeof(System.Double))
               {
                    try
                    {
                         double ddOb = Convert.ToDouble(ob);
                         if ((double)oa == ddOb)
                            return true;
                         else
                             return false;

                     }
                    catch
                   {
                        return false;
                   }
              }

            return true;

        }

我知道我的比较方法太笨了，实际上，每个循环循环花费 2.4 秒，即：190000 循环花费 130 小时，看起来很糟糕，我听说它可以使用哈希表来加速搜索性能，但我不知道如何使用它。无论如何，对于 grid_A 中的每条记录，搜索 grid_B 中的所有记录是不可接受的，所以任何帮助都是不胜感激的。

我的网格数据是从 excel 导入的，所以它没有 sql 数据库或表。

4

3 回答 3

1

所以你想找出grid_B中是否有与grid_A中相同的记录。foreach您可以更改算法，而不是进行嵌套（导致 O(n^2) 复杂性，这是巨大的）。

如果您首先迭代grid_B并计算每行的哈希值（例如，通过将数据组合成字符串形式，然后获取哈希值，但可能有更好的方法来生成哈希值）。如果您将这些散列作为键放入字典中，则值可以引用行grid_B或其他需要的值。
然后你可以迭代grid_A，计算行的哈希值并在字典中检查键是否存在。如果它存在 - 您有相同的行grid_B（例如，存储在字典中的值可能会引导您到该行）。如果它不存在 - 没有具有相同值的行。

这种方法会给你 O(2n) 的复杂性，通常简化为 O(n) - 我们总是对数据进行两次迭代。这是显着的改进，但代价是更高的内存消耗。
这种方法是否更快可能取决于网格中的记录数量，但鉴于您有 190k 记录 - 这应该更快（虽然我现在无法测试，但会在晚上尝试这样做）。

于 2013-03-20T13:42:18.800 回答
0

处理原始数据而不是通过数据网格，这样你就不会有超网格的开销，它会加快速度。

另一个想法是从每一行创建一个字符串并比较这两个字符串。例如，如果该行是 1,'text', true, 1/1/2001 那么您必须创建包含字符串 '1-text-true-1/1/2001' 的有序列表，这样您将获得更快的索引.

于 2013-03-20T13:36:17.993 回答
0

如果您可以预先对两个网格进行排序，则可以大大减少比较次数。您将为每个网格（row_Afor grid_A，row_Bfor grid_B）维护一个当前行索引，并逐步浏览网格。对于每个比较（伪代码）：

if (grid_A[row_A] < grid_B[row_B])
    row_A++;

if (grid_A[row_A] == grid_B[row_B])
{
    //    matching record
    row_A++;
    row_B++;
}

if (grid_A[row_A] > grid_B[row_B])
    row_B++;

如果您无法对网格进行排序，那么我不知道有一种方法可以避免您当前的算法。您只需要尽可能优化各个行的比较。

于 2013-03-20T13:33:44.687 回答