В настоящее время я экспериментирую с использованием stl-datastructures.Однако я все еще не уверен, когда использовать какую и когда использовать определенную комбинацию.В настоящее время я пытаюсь понять, когда использование std::multimap имеет смысл.Насколько я вижу, можно легко создать собственную реализацию нескольких карт, комбинируя std::map и std::vector.Поэтому у меня остается вопрос, когда следует использовать каждую из этих структур данных.
- Простота: std :: multimap определенно проще в использовании, поскольку не нужно обрабатывать дополнительное вложение.Однако при доступе к целому ряду элементов может потребоваться скопировать данные из итераторов в другую структуру данных (например,
std::vector). - Скорость: локальность вектора, скорее всего, делает итерации подиапазон равных элементов намного быстрее, потому что использование кэша оптимизировано.Однако я предполагаю, что у
std::multimaps также есть много приемов оптимизации за спиной, чтобы сделать перебор одинаковых элементов максимально быстрым.Кроме того, получение правильного диапазона элементов может быть оптимизировано для std::multimaps.
Чтобы проверить проблемы со скоростью, я провел несколько простых сравнений, используя следующую программу:
#include <stdint.h>
#include <iostream>
#include <map>
#include <vector>
#include <utility>
typedef std::map<uint32_t, std::vector<uint64_t> > my_mumap_t;
const uint32_t num_partitions = 100000;
const size_t num_elements = 500000;
int main() {
srand( 1337 );
std::vector<std::pair<uint32_t,uint64_t>> values;
for( size_t i = 0; i <= num_elements; ++i ) {
uint32_t key = rand() % num_partitions;
uint64_t value = rand();
values.push_back( std::make_pair( key, value ) );
}
clock_t start;
clock_t stop;
{
start = clock();
std::multimap< uint32_t, uint64_t > mumap;
for( auto iter = values.begin(); iter != values.end(); ++iter ) {
mumap.insert( *iter );
}
stop = clock();
std::cout << "Filling std::multimap: " << stop - start << " ticks" << std::endl;
std::vector<uint64_t> sums;
start = clock();
for( uint32_t i = 0; i <= num_partitions; ++i ) {
uint64_t sum = 0;
auto range = mumap.equal_range( i );
for( auto iter = range.first; iter != range.second; ++iter ) {
sum += iter->second;
}
sums.push_back( sum );
}
stop = clock();
std::cout << "Reading std::multimap: " << stop - start << " ticks" << std::endl;
}
{
start = clock();
my_mumap_t mumap;
for( auto iter = values.begin(); iter != values.end(); ++iter ) {
mumap[ iter->first ].push_back( iter->second );
}
stop = clock();
std::cout << "Filling my_mumap_t: " << stop - start << " ticks" << std::endl;
std::vector<uint64_t> sums;
start = clock();
for( uint32_t i = 0; i <= num_partitions; ++i ) {
uint64_t sum = 0;
auto range = std::make_pair( mumap[i].begin(), mumap[i].end() );
for( auto iter = range.first; iter != range.second; ++iter ) {
sum += *iter;
}
sums.push_back( sum );
}
stop = clock();
std::cout << "Reading my_mumap_t: " << stop - start << " ticks" << std::endl;
}
}
Как я и подозревал, это зависит главным образом от соотношения между num_partitions и num_elements, поэтому я все еще здесь в растерянности.Вот несколько примеров выходных данных:
Для num_partitions = 100000 и num_elements = 1000000
Filling std::multimap: 1440000 ticks
Reading std::multimap: 230000 ticks
Filling my_mumap_t: 1500000 ticks
Reading my_mumap_t: 170000 ticks
Для num_partitions = 100000 и num_elements = 500000
Filling std::multimap: 580000 ticks
Reading std::multimap: 150000 ticks
Filling my_mumap_t: 770000 ticks
Reading my_mumap_t: 140000 ticks
Для num_partitions = 100000и num_elements = 200000
Filling std::multimap: 180000 ticks
Reading std::multimap: 90000 ticks
Filling my_mumap_t: 290000 ticks
Reading my_mumap_t: 130000 ticks
Для num_partitions = 1000 и num_elements = 1000000
Filling std::multimap: 970000 ticks
Reading std::multimap: 150000 ticks
Filling my_mumap_t: 710000 ticks
Reading my_mumap_t: 10000 ticks
Я не уверен в том, как интерпретировать эти результаты.Как бы вы решили выбрать правильную структуру данных?Есть ли какие-то дополнительные ограничения для принятия решения, которые я мог бы пропустить?