Наиболее эффективная сортировка расчетов при вычислении столбцов DataTable

Question

Допустим, у вас есть DataTable, в котором есть столбцы «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 это было бы тривиально; как BEST (наиболее эффективно) вы бы достигли этого в C # без LINQ?

Обновление: Поиск ответов, которые не изменяют таблицу.

Answer 1

Добавить столбец:

dt.Columns["CostPerQty"].Expression = "cost / qty";

Затем сортировать:

dt.DefaultView.Sort = "CostPerQty desc";

Просто получите 3 верхних ряда.

Answer 2

Я не уверен, что это лучше, но это лучше, чем сортировка и выбор трех верхних элементов, которые имеют временную сложность O (n log n).

Вы можете использовать приоритетную очередь для фильтрации трех верхних элементов. Информация о реализации приоритетных очередей .Net доступна здесь .

Основная идея - вставить первые три элемента вашей таблицы данных в очередь с приоритетами. Затем вы последовательно добавляете все оставшиеся элементы, удаляя верхний элемент после каждого добавления. Элементы, оставшиеся в приоритетной очереди (куче) после этого, будут тремя верхними элементами.

Никаких изменений в таблице не требуется, с точки зрения добавления еще одного столбца (вам просто нужно определить критерии относительного порядка / приоритета), и это не меняет порядок элементов таблицы. Временная сложность будет O (n log 3) = O (n).

Answer 3

Мне нравится решение BFree, но, если по какой-то причине вам не нужен дополнительный столбец в наборе данных, есть ли причина, по которой вы не можете инициировать вызов вашей БД и выполнить хранимую процедуру для результатов?

В качестве альтернативы, не используйте DataTable, а анализируйте объекты из результатов ADO.NET и создавайте IEnumerable<T> (или Список, или массив, или что-то еще) из этих объектов. Тогда просто отсортировать их? Я предпочитаю объектное решение (даже без использования Entities, Linq2SQL и т. Д.) Только потому, что оно дает мне гораздо большую гибкость в отношении того, что я могу сделать со строкой, когда она у меня будет ...