0

我正在我的应用程序中开发一些功能，查询我们的数据库并将数据拉到一个数据表中，然后打开一个 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 中显示匹配的记录。

这目前按预期工作，但如果我的大 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"];
    }
}

现在我看到了可以在哪里应用优化。我们正在使用“where”进行嵌套的“from”，这相当于交叉连接。此外，我们可以删除大部分现在只使用一次的临时文件：

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

您可以散列要匹配的值并具有 O(m+n) 复杂度。

您必须创建一个函数来解析双方并创建一对（或一组）统一结果，然后可以对其进行散列。例如，如果您contract_no的一侧有一些已知格式的前缀，而另一侧没有前缀，您可以删除前缀并对其进行哈希处理。

于 2013-03-04T19:24:48.397 回答
0

在找到匹配的零件号后，您应该能够通过退出内部循环将时间减少大约一半。也就是说，将 abreak作为零件编号匹配时执行的代码中的最后一条语句。

尽管如此，永远的一半仍然是永远。

只需 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 log n) 而不是 O(m * n)。还是快了不少。

于 2013-03-04T19:25:51.660 回答
0

Trie将是查找子字符串的最快结构。

于 2013-03-04T19:35:37.980 回答
0

如果 ContractTable.ContractNo 具有已知的恒定长度，那么您（事实上）在以下两个表之间具有 PK-FK 关系：

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

其中 K == 长度（ContractTabel.ContractNo）。

在这个键结构上索引两个表将允许在 O(Log N) + O(Log M) 时间内进行匹配，索引创建需要 O(N * Log N) + O(M * Log M) 时间。散列可以进一步改善这一点，这取决于一个好的散列的构造。

于 2013-03-04T19:36:23.310 回答