Блог

Главная - Вопросы по программированию - Верхние и нижние 5% элементов из потока данных

Верхние и нижние 5% элементов из потока данных

#algorithm #data-structures

#алгоритм #структуры данных

Вопрос:

Учитывая поток цифрового ввода, требуется среднее значение последнего последнего значения k, и при вычислении требуется удалить верхние 5% и нижние 5% из k чисел.

Можем ли мы сделать это за линейное время. Решением O (n log k) было бы использование очередей с приоритетом, но я не могу придумать более оптимального решения.

Комментарии:

1. Поскольку вы должны сохранить отсортированную версию всего входного потока, чтобы отслеживать верхние и нижние 5%, вы как бы застряли с решением O (n log n) (т. Е. Вставкой журнала (n) в отсортированную структуру ввода).).

2. вы хотите вычислить n средние числа за меньшее O(n log k) время?

3. @Yola Я думаю, вам нужно сохранить все n значения, поскольку вам нужно запомнить их, чтобы узнать новый рейтинг для каждого нового входного значения. например, вы всегда должны помнить самое первое значение, потому что оно может входить и выходить из верхних / нижних 5% в любой момент в будущем.

4. @wcochran вам нужно запомнить 5% только для, k не для n , я думаю.

5. @Yola Я думаю, вы правы … поскольку вся статистика относится к последним k числам, мы можем забыть о тех, которые были до этого. Итак, вы хотите удалить самое старое число и добавить самое новое число, чтобы сохранить k значения.

Ответ №1:

Вот O(n log(k)) подход. Я использовал deque для хранения последних k значений в порядке ввода и упорядоченный набор для сохранения отсортированной версии последних k значений:

 deque<T> d;
set<T> s;   // e.g., red-black tree
for each new value x {
     d.push_back(x);
     s.insert(x);
     if (d.size() > k) {
         old = d.front(); d.pop_front();
         s.erase(old);
         // s holds sorted k-values
         // traverse to find mean
         // traverse in order, pass over the first and last 0.05*k values
     }
}