Рассчитать медианные продажи для каждого клиента в массиве клиентов (неофит)

Question

У меня есть массив объектов клиента, сгенерированный из файла CSV:

Дата, Имя, Продажи
03/01, альфа, 110
23.03, Альфа, 25
01/02, бета, 135
...
и требовать эффективного способа создать новый массив уникальных клиентов со средними продажами и экспортировать их обратно в CSV Может быть до 500 000 записей и 100 000 уникальных клиентов!

Answer 1

- Разделите ваши исходные данные на коллекции для каждого клиента.

Для каждого клиента:

- Сортировка по продажам

- если количество записей нечетное, вернуть продажи по среднему индексу

- если число записей четное, вернуть среднее значение записей по обе стороны от середины

- Вставить возвращенную запись в массив результатов.

Answer 2

В подобных случаях я бы использовал:

Dictionary<string, List<int>> dict; 

Ключами являются имена клиентов (если они уникальны, в противном случае присваивают уникальный идентификатор какого-либо рода?) Значения представляют собой списки продаж для каждогопокупатель.После заполнения этого массива вы можете продолжить либо сортировку и получение среднего элемента (как упомянуто выше) , либо суммирование и деление на количество элементов для получения медианы. (это неправильно)

Сортировка (с использованием метода, который сравнивает) занимает время O (nlog n), где n - длина списка, который нужно отсортировать.

Существуют алгоритмы выбора, которые могут вернуть k-е наименьшее значение в O (n), проверьте ссылку в Википедии ниже