Es list :: size () realmente O (n)?

StackOverflow https://stackoverflow.com/questions/228908

Pregunta

Recientemente, noté que algunas personas mencionan que std :: list :: size () tiene una complejidad lineal.
Según some sources , esto es en realidad dependiente de la implementación ya que el estándar no dice cuál debe ser la complejidad.
El comentario en esta entrada de blog dice :

  

En realidad, depende de qué STL   están usando. Microsoft Visual Studio V6   implementa size () como {return (_Size);   } mientras que gcc (al menos en versiones   3.3.2 y 4.1.0) hacerlo como {return std :: distance (begin (), end ()); } Los   primero tiene velocidad constante, el segundo   tiene o (N) velocidad

  1. Así que mi conjetura es que para la multitud VC ++ size () tiene una complejidad constante como Dinkumware Probablemente no haya cambiado ese hecho desde VC6. ¿Estoy ahí?
  2. ¿Cómo se ve actualmente en gcc ? Si es realmente O (n), ¿por qué el los desarrolladores eligen hacerlo?
¿Fue útil?

Solución

Respuesta anterior a C ++ 11

Tienes razón en que el estándar no establece cuál debe ser la complejidad de list :: size (), sin embargo, recomienda que " tenga una complejidad constante " (Nota A en la Tabla 65).

Aquí hay un interesante artículo de Howard Hinnant que explica por qué algunas personas piensan en la lista :: tamaño ( ) debe tener complejidad O (N) (básicamente porque creen que O (1) list :: size () hace que list :: splice () tenga complejidad O (N)) y por qué una lista O (1) :: size ( ) es una buena idea (en opinión del autor):

Creo que los puntos principales del documento son:

  • hay pocas situaciones en las que mantener un recuento interno, por lo que list :: size () puede ser O (1) hace que la operación de empalme se vuelva lineal
  • probablemente hay muchas más situaciones en las que alguien podría desconocer los efectos negativos que pueden ocurrir debido a que llaman a un O (N) tamaño () (como su ejemplo en el que lista :: se llama a size () mientras se mantiene un candado).
  • que en lugar de permitir que tamaño () sea O (N), en aras de la "sorpresa mínima", la norma debería requerir cualquier contenedor que implemente tamaño () para implementarlo en forma O (1). Si un contenedor no puede hacer esto, no debe implementar size () en absoluto. En este caso, el usuario del contenedor sabrá que size () no está disponible, y si aún desean o necesitan obtener la cantidad de elementos en el contenedor, pueden seguir utilizando container :: distance (begin (), end ()) para obtener ese valor, pero sabrán que es una operación O (N).

Creo que tiendo a estar de acuerdo con la mayor parte de su razonamiento. Sin embargo, no me gusta su adición propuesta a las sobrecargas de splice () . Tener que pasar un n que debe ser igual a distancia (primero, último) para obtener el comportamiento correcto parece una receta para los errores difíciles de diagnosticar.

No estoy seguro de qué debería o podría hacerse para avanzar, ya que cualquier cambio tendría un impacto significativo en el código existente. Pero tal como está, creo que el código existente ya está afectado, el comportamiento puede ser bastante diferente de una implementación a otra por algo que debería haber sido bien definido. Tal vez el comentario de onebyone sobre tener el tamaño 'almacenado en caché' y marcado como conocido / desconocido podría funcionar bien - obtiene un comportamiento O (1) amortizado - la única vez que obtiene un comportamiento O (N) es cuando la lista es modificada por algunas operaciones de empalme () . Lo bueno de esto es que los implementadores pueden hacerlo hoy sin un cambio en el estándar (a menos que me esté perdiendo algo).

Por lo que sé, C ++ 0x no está cambiando nada en esta área.

Otros consejos

En C ++ 11 se requiere que para cualquier contenedor estándar, la operación .size () debe estar completa en " constante " complejidad (O (1)). (Tabla 96 - Requisitos de contenedores). Anteriormente, en C ++ 03 .size () debería tener una complejidad constante, pero no es obligatorio (consulte ¿Es std :: string size () una operación O (1)? ).

El cambio en el estándar es introducido por n2923 : Especificando la complejidad del tamaño () (Revisión 1) .

Sin embargo, la implementación de .size () en libstdc ++ todavía usa un algoritmo O (N) en gcc hasta 4.8: 

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

Vea también ¿Por qué std :: list es más grande en c ++ 11? para detalles por qué se mantiene de esta manera.

Actualización : std :: list :: size () es correctamente O (1) cuando se usa gcc 5.0 en el modo C ++ 11 (o superior).

Por cierto, el .size () en libc ++ es correctamente O (1): 

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

He tenido que buscar en la lista de gcc 3.4 :: tamaño antes, así que puedo decir esto:

  1. usa std :: distance (head, tail)
  2. std :: distance tiene dos implementaciones: para tipos que satisfacen RandomAccessIterator, usa "tail-head", y para tipos que simplemente satisfacen InputIterator, usa un algoritmo O (n) que se basa en & it; iterator ++ " , contando hasta que llegue a la cola dada.
  3. std :: list no satsifica RandomAccessIterator, por lo que el tamaño es O (n).

En cuanto al " por qué " ;, solo puedo decir que std :: list es apropiado para problemas que requieren acceso secuencial. Almacenar el tamaño como una variable de clase introduciría una sobrecarga en cada inserción, eliminación, etc., y ese desperdicio es un gran no-no por la intención de la STL. Si realmente necesita un tamaño de tiempo constante (), use std :: deque.

Personalmente no veo que el problema con el empalme sea O (N) como la única razón por la que se permite que el tamaño sea O (N). No pagas por lo que no usas es un lema importante de C ++. En este caso, mantener el tamaño de la lista requiere un incremento / decremento adicional en cada inserción / borrado, ya sea que verifique el tamaño de la lista o no. Esta es una pequeña sobrecarga fija, pero todavía es importante tener en cuenta.

Rara vez es necesario verificar el tamaño de una lista. Iterar de principio a fin sin importar el tamaño total es infinitamente más común.

Iría a la fuente ( archive ). La página STL de SGI dice que está permitido tener una complejidad lineal. Creo que la guía de diseño que siguieron fue permitir que la implementación de la lista sea lo más general posible y, por lo tanto, permitir una mayor flexibilidad en el uso de listas.

Este informe de error: [C ++ 0x] std :: list: : complejidad de tamaño , captura en detalle insoportable el hecho de que la implementación en GCC 4.x es un tiempo lineal y que la transición al tiempo constante para C ++ 11 se produjo (disponible en 5.0) debido a la compatibilidad ABI preocupaciones.

La página de manual de la serie GCC 4.9 aún incluye la siguiente renuncia de responsabilidad:

  

El soporte para C ++ 11 sigue siendo   Experimental, y puede cambiar de manera incompatible en futuras versiones.

Se hace referencia al mismo informe de error aquí: ¿Debe std :: list :: size tener complejidad constante en C ++ 11?

Si está utilizando correctamente las listas, probablemente no note ninguna diferencia.

Las listas son buenas con las estructuras de datos grandes que desea reorganizar sin copiar, para los datos que desea mantener punteros válidos después de la inserción.

En el primer caso no hace ninguna diferencia, en el segundo preferiría la implementación antigua (más pequeña) de tamaño ().

De todos modos, std es más sobre la corrección y el comportamiento estándar y la 'facilidad de uso' que la velocidad bruta.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top