Как получить медианное значение из отсортированной карты

Я использую std:: map. Иногда я буду выполнять операцию, например: поиск медианного значения всех элементов. например если я добавлю

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;
 }
}
</int,string></int,string></int,string></int,string></int,string></map></string></iostream>


Я думаю, что ответ отрицательный. Вы не можете просто перейти к элементу N/2 за начало, потому что std::map использует двунаправленные итераторы. Вы должны перебрать половину элементов на карте. Если у вас был доступ к базовой реализации Red/Black tree, которая обычно используется для std::map, вы можете приблизиться, как в ответы Дани. Однако у вас нет доступа к этому, поскольку он инкапсулирован как деталь реализации.


Try:

typedef std::map<int,std::string> Data;
Data data;
Data::iterator median = std::advance(data.begin(), data.size() / 2); 
</int,std::string>

Работает, если размер() нечетный. Я дам вам понять, как это сделать, когда размер() равен.


В самобалансирующемся бинарном дереве (std:: map - это я считаю) хорошим приближением будет корень. Для точного значения просто кешируйте его индикатором баланса, и каждый раз, когда элемент, добавленный ниже медианного, уменьшает индикатор и увеличивается, когда элемент добавляется выше. Когда индикатор равен 2/-2, перемещайте медиану вверх/вниз на один шаг и reset индикатор.


Если вы можете переключить структуры данных, сохраните элементы в std::vector и отсортируйте их. Это позволит осуществлять доступ к среднему элементу позиционно без повторения. (Это может быть удивительно, но отсортированный vector часто выходит из map из-за локальности. Для поиска с помощью ключа сортировки вы можете использовать двоичный поиск, и в любом случае он будет иметь такую ​​же производительность, что и map. См. Scott Meyer Эффективный STL.)


Если вы знаете, что карта будет сортироваться, то получите элемент на этаже (длина/2). Если вы немного настроены, попробуйте (длина → 1).


Так как это звучит как вставка и найти ваши две общие операции, в то время как медианная редка, самый простой подход - использовать карту и std::advance( m.begin(), m.size()/2 );, как первоначально было предложено Дэвидом Родригесом. Это линейное время, но это легко понять, поэтому я рассматриваю только другой подход, если профилирование показывает, что медианные вызовы слишком дороги относительно работы, выполняемой вашим приложением.


Я не знаю, как быстро получить медиану с чистой карты STL для больших карт. Если ваша карта мала или вам нужна медиана редко, вы должны использовать линейное продвижение к n/2, как мне кажется, ради простоты и стандартности.

Вы можете использовать карту для создания нового контейнера, предлагающего медиану: Jethro предложил использовать две карты, на основе которых, возможно, лучше было бы одна карта и постоянно обновляемый медиатор итератора. Эти методы страдают от недостатка, который вы должны выполнить для каждой операции модификации и в jethro случае даже операций чтения.

Пользовательский письменный контейнер также будет делать то, что вы, возможно, наиболее эффективно, но за цену настраиваемого кода. Вы можете попробовать, так как было предложено изменить существующую реализацию stl-карты. Вы также можете искать существующие реализации.

Существует суперэффективная реализация C, которая предлагает большинство функций карты, а также произвольный доступ, называемый Judy Arrays. Они работают для целых, строковых и байтовых ключей массива.


Для этого существует метод nth_element() для него:) Он реализует часть раздела быстрой сортировки, и вам не нужен ваш вектор (или массив) для сортировки. А также временная сложность O (n) (в то время как для сортировки вам нужно заплатить O (nlogn)).


Для списка сортировки здесь он находится в java-коде, но я предполагаю, что его очень легко переносить на С++:

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]);
 }

licensed under cc by-sa 3.0 with attribution.