как получить среднее значение из отсортированной карты
Я использую станд.:: карта. Иногда я буду делать операцию как: нахождение среднего значения всех объектов. например, если я добавляю
1 "s"
2 "sdf"
3 "sdfb"
4 "njw"
5 "loo"
затем медиана равняется 3.
Есть ли некоторое решение, не выполняя итерации более чем половины объектов в карте?
10 ответов
Я думаю, вы можете решить проблему, используя два std :: map . Один для меньшей половины элементов (mapL), а второй для другой половины (mapU). Когда у вас есть операция вставки. Это будет любой случай:
- добавить элемент в mapU и переместить наименьший элемент в mapL
- добавить элемент в mapL и переместить самый большой элемент в mapU
Если карты имеют другой размер и вы вставляете элемент в карту с меньшее количество элементы, которые вы пропускаете в разделе перемещения. Основная идея состоит в том, чтобы ваши карты были сбалансированы так, чтобы максимальная разница в размере составляла 1 элемент. Насколько я знаю STL, все операции должны работать за время O (ln (n)). Доступ к наименьшему и наибольшему элементу на карте можно выполнить с помощью итератора. Когда у вас есть запрос n_th позиции, просто проверьте размеры карты и верните наибольший элемент в mapL или наименьший элемент в mapR.
Вышеупомянутый сценарий использования предназначен только для вставки, но вы можете расширить его и до удаления элементов, но вам нужно отслеживать, какая карта содержит элемент, или пытаться удалить из обоих.
Вот мой код с примером использования:
#include <iostream>
#include <string>
#include <map>
using namespace std;
typedef pair<int,string> pis;
typedef map<int,string>::iterator itis;
map<int,string>Left;
map<int,string>Right;
itis get_last(map<int,string> &m){
return (--m.end());
}
int add_element(int key, string val){
if (Left.empty()){
Left.insert(make_pair(key,val));
return 1;
}
pis maxl = *get_last(Left);
if (key <= maxl.first){
Left.insert(make_pair(key,val));
if (Left.size() > Right.size() + 1){
itis to_rem = get_last(Left);
pis cpy = *to_rem;
Left.erase(to_rem);
Right.insert(cpy);
}
return 1;
} else {
Right.insert(make_pair(key,val));
if (Right.size() > Left.size()){
itis to_rem = Right.begin();
pis cpy = *to_rem;
Right.erase(to_rem);
Left.insert(*to_rem);
}
return 2;
}
}
pis get_mid(){
int size = Left.size() + Right.size();
if (Left.size() >= size / 2){
return *(get_last(Left));
}
return *(Right.begin());
}
int main(){
Left.clear();
Right.clear();
int key;
string val;
while (!cin.eof()){
cin >> key >> val;
add_element(key,val);
pis mid = get_mid();
cout << "mid " << mid.first << " " << mid.second << endl;
}
}
Я думаю, что ответ отрицательный. Вы не можете просто перейти к элементу N / 2 после начала, потому что std::map использует двунаправленные итераторы. Вы должны выполнить итерацию через половину элементов в карте. Если бы у вас был доступ к реализации базового дерева Red/Black, которое обычно используется для std::map, вы могли бы приблизиться к этому, как в ответе Дани. Однако у вас нет доступа к этому, поскольку это инкапсулировано как деталь реализации.
В самобалансирующемся двоичном дереве (я думаю, что это std :: map) хорошим приближением будет корень.
Для точного значения просто кешируйте его с индикатором баланса, и каждый раз, когда элемент добавляется ниже медианы, уменьшайте индикатор и увеличивайте, когда элемент добавляется выше. Когда индикатор равен 2 / -2, переместите медианное значение на один шаг вверх / вниз и сбросьте индикатор.
Попробуйте:
typedef std::map<int,std::string> Data;
Data data;
Data::iterator median = std::advance(data.begin(), data.size() / 2);
Работает, если размер () нечетный. Я позволю вам разобраться, как это сделать, когда size () четный.
Если вы можете переключать структуры данных, сохраните элементы в std :: vector и отсортируйте его. Это позволит получить доступ к среднему элементу позиционно без повторения. (Это может быть удивительно, но отсортированный вектор часто превосходит карту из-за местоположения. Для поиска по ключу сортировки вы можете использовать двоичный поиск, и он будет иметь примерно то же самое производительность как карта в любом случае. См. Скотт Мейер Эффективный STL .)
Если вы знаете, что карта будет отсортирована, получите элемент на уровне пола (длина / 2). Если у вас немного приподнятое настроение, попробуйте (длина >> 1).
Я не знаю способа быстро получить медианное значение из чистой карты STL для больших карт. Если ваша карта мала или вам редко нужна медиана, вы все равно должны использовать линейное продвижение до n / 2 - для простоты и стандартизации.
Вы можете использовать карту для создания нового контейнера, который предлагает медианное значение: Джетро предложил использовать две карты, исходя из этого, возможно, лучше было бы одну карту и постоянно обновляемый медианный итератор. У этих методов есть недостаток, заключающийся в том, что вам приходится заново реализовывать каждую операцию модификации, а в случае jethro даже операции чтения.
Контейнер, написанный на заказ, также будет делать то, что вы, вероятно, наиболее эффективно, но за счет специального кода. Вы можете попробовать, как было предложено, изменить существующую реализацию stl-карты. Вы также можете поискать существующие реализации.
Существует сверхэффективная реализация C, которая предлагает большую часть функциональных возможностей отображения, а также произвольный доступ, под названием Judy Arrays . Они работают для ключей целочисленных, строковых и байтовых массивов.
Для списка сортировок, вот он в коде java, но я предполагаю, что его очень легко перенести на c++:
if (input.length % 2 != 0) {
return input[((input.length + 1) / 2 - 1)];
} else {
return 0.5d * (input[(input.length / 2 - 1)] + input[(input.length / 2 + 1) - 1]);
}
Для этого вам нужен метод nth_element () :) Он реализует разделение части быстрой сортировки, и вам не нужно, чтобы ваш вектор (или массив) сортировался. А также временная сложность O (n) (а за сортировку нужно платить O (nlogn)).
Похоже, что вставка и поиск - две общие операции, а медиана - редкость. Самый простой подход - использовать карту и std :: advance (m.begin (), m.size () / 2 ); как первоначально предложил Дэвид Родригес. Это линейное время, но его легко понять, поэтому я бы рассмотрел другой подход только в том случае, если профилирование показывает, что медианные вызовы слишком дороги по сравнению с работой, которую выполняет ваше приложение.