¿Std :: deque tiene realmente una inserción de tiempo constante al principio?

8

El estándar dice:

Un deque es un contenedor de secuencia que admite iteradores de acceso aleatorio (27.2.7). Además, admite operaciones de inserción y borrado de tiempo constante al principio o al final; insertar y borrar en el medio toma tiempo lineal.

Sin embargo, también dice en la misma Cláusula:

Todos los requisitos de complejidad en esta Cláusula se establecen únicamente en términos del número de operaciones en los objetos contenidos. [Ejemplo: el constructor de copia de tipo vector<vector<int>>tiene una complejidad lineal, aunque la complejidad de copiar cada contenido vector<int>es lineal en sí misma. - ejemplo final]

¿No significa esto que la inserción al comienzo de, digamos, deque<int>puede tomar tiempo lineal siempre que no realice más que un número constante de operaciones en los ints que ya están en la deque y el nuevo intobjeto que se está insertando? ?

Por ejemplo, supongamos que implementamos una deque utilizando un "vector de vectores de tamaño K". Parece que una vez cada K veces que insertemos al principio, se debe agregar un nuevo vector de tamaño K al principio, por lo que todos los demás vectores de tamaño K deben moverse. Esto significaría que la complejidad temporal de la inserción al principio se amortiza O (N / K) donde N es el número total de elementos, pero K es constante, por lo que esto es solo O (N). Pero parece que esto está permitido por el Estándar, porque mover un vector de tamaño K no mueve ninguno de sus elementos, y los "requisitos de complejidad" están "establecidos únicamente en términos del número de operaciones" en los intobjetos contenidos .

¿El estándar realmente permite esto? ¿O deberíamos interpretar que tiene un requisito más estricto, es decir , un número constante de operaciones en los objetos contenidos más un tiempo adicional constante?

Brian
fuente
2
Tu interpretación suena plausible. Para agregar más combustible al fuego, [deque.modifiers] tiene una inserción en el medio del deque invalida todos los iteradores y referencias a elementos del deque. Una inserción en cualquier extremo de la deque invalida todos los iteradores de la deque, pero no tiene ningún efecto sobre la validez de las referencias a elementos de la deque. Que al igual que su ejemplo vectorial funciona, ya que el movimiento invalida los iteradores pero no las referencias.
NathanOliver
Creo que el ejemplo es un poco confuso porque usa "lineal" una vez para lineal con respecto al número de elemento del vector<vector<int>>pero luego lineal con respecto a los elementos del interior vector<int>. Si solo considera el número de elementos del vector externo, consideraría copiar el vector interno como constante, aunque podría estar equivocado, ya es tarde aquí
idclev 463035818

Respuestas:

2

Por ejemplo, supongamos que implementamos una deque usando un "vector de vectores de tamaño K".

Esa no sería una implementación válida. La inserción en la parte frontal de un vectorinvalida todos los punteros / referencias en el contenedor. dequese requiere para no invalidar ningún puntero / referencia en la inserción frontal.

Pero ignoremos eso por ahora.

Pero parece que esto está permitido por el Estándar, porque mover un vector de tamaño K no mueve ninguno de sus elementos, y los "requisitos de complejidad" están "establecidos únicamente en términos del número de operaciones" en los objetos int contenidos .

Sí, eso estaría permitido. De hecho, las implementaciones reales de dequeno son tan diferentes de eso (aunque no se usan std::vectorpor razones obvias). El esquema general de una dequeimplementación es una matriz de punteros a bloques (con espacio para crecimiento tanto en el frente como en la parte posterior), con cada bloque que contiene hasta X elementos, así como punteros a los bloques siguientes / anteriores (para hacer iteración de elementos rápida).

Si inserta suficientes elementos en la parte frontal o posterior, entonces la matriz de punteros de bloque tiene que crecer. Eso requerirá una operación que es tiempo lineal en relación con el número de elementos en el deque, pero que en realidad no opera en los elementos, por lo que no cuenta. La especificación no tiene nada que decir sobre la complejidad de esa operación.

Sin esta disposición, no estoy seguro de si el conjunto único de características de deque(inserción frontal / posterior rápida y acceso aleatorio) sería implementable.

Nicol Bolas
fuente
"Una inserción en cualquier extremo de la deque invalida todos los iteradores de la deque, pero no tiene ningún efecto sobre la validez de las referencias a elementos de la deque".
Brian
Obviamente, una inserción en la parte delantera o trasera a veces tomará tiempo lineal. Pero si el conjunto de punteros tiene espacio en el frente, entonces el tiempo debe amortizarse constantemente. Si no tiene espacio en el frente, entonces el tiempo no se amortiza constantemente. Estoy preguntando si esto último está permitido.
Brian
@Brian: " Pero si la matriz de punteros realmente tiene espacio en el frente, entonces el tiempo debe amortizarse constantemente " Eso no es lo que significa " constante amortizada ". Significa que la distancia entre las N cuando tiene que ser no constante siempre aumenta. Si vectorla implementación de un cambio de tamaño automático solo agrega un número constante de elementos adicionales, entonces la inserción no sería "constante amortizada". Entonces no se trata simplemente de tener espacio; tienes que insertar más espacio cada vez.
Nicol Bolas
@Brian: Y sí, no hay nada sobre los dequerequisitos de que cualquiera de los insertos sea "constante amortizada" con respecto al número de artículos en el contenedor; solo es constante con respecto al número de operaciones en artículos en el contenedor.
Nicol Bolas
"Constante amortizada" significa que hay una constante c tal que si realiza N operaciones, entonces el tiempo total empleado es como máximo cN. Como dije, si la deque no mantiene espacio en el frente, entonces obviamente las inserciones en el frente no pueden amortizarse de manera constante. Si la deque mantiene suficiente espacio en el frente (más de una cantidad constante, como usted dice), entonces es posible que se amortice de manera constante. Sin embargo, en ambos casos, será constante en términos de operaciones en elementos.
Brian
1

Creo que estás llegando un poco, en cómo interpretas el significado de los dominios de complejidad. Estás tratando de hacer una distinción entre "tiempo lineal" y "complejidad lineal" que no estoy convencido tiene mucho sentido.

El estándar es claro que la inserción en el frente es de tiempo constante, y creo que todos estamos de acuerdo en eso. El último pasaje simplemente nos dice que lo que cada una de esas cantidades "constantes" de operaciones involucra debajo simplemente no está especificado o limitado por el estándar.

Y esto no es inusual. Cualquier algoritmo funciona sobre alguna base de abstracción. Incluso si tuviéramos que escribir un algoritmo que se redujera a instrucciones de máquina individuales, y dijéramos que solo había N instrucciones de máquina generadas por nuestro algoritmo, no investigaríamos qué tipo de complejidad tiene cada complejidad individual dentro del procesador y agregue eso a nuestros resultados. No diríamos que algunas operaciones terminan haciendo más en el nivel molecular cuántico y, por lo tanto, nuestro algoritmo O (n) es en realidad O (N × M 3 ) o somesuch. Elegimos no considerar ese nivel de abstracción. Y, a menos que dicha complejidad dependa de las entradas del algoritmo, está completamente bien.

En su caso, el tamaño de los vectores internos movidos / copiados no es realmente relevante, porque estos no cambian inherentemente a medida que crece la disminución. El número de vectores internos sí, pero el tamaño de cada uno es una propiedad independiente. Por lo tanto, es irrelevante al describir la complejidad de insertar un nuevo elemento en el vector externo.

¿El tiempo de ejecución real (que podría describirse en algunos términos algorítmicos si así lo elige) varía según el contenido de los vectores internos copiados? Sí, por supuesto. Pero eso no tiene nada que ver con cómo la tarea de expandir el vector externo crece en la carga de trabajo a medida que crece el vector externo.

Entonces, aquí, el estándar dice que no copiará N o N 2 ni siquiera registrará N vectores internos cuando coloque otro en el frente; está diciendo que el número de estas operaciones no cambiará de escala a medida que crezca su deque. También dice que, a los efectos de esa regla, no le importa lo que realmente implica copiar / mover los vectores internos o qué tan grandes son.

El análisis de complejidad no se trata de rendimiento. El análisis de complejidad trata sobre cómo escala el rendimiento.

Asteroides con alas
fuente
Nota de inicio: si realmente lo desea, puede describir la complejidad de la operación como no O (1) , sino O (A + B + C + D + E + F + ...) donde esas variables internas se relacionan con el tamaño de la operación elementos existentes afectados, o alguna otra función de ellos ... pero eso sería (a) no útil, (b) además del punto de la regla que se define en ese pasaje, y (c) una pérdida de tiempo, ya que el estándar ya nos ha informado que no habrá impacto en esos elementos existentes.
Asteroides con alas