0

grid_A と grid_B という名前の 190000 以上のレコードをそれぞれ含む 2 つのグリッドがあるとします。

grid_A のすべてのレコードについて、grid_B に同じレコードがあるかどうかを調べたい。

grid_A と grid_B には同じ列があります。私の場合、それらの列は

col1 col2 col3 col4

そしてそれらのデータ型は

文字列 datatime double

今では、私がしていることは次のとおりです。

grid_A の各行について、grid_B のすべての行をループし、4 つの列を比較します。

一つずつ。

コードは次のとおりです。

        //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) に単純化されます。データに対して常に 2 回の反復が行われます。これは大幅な改善ですが、メモリ消費量が増えます。
このようなアプローチが速いかどうかは、グリッド内のレコードの数に依存する可能性がありますが、190k のレコードがある場合は、より高速になるはずです (今はテストできませんが、夕方に試してみます)。

于 2013-03-20T13:42:18.800 に答える
0

データグリッドを介さずに生データを渡すと、ultraGridのオーバーヘッドがなくなり、処理速度が少し向上します。

もう1つのアイデアは、すべての行から文字列を作成し、これら2つの文字列を比較することです。たとえば、行が1、'text'、true、1/1/2001の場合、文字列'1-text-true-1/1/2001'を含むリストを作成して順序付けする必要があります。これにより、インデックス作成がはるかに高速になります。 。

于 2013-03-20T13:36:17.993 に答える
0

事前に両方のグリッドを並べ替えることができれば、比較の回数を大幅に減らすことができます。row_A各グリッド ( for 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 に答える