Я пытаюсь использовать STL для решения следующей проблемы (я не хочу реализовывать свою собственную структуру данных, если мне это не нужно). Я придумал рабочую реализацию, но я надеюсь, что есть что-то быстрее ... или какой код у меня есть лучший способ сделать это?Сортировка std :: map с помощью другого ключа?
У меня есть большой набор данных, в котором каждая запись содержит два элемента: ключ и размер. В наборе данных есть несколько записей с одним и тем же ключом. Мне нужно знать: для каждого ключа, сколько из этих ключей находится в наборе данных, а для каждого ключа - общий размер их. Например, если этот набор данных (ключ, размер):
(1, 3)
(3, 27)
(7, 7)
(3, 2)
(1, 1)
Я хочу, чтобы сгенерировать этот вывод, отсортированный по размеру по возрастанию:
Key 1: Size 4, Count 2
Key 7: Size 7, Count 1
Key 3: Size 29, Count 2
Поскольку набор данных полностью несортированный, я первая потребность для объединения ключей для подсчета их и суммирования размера. Затем мне нужно применить эту структуру данных к общему размеру для получения конечного результата. Это код, который я придумал, чтобы выполнить задачу, используя зЬй :: Карты и зЬй :: вектора:
struct Node
{
int Size;
int Count;
Node()
: Size(0), Count(0)
{
}
Node(int size)
: Size(size), Count(1)
{
}
};
void map_insert(std::map<int, Node> &map, int key, int size)
{
std::map<int, Node>::iterator itr = map.find(key);
if (itr != map.end())
{
itr->second.Count++;
itr->second.Size += size;
}
else
{
map[key] = Node(size);
}
}
bool compare(const std::pair<int, Node> &a1, const std::pair<int, Node> &a2)
{
return a1.second.Size < a2.second.Size;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::map<int, Node> _map;
map_insert(_map, 1, 3);
map_insert(_map, 3, 27);
map_insert(_map, 7, 7);
map_insert(_map, 3, 2);
map_insert(_map, 1, 1);
std::vector<std::pair<int, Node>> v(_map.begin(), _map.end());
std::sort(v.begin(), v.end(), compare);
return 0;
}
Минус выходной код, это дает правильный вид. Я ненавижу использование двух отдельных структур данных, но, похоже, не существует способа «прибегнуть» к дереву на основе другого ключа. Существуют ли какие-то грубые неэффективности, которых я могу избежать? Может ли кто-нибудь подумать о лучшем способе сделать это?
Обратите внимание, что я предполагаю, что использование экземпляров Node (вместо указателей Node) будет быстрее, чем new'ing и delete'ing каждого узла, который используется здесь. Является ли это разумным предположением или вы считаете, что новое/удаление будет быстрее, чем копирование этих небольших структур?
Редактировать: Интересно, что я никогда не знала о мультимапе, но используя реализацию, представленную ниже (спасибо Naveen), похоже, что Multimap хуже работает. (Обратите внимание, мое намерение здесь была быстрая реализация, память не является проблемой, я бы указал на это.) С помощью этой реализации:
class Timer
{
public:
Timer()
: mStart(0)
{
}
void Start()
{
mStart = std::clock();
}
double Mark()
{
std::clock_t curr = std::clock();
double f = (curr - mStart)/((double)CLOCKS_PER_SEC);
mStart = curr;
return f;
}
private:
std::clock_t mStart;
};
struct Node
{
int Size;
int Count;
Node()
: Size(0), Count(0)
{
}
Node(int size)
: Size(size), Count(1)
{
}
};
void map_insert(std::map<int, Node> &map, int key, int size)
{
std::map<int, Node>::iterator itr = map.find(key);
if (itr != map.end())
{
itr->second.Count++;
itr->second.Size += size;
}
else
{
map[key] = Node(size);
}
}
bool compare(const std::pair<int, Node> &a1, const std::pair<int, Node> &a2)
{
return a1.second.Size < a2.second.Size;
}
int make_size(int i, int size_max)
{
return (7 * i) % size_max;
}
int make_key(int i, int key_max)
{
return (11 * i) % key_max;
}
void first_impl(int max, int size_max, int key_max)
{
std::cout << "first_impl:" << std::endl;
double total = 0;
double curr = 0;
Timer t;
t.Start();
{
std::map<int, Node> _map;
for (int i = 0; i < max; ++i)
map_insert(_map, make_key(i, key_max), make_size(i, size_max));
total += curr = t.Mark();
std::cout << "\tinsert: " << curr << std::endl;
std::vector<std::pair<int, Node>> v(_map.begin(), _map.end());
total += curr = t.Mark();
std::cout << "\tcreate: " << curr << std::endl;
std::sort(v.begin(), v.end(), compare);
total += curr = t.Mark();
std::cout << "\tsort: " << curr << std::endl;
}
total += curr = t.Mark();
std::cout << "\tcleanup: " << curr << std::endl;
std::cout << "\ttotal: " << total << std::endl;
}
void second_impl(int max, int size_max, int key_max)
{
std::cout << "second_impl:" << std::endl;
double total = 0;
double curr = 0;
Timer t;
t.Start();
{
std::map<int, Node> res;
typedef std::multimap<int, int> MultiMap;
MultiMap mMap;
for (int i = 0; i < max; ++i)
mMap.insert(std::make_pair(make_key(i, key_max), make_size(i, size_max)));
total += curr = t.Mark();
std::cout << "\tinsert: " << curr << std::endl;
std::multimap<int, int>::iterator iter = mMap.begin();
std::multimap<int, int>::iterator endIter = mMap.end();
for(; iter != endIter; ++iter)
{
int val = iter->first;
if(res.find(val) != res.end())
{
continue;
}
std::pair<MultiMap::iterator, MultiMap::iterator> iterPair = mMap.equal_range(val);
Node n;
n.Size = val;
n.Count = mMap.count(val);
int size = 0;
for(; iterPair.first != iterPair.second; ++iterPair.first)
{
size += iterPair.first->second;
}
res[size] = n;
}
total += curr = t.Mark();
std::cout << "\tsort: " << curr << std::endl;
}
total += curr = t.Mark();
std::cout << "\tcleanup: " << curr << std::endl;
std::cout << "\ttotal: " << total << std::endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
const int size_max = 31;
const int key_max = 1019;
const int max = 1000000;
first_impl(max, size_max, key_max);
second_impl(max, size_max, key_max);
return 0;
}
Результаты выглядеть примерно так:
first_impl:
insert: 0.094
create: 0
sort: 0
cleanup: 0
total: 0.094
second_impl:
insert: 1.653
sort: 46.894
cleanup: 66.081
total: 114.628
во второй реализация явно медленнее. Похоже, что общее количество ключей составляет far меньше, чем общее количество элементов (общее число уникальных ключей, составляющих около 1000, является представителем моего набора данных) делает std :: map победителем здесь, потому что он быстро достигает стабильное состояние, в котором не требуется больше узлов. I полностью пропустил этот факт, прежде чем я сделал это вторичное расследование.
Похоже, что моя первоначальная реализация лучше мультимапа, и поскольку я не хочу зависеть от Boost, я думаю, что у меня есть мой ответ. Спасибо всем!
На втором взгляде на код, который использует multimap, я не совсем уверен, что эта реализация верна, однако тот факт, что требуется больше времени вставлять в multimap, чем для полного расчета того, что я ищу с помощью карты/vector/sort, это все еще кажется ясным, что первоначальная реализация - это та, с которой я иду. – LCC
Для большей скорости вы можете посмотреть hash_map (или tr1: unordered_map). – Joel
Да, итерации очень медленные, поэтому MultiMap вышел, и это технически некорректно, так как вам не нужно держать размер и подсчет, просто подведите итог, как вы правильно сделали. Хэш-таблица неупорядоченной карты STL примерно в 3 раза быстрее, чем карта, но для вашего скромного размера данных не стоит хлопот. Интригующей идеей было бы использовать 1 карту для суммирования данных и вторую карту для ее сортировки - не то, что qsort() работает не очень хорошо, как только вы суммируете данные, но вторая карта предоставит отсортированное резюме в в режиме реального времени. – user2548100