c# - DataTable 列计算的最有效排序计算

Question

假设您有一个包含“id”、“cost”、“qty”列的数据表:

DataTable dt = new DataTable();
dt.Columns.Add("id", typeof(int));
dt.Columns.Add("cost", typeof(double));
dt.Columns.Add("qty", typeof(int));

它以“id”为键:

dt.PrimaryKey = new DataColumn[1] { dt.Columns["id"] };

现在我们感兴趣的是单位数量的成本。所以，换句话说，如果你有一排:

id | cost  | qty
----------------
42 | 10.00 | 2

单位数量的成本为 5.00。

那么我的问题是，鉴于前面的表格，假设它由数千行构成，并且您对前 3 位每数量成本 行感兴趣。所需的信息是id、每数量成本。您不能使用 LINQ。

在 SQL 中这是微不足道的；在没有 LINQ 的情况下，您如何BEST(最有效地)在 C# 中完成它？

更新:求不修改表格的答案。

Answer 1

我不确定这是否最好，但它胜过排序然后选择时间复杂度为 O(n log n) 的前三个元素。

您可以使用优先级队列来过滤前三个元素。有关 .Net 优先级队列实现的信息可用 here .

基本思路是将你的数据表的前三个元素插入到优先级队列中。然后依次添加所有剩余元素，每次添加后删除顶部元素。之后留在优先级队列(堆)中的元素将是前三名元素。

无需修改表格，只需添加另一列(您只需定义相对排序/优先级标准)并且不会更改表格元素的顺序。时间复杂度为 O(n log 3) = O(n)。