c# - 两个(未排序的)数据表之间匹配的优化算法？

Question

我正在开发我的应用程序中的一些功能，这些功能查询我们的数据库并将数据提取到一个数据表，然后打开一个 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 分钟才能完成该大小的集合。

Answer 1

天哪，代码有很多简化的机会。您可以缩小局部变量的范围，消除为它们分配未使用的值的任何诱惑。当您不使用索引(访问集合除外)时，您还可以将 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 类，这样您就可以对行字段进行类型安全访问。