0

私は、データベースにクエリを実行してデータを1つのデータテーブルにプルし、Excelファイルを開いて別のデータテーブルにデータを入力する、アプリケーションのいくつかの機能に取り組んでいます。

Excelファイルに使用可能なIDが含まれていないため、データを並べ替えることができず、おそらく使用できませんDataTable.Merge()。

これが私が作成したマッチングアルゴリズムのコードです。

 private void RunMatchingAlgorithm()
    {
        // Initialize variables
        string partNumber = "";
        DateTime expiration_date = DateTime.Now;
        decimal contract_cost = 0;
        string contract_no = "";

        string partNumber2 = "";
        DateTime expiration_date2 = DateTime.Now;
        decimal contract_cost2 = 0;
        string contract_no2 = "";

        //Get values from DataBase
        for (int i = 0; i < dtFromTableContracts.Rows.Count; i++)
        {
            partNumber2 = dtFromTableContracts.Rows[i]["supplier_part_no"].ToString();
            contract_no2 = dtFromTableContracts.Rows[i]["contract_no"].
            expiration_date2 = Convert.ToDateTime(dtFromTableContracts.Rows[i]["con_end_date"]).Date;

            //Get Values from converted Excel table
            for (int j = 0; j < dtConversion.Rows.Count; j++)
            {
                contract_no = dtConversion.Rows[j]["vend_contract_no"].ToString();

                //If we have even a partial match, check for a part number match
                if (contract_no2.StartsWith(contract_no))
                {
                    partNumber = dtConversion.Rows[j]["vend_item_id"].ToString();

                    //If the values match, populate from both tables
                    if (partNumber == partNumber2)
                    {
                        dtConversion.Rows[j]["wpd_expiration_date"] = expiration_date2.Date;
                        dtConversion.Rows[j]["wpd_cont_cost"] = dtFromTableContracts.Rows[i]["contract_cost"];
                        dtConversion.Rows[j]["wpd_contract_no"] = dtFromTableContracts.Rows[i]["contract_no"];
                        dtConversion.Rows[j]["wpd_item_id"] = dtFromTableContracts.Rows[i]["supplier_part_no"];
                        dtConversion.Rows[j]["wpd_item_no"] = dtFromTableContracts.Rows[i]["item_id"];
                        dtConversion.Rows[j]["discontinued"] = dtFromTableContracts.Rows[i]["discontinued"];
                        dtConversion.Rows[j]["job_no"] = dtFromTableContracts.Rows[i]["job_no"];
                    }
                }
            }
        }
    }

興味がある場合は、後のメソッドで一致しない行を削除し、一致したレコードのみをDGVに表示します。

これは現在期待どおりに機能しますが、Big O表記が正しければ、O（m * n）を処理しています。これは、データセットが大きくなると非常に遅くなり、プロセッサに非常に負荷がかかります。

使用しているExcelスプレッドシートの一部は40,000行に近いため、すべての行をループするよりも効率的な方法を探しています。このアルゴリズムは、そのサイズのセットで完了するのに約6分かかります。

4

5 に答える 5

3

おやおや、単純化の機会がたくさんあるコード。ローカル変数のスコープを縮小して、未使用の値を割り当てる誘惑を取り除くことができます。コレクションへのアクセス以外にインデックスを使用しない場合は、ForループをForEachループに変換することもできます。

初期の簡略化：

private void RunMatchingAlgorithm() {
    foreach (var databaseRow in dtFromTableContracts.Rows) {
        string partNumber2 = databaseRow["supplier_part_no"].ToString();
        string contract_no2 = databaseRow["contract_no"].ToString();
        DateTime expiration_date2 = Convert.ToDateTime(databaseRow["con_end_date"]).Date;

        foreach (var excelRow in dtConversion.Rows) {
            string contract_no = excelRow["vend_contract_no"].ToString();

            //If we have even a partial match, check for a part number match
            if (contract_no2.StartsWith(contract_no)) {
                string partNumber = excelRow["vend_item_id"].ToString();

                //If the values match, populate from both tables
                if (partNumber == partNumber2) {
                    excelRow["wpd_expiration_date"] = expiration_date2.Date;
                    excelRow["wpd_cont_cost"] = databaseRow["contract_cost"];
                    excelRow["wpd_contract_no"] = databaseRow["contract_no"];
                    excelRow["wpd_item_id"] = databaseRow["supplier_part_no"];
                    excelRow["wpd_item_no"] = databaseRow["item_id"];
                    excelRow["discontinued"] = databaseRow["discontinued"];
                    excelRow["job_no"] = databaseRow["job_no"];
                }
            }
        }
    }
}

考えてみると、これはlinqクエリが設計されたケースとほぼ同じです。ほとんどのコードをクエリに変換できます。

private void RunMatchingAlgorithm() {
    var matches = from databaseRow in dtFromTableContracts.Rows
                  let partNumber2 = databaseRow["supplier_part_no"].ToString()
                  let contract_no2 = databaseRow["contract_no"].ToString()
                  let expiration_date2 = Convert.ToDateTime(databaseRow["con_end_date"]).Date
                  from excelRow in dtConversion.Rows
                  let contract_no = excelRow["vend_contract_no"].ToString()
                  where contract_no2.StartsWith(contract_no)
                  let partNumber = excelRow["vend_item_id"].ToString()
                  where partNumber == partNumber2
                  select new { databaseRow, excelRow, expiration_date2 }
    foreach (var m in matches) {
        var dst = m.excelRow;
        var src = m.databaseRow;

        dst["wpd_expiration_date"] = m.expiration_date2.Date;
        dst["wpd_cont_cost"] = src["contract_cost"];
        dst["wpd_contract_no"] = src["contract_no"];
        dst["wpd_item_id"] = src["supplier_part_no"];
        dst["wpd_item_no"] = src["item_id"];
        dst["discontinued"] = src["discontinued"];
        dst["job_no"] = src["job_no"];
    }
}

そして今、最適化を適用できる場所がわかりました。ネストされた'from'と'where'を実行しています。これは、クロス結合と同等です。また、現在のみ使用されている一時的なもののほとんどを削減できます。

private void RunMatchingAlgorithm() {
    var matches = from databaseRow in dtFromTableContracts.Rows
                  join excelRow in dtConversion.Rows
                  on excelRow["vend_item_id"].ToString() equals databaseRow["supplier_part_no"].ToString()
                  where databaseRow["contract_no"].ToString().StartsWith(excelRow["vend_contract_no"].ToString())
                  select new { databaseRow, excelRow }
    foreach (var m in matches) {
        var dst = m.excelRow;
        var src = m.databaseRow;

        dst["wpd_expiration_date"] = Convert.ToDateTime(src["con_end_date"]).Date;
        dst["wpd_cont_cost"] = src["contract_cost"];
        dst["wpd_contract_no"] = src["contract_no"];
        dst["wpd_item_id"] = src["supplier_part_no"];
        dst["wpd_item_no"] = src["item_id"];
        dst["discontinued"] = src["discontinued"];
        dst["job_no"] = src["job_no"];
    }
}

私は実際にはクロス結合をあまり使用していませんが、内部でハッシュテーブルを使用して、O（n * m）ではなくO（n + m）の複雑さを持っていると思います。両方のテーブルがデータベースにある場合、データベースはすでに構築されたハッシュテーブル/インデックスを利用できます。

また、生成されたLinq2SQLクラスの種類を検討して、行フィールドにタイプセーフにアクセスできるようにすることもできます。

于 2013-03-04T19:37:29.117 に答える
0

Trieは、部分文字列を見つけるための最速の構造です。

于 2013-03-04T19:35:37.980 に答える
0

ContractTable.ContractNoが既知の一定の長さである場合、次の2つのテーブル間に（事実上）PK-FK関係があります。

ContractTable.ContractNo = substring(Conversion.VendContractNo,1,K)
ContractTable.PartNumber = Conversion.PartNumber

ここで、K == Length（ContractTabel.ContractNo）です。

このキー構造で両方のテーブルにインデックスを付けると、O（Log N）+ O（Log M）時間で一致を作成でき、インデックスの作成にはO（N * Log N）+ O（M * Log M）時間がかかります。優れたハッシュの構築によっては、ハッシュによってこれをさらに改善できる可能性があります。

于 2013-03-04T19:36:23.310 に答える
0

一致させたい値をハッシュし、O(m+n) の複雑さを持たせることができます。

両側を解析し、ハッシュできる均一な結果のペア (またはセット) を作成する関数を作成する必要があります。たとえば、contract_no一方に既知の形式のプレフィックスがあり、もう一方にプレフィックスがない場合、プレフィックスを削除してそれをハッシュできます。

于 2013-03-04T19:24:48.397 に答える
0

一致する部品番号を見つけた後、内側のループを終了することで、時間を約半分に短縮できるはずです。つまりbreak、部品番号が一致したときに実行されるコードの最後のステートメントとして a を配置します。

それでも、永遠の半分は永遠です。

わずか 40,000 行で、契約番号と部品番号をキーとして、変換テーブルの行インデックスを値として含むディクショナリを簡単に作成できます。何かのようなもの：

Dictionary<string, int> conversionLookup = new Dictionary<string, int>();
for (int i = 0; i < dtConversion.Rows.Count; ++j)
{
    conversionLookup.Add(string.Format("{0}:{1}", 
        dtConversion.Rows[j]["vend_contract_no"].ToString(),
        dtConversion.Rows[j]["vend_item_id"].ToString()), j);
}

次に、外側のループは次のようになります。

for (int i = 0; i < dtFromTableContracts.Rows.Count; i++)
{
    partNumber2 = dtFromTableContracts.Rows[i]["supplier_part_no"].ToString();
    contract_no2 = dtFromTableContracts.Rows[i]["contract_no"].ToString();
    string lookup = string.Format("{0}:{1}", contract_no2, partNumber2);
    int ix;
    if (conversionLookup(lookup, out ix))
    {
        // update dtConversion.Rows[ix]
    }
}

私はあなたの部品番号の制限に慣れていないので (StartsWith内側のループでは equals ではなく使用しています)、インデックスを多少調整する必要があるかもしれません。

それは非常に速いはずです。

直接検索に契約番号を使用するキーを作成できない場合はList、契約番号と部品番号を使用して を作成し、それをバイナリ検索することで、非常に類似したことを行うことができます。これは、O(m * n) ではなく O(m log n) になります。それでもかなり速い。

于 2013-03-04T19:25:51.660 に答える