c++ - example - ¿Cuándo tiene sentido usar un std:: multimap?

multimap c++

Question

Actualmente estoy experimentando con el uso de stl-datastructures. Sin embargo, todavía no estoy seguro de cuándo usar cuál y cuándo usar una determinada combinación. Actualmente estoy tratando de averiguarlo, cuando se usa std::multimap tiene sentido. Por lo que puedo ver, uno puede construir fácilmente su propia implementación multimap combinando std::map y std::vector . Por lo tanto, me queda la pregunta de cuándo se debe usar cada una de estas estructuras de datos.

• Simplicidad: Un std :: multimap es definitivamente más fácil de usar, porque uno no tiene que manejar el anidamiento adicional. Sin embargo, el acceso a un rango de elementos como uno masivo podría necesitar copiar los datos de los iteradores a otra estructura de datos (por ejemplo, un std::vector ).
• Velocidad: la ubicación del vector probablemente hace que la iteración sobre el rango de elementos iguales sea mucho más rápida, porque el uso de la memoria caché está optimizado. Sin embargo, supongo que std::multimaps también tiene una gran cantidad de trucos de optimización detrás de la parte posterior para hacer iterar sobre elementos iguales lo más rápido posible. También llegar al correcto rango de elementos probablemente sea optimizado para std::multimaps .

Para probar los problemas de velocidad hice algunas comparaciones simples usando el siguiente programa:

#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;
  }
}

Como sospechaba, depende principalmente de la relación entre num_partitions y num_elements , así que todavía estoy perdido aquí. Aquí hay algunos ejemplos de resultados:

Para num_partitions = 100000 y 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

Para num_partitions = 100000 y 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

Para num_partitions = 100000 y 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

Para num_partitions = 1000 y 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

No estoy seguro de cómo interpretar estos resultados. ¿Cómo tomarías la decisión de la estructura de datos correcta? ¿Hay alguna restricción adicional para la decisión, que podría haber pasado por alto?

Answer 1

Has olvidado una alternativa muy importante: no todas las secuencias se crean iguales.

Especialmente, ¿por qué un vector y no un deque o una list ?

Usando la list

Un std::map<int, std::list<int> > debería funcionar aproximadamente de forma equivalente a un std::multimap<int, int> ya que la list se basa en nodos.

Usando deque

Un deque es el contenedor predeterminado para usar cuando no se sabe a qué ir y no tiene ningún requisito especial.

Con respecto al vector , intercambias cierta velocidad de lectura (no mucho) para operaciones push y pop más rápidas.

Usando un deque lugar, y algunas optimizaciones obvias , obtengo:

const uint32_t num_partitions = 100000;
const size_t num_elements =     500000;

Filling std::multimap: 360000 ticks
Filling MyMumap:       530000 ticks

Reading std::multimap: 70000 ticks (0)
Reading MyMumap:       30000 ticks (0)

O en el caso "malo":

const uint32_t num_partitions = 100000;
const size_t num_elements =     200000;

Filling std::multimap: 100000 ticks
Filling MyMumap:       240000 ticks

Reading std::multimap: 30000 ticks (0)
Reading MyMumap:       10000 ticks (0)

Por lo tanto, la lectura es incondicionalmente más rápida, pero el llenado también es mucho más lento.

Answer 2

Un mapa de vectores viene con la sobrecarga de memoria para la capacidad de cada vector. std::vector normalmente asigna espacio para más elementos de los que realmente tiene. Puede que no sea un gran problema para su aplicación, pero es otra compensación que no ha considerado.

Si realiza muchas lecturas, entonces el tiempo de búsqueda O (1) de unordered_multimap podría ser una mejor opción.

Si tiene un compilador razonablemente moderno (y dada la presencia de la palabra clave auto , lo hace), en general tendrá dificultades para superar los contenedores estándar en términos de rendimiento y confiabilidad. Las personas que los escribieron son expertos. Siempre comenzaría con el contenedor estándar que expresa más fácilmente lo que quiere hacer. Perfile su código temprano y con frecuencia, y si no se está ejecutando lo suficientemente rápido, busque la forma de mejorarlo (por ejemplo, utilizando los contenedores unordered_ cuando realiza la mayoría de las lecturas).

Entonces, para responder a su pregunta original, si necesita una matriz asociativa de valores donde esos valores no serán únicos, entonces usar std::multimap definitivamente tiene sentido.

Answer 3

Es difícil decir si su punto de referencia está haciendo lo correcto, por lo que no puedo comentar sobre los números. Sin embargo, algunos puntos generales:

• Por qué multimap lugar de un mapa de vectores : Maps, multimaps, sets y multisets son esencialmente la misma estructura de datos, y una vez que tienes uno, es trivial simplemente deletrear los cuatro. Entonces, la primera respuesta es "¿por qué no tenerla?"

• ¿Cómo es útil ? Las multimapas son una de esas cosas que rara vez necesitas, pero cuando las necesitas, realmente las necesitas.

• ¿Por qué no lanzar mi propia solución? Como dije, no estoy seguro acerca de esos puntos de referencia, pero incluso si pudiera hacer algo más que no sea peor que el contenedor estándar (que cuestiono), entonces debe considerar la carga general de hacerlo bien, probarlo y manteniéndolo. Imagina un mundo en el que te cobrarían impuestos por cada línea de código que escribiste (esa es la sugerencia de Stepanov). Reutilice los componentes estándar de la industria siempre que sea posible.

Finalmente, esta es la forma típica de iterar un multimap:

for (auto it1 = m.cbegin(), it2 = it1, end = m.cend(); it1 != end; it1 = it2)
{
  // unique key values at this level
  for ( ; it2 != end && it2->first == it1->first; ++it2)
  {
    // equal key value (`== it1->first`) at this level
  }
}