Por que o push_back nos vetores C ++ é amortizado constantemente?

Estou aprendendo C ++ e notei que o tempo de execução da função push_back para vetores é "amortizado" constante. A documentação observa ainda que "se uma realocação acontecer, a realocação é linear em todo o tamanho".

Isso não significa que a função push_back é , onde é o comprimento do vetor? Afinal, estamos interessados ​​na análise do pior caso, certo?$O(n)$$n$

Acho que, crucialmente, não entendo como o adjetivo "amortizado" altera o tempo de execução.

A palavra importante aqui é "amortizado". A análise amortizada é uma técnica de análise que examina uma sequência de operações. Se a sequência inteira for executada no tempo T ( n ) , cada operação na sequência será executada em T ( n ) / n . A idéia é que, embora algumas operações na sequência possam ser caras, elas não podem acontecer com frequência suficiente para sobrecarregar o programa. É importante observar que isso é diferente da análise de caso médio em relação a alguma distribuição de entrada ou análise aleatória. A análise amortizada estabeleceu o pior caso$n$$T(n)$$T(n)/n$vinculado ao desempenho de um algoritmo, independentemente das entradas. É mais comumente usado para analisar estruturas de dados, que têm um estado persistente ao longo do programa.

Um dos exemplos mais comuns dados é a análise de uma pilha com operações multipop que exibem elementos. Uma análise ingênua do multipop diria que, na pior das hipóteses, o multipop deve levar O ( n ) tempo, pois pode ser necessário remover todos os elementos da pilha. No entanto, se você observar uma sequência de operações, perceberá que o número de pops não pode exceder o número de pushes. Assim, em qualquer sequência de n operações, o número de pops não pode exceder O ( n ) e, portanto, o multipop é executado em O ( 1 ) tempo amortizado , embora ocasionalmente uma única chamada possa levar mais tempo.$k$$O(n)$$n$$O(n)$$O(1)$

Agora, como isso se relaciona com vetores C ++? Os vetores são implementados com matrizes, para aumentar o tamanho de um vetor, você deve realocar a memória e copiar toda a matriz. Obviamente, não gostaríamos de fazer isso com muita frequência. Portanto, se você executar uma operação push_back e o vetor precisar alocar mais espaço, aumentará o tamanho em um fator . Agora, isso requer mais memória, que você pode não usar por completo, mas as próximas operações push_back são executadas em tempo constante.$m$

Agora, se fizermos a análise amortizada da operação push_back (que encontrei aqui ), descobriremos que ela é executada em tempo amortizado constante. Suponha que você tenha itens e seu fator de multiplicação é m . Então o número de realocações é aproximadamente log m ( n ) . O i th reatribuição custará proporcional a m i , sobre o tamanho da matriz corrente. Portanto, o tempo total para n push back é ∑ log m ( n ) i = 1 m i ≈ n $n$$m$$\log_m(n)$$i$$m^i$$n$ , já que é uma série geométrica. Divida isso pornoperações e obtemos que cada operação leva$\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$$n$ , uma constante. Por fim, você deve ter cuidado ao escolher seu fatorm. Se estiver muito próximo de1, essa constante ficará muito grande para aplicações práticas, mas semfor muito grande, digamos 2, você começará a desperdiçar muita memória. A taxa de crescimento ideal varia de acordo com o aplicativo, mas acho que algumas implementações usam1,5.$\frac{m}{m-1}$$m$$1$$m$$1.5$

Embora o @Marc tenha fornecido (o que eu acho que seja) uma excelente análise, algumas pessoas podem preferir considerar as coisas de um ângulo um pouco diferente.

Uma é considerar uma maneira ligeiramente diferente de realizar uma realocação. Em vez de copiar todos os elementos do armazenamento antigo para o novo armazenamento imediatamente, considere copiar apenas um elemento por vez - ou seja, cada vez que você faz um push_back, ele adiciona o novo elemento ao novo espaço e copia exatamente um existente elemento do espaço antigo para o novo espaço. Assumindo um fator de crescimento 2, é bastante óbvio que, quando o novo espaço estiver cheio, teríamos terminado de copiar todos os elementos do espaço antigo para o novo espaço, e cada push_back teria exatamente o tempo constante. Nesse ponto, descartávamos o espaço antigo, alocávamos um novo bloco de memória com ganho duas vezes maior e repetíamos o processo.

Muito claramente, podemos continuar indefinidamente (ou desde que haja memória disponível) e cada push_back envolveria a adição de um novo elemento e a cópia de um elemento antigo.

Uma implementação típica ainda tem exatamente o mesmo número de cópias - mas, em vez de fazer as cópias uma por vez, copia todos os elementos existentes de uma só vez. Por um lado, você está certo: isso significa que, se você observar invocações individuais de push_back, algumas delas serão substancialmente mais lentas que outras. Se observarmos uma média de longo prazo, no entanto, a quantidade de cópias feitas por chamada de push_back permanece constante, independentemente do tamanho do vetor.

Embora seja irrelevante para a complexidade computacional, acho que vale a pena apontar por que é vantajoso fazer as coisas como elas fazem, em vez de copiar um elemento por push_back, para que o tempo por push_back permaneça constante. Há pelo menos três razões a considerar.

O primeiro é simplesmente a disponibilidade de memória. A memória antiga pode ser liberada para outros usos somente após a conclusão da cópia. Se você apenas copiasse um item por vez, o antigo bloco de memória permaneceria alocado por muito mais tempo. Na verdade, você teria um bloco antigo e um novo bloco alocados essencialmente o tempo todo. Se você optar por um fator de crescimento menor que dois (o que geralmente deseja), precisará de ainda mais memória alocada o tempo todo.

Segundo, se você apenas copiasse um elemento antigo de cada vez, a indexação na matriz seria um pouco mais complicada - cada operação de indexação precisaria descobrir se o elemento no índice fornecido estava atualmente no antigo bloco de memória ou no novo. Isso não é terrivelmente complexo de forma alguma, mas para uma operação elementar como a indexação em uma matriz, quase qualquer desaceleração pode ser significativa.

Terceiro, copiando tudo de uma vez, você aproveita muito melhor o cache. Copiando de uma só vez, você pode esperar que a origem e o destino estejam no cache na maioria dos casos, para que o custo de uma falha de cache seja amortizado pelo número de elementos que caberão em uma linha de cache. Se você copiar um elemento de cada vez, poderá facilmente ter uma falta de cache para cada elemento que copiar. Isso muda apenas o fator constante, não a complexidade, mas ainda pode ser bastante significativo - para uma máquina típica, você pode esperar facilmente um fator de 10 a 20.

Provavelmente também vale a pena considerar a outra direção por um momento: se você estivesse projetando um sistema com requisitos em tempo real, seria bom copiar apenas um elemento de cada vez, em vez de todos de uma vez. Embora a velocidade geral possa (ou não) ser menor, você ainda terá um limite superior rígido no tempo necessário para uma única execução de push_back - presumindo que você tenha um alocador em tempo real (embora, é claro, muitos em tempo real os sistemas simplesmente proíbem a alocação dinâmica de memória, pelo menos em partes com requisitos em tempo real).