В настоящее время я экспериментирую с некоторым использованием stl-datastructures. Однако я до сих пор не уверен, когда использовать какой и когда использовать определенную комбинацию. В настоящее время я пытаюсь выяснить, когда использование std::multimap имеет смысл. Насколько я вижу, можно легко создать собственную реализацию мультимапа, объединив std::map и std::vector. Поэтому я оставляю вопрос, когда нужно использовать каждую из этих структур данных.
- Простота: std:: multimap определенно проще использовать, потому что не нужно обрабатывать дополнительное вложение. Однако доступ к целому ряду элементов в качестве объемного может потребоваться скопировать данные из итераторов в другую структуру данных (например, a
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
Я не уверен, как интерпретировать эти результаты. Как бы вы определили правильную структуру данных? Существуют ли какие-либо дополнительные ограничения для деления, которые я, возможно, пропустил?
