Comparação de métodos de iteração: número de iterações x tempo da CPU

Estou comparando dois métodos iterativos para inverter matrizes quadradas aleatórias. Como as matrizes são aleatórias, todo caso de teste leva quantidades diferentes de iterações e diferentes tempos decorridos. Minha pergunta é, além do tempo médio da CPU, o valor médio das iterações realizadas pelas informações úteis dos dois métodos para comparar os métodos.

performance benchmarking srijan
fonte

Reescrevi sua pergunta para torná-la mais clara. Por favor, certifique-se de que eu não mudei seu significado de forma alguma.

Godric Seer

@GodricSeer Sua edição melhorou minha pergunta. Graças

srijan

Respostas:

Em geral, ambos os métodos de comparação de desempenho têm seu lugar.

Comparar o tempo da CPU é, de certo modo, a métrica mais interessante, porque no final do dia você está realmente interessado em qual dos métodos é mais rápido. (Mas verifique se os critérios de término são comparáveis; por exemplo, se os dois métodos produzem uma aproximação com a mesma precisão). A desvantagem é que isso apenas informa qual método (e mais importante, qual implementação ) é mais rápido na máquina em que você executou os testes. Não há garantia de que uma máquina diferente com arquitetura ou software diferente escolha o mesmo vencedor.
A comparação de números de iteração , por outro lado, é independente da máquina, mas potencialmente enganosa se os dois métodos tiverem iterações muito diferentes - nesse caso, o método com iterações menos caras mas mais caras pode não ser preferido (por exemplo, métodos de otimização de Newton vs. gradiente se você precisar de precisão muito baixa).

Então, sim, faz sentido fornecer os dois números [1], e eu já o vi com frequência em publicações. Há também uma terceira opção:

Comparando números de operações elementares . Se ambas as iterações consistirem no mesmo tipo de operação dispendiosa, mas exigirem um número diferente (possivelmente nem mesmo o mesmo número em cada iteração), faz sentido contar o número total dessas operações. No seu caso, um candidato provável seria multiplicações vetor-matriz ou matriz-matriz.

[1] Definitivamente apresente estatísticas sobre várias execuções; se você mostrar meios, não esqueça de incluir também os desvios padrão.

Christian Clason
fonte

Não basta ter meios! Se você tiver pontos de teste suficientes com entradas aleatórias, plote uma distribuição.

Bill Barth

@ BillBarth - bom argumento, embora isso nem sempre seja viável; mas sempre é possível fornecer desvios padrão juntamente com a média. De fato, quais estatísticas apresentar para relatar o desempenho parecem uma excelente pergunta de acompanhamento.

Christian Clason

@ BillBarth Você fez um bom argumento. Mas estou usando várias matrizes de teste em ordem crescente. Para tais casos, não é viável plotar a distribuição desde então, eu tenho que plotar as distribuições para todas as outras matrizes de teste. É por isso que eu queria tabulá-los. Obrigado por seus comentários.

srijan

@srijan: Você terá os dados, deve plotar histogramas sempre que puder. Você não precisa publicá-las todas, mas prometo que um gráfico da distribuição lhe dirá mais do que um mar de números ou apenas as médias.

Bill Barth

Eu incluiria o tempo de execução por iteração. Como cada matriz é diferente, você pode ter um número diferente de iterações com diferentes tempos de execução. Juntamente com o que o @Cristian disse, o tempo de execução por iteração seria útil.

Jbcolmenares

Acho que o número de iterações é uma métrica enganosa, porque sugere "velocidade" quando não é. Para um exemplo simples de comparação de alguns pré-condicionadores diferentes que mostram essa diferença, consulte aqui: http://www.dealii.org/developer/doxygen/deal.II/step_6.html#Possibilityforextensions

Wolfgang Bangerth
fonte

Obrigado pela resposta. Não consigo entender essa linha 'número de iterações como uma métrica enganosa, porque sugere "velocidade" quando não é ". O exemplo que você sugeriu é um pouco difícil para mim entender.

srijan

O que estou dizendo é que geralmente apresentamos "número de iterações" como equivalente ao "tempo de CPU usado", o que implica que um método que requer menos iterações também é mais rápido. Mas isso não é verdade, como mostram os números aos quais vinculei.

Wolfgang Bangerth

Agora, eu entendi perfeitamente o seu ponto. O mesmo que observei com o método newtons para aproximação inversa de uma matriz quadrada. Como a ordem do método aumenta, inicialmente o tempo da CPU e o número de iterações diminuem, mas à medida que a ordem aumenta, o tempo de início da CPU aumenta mesmo que o número de iterações diminua. Muito obrigado pela sua resposta.

srijan

Caso não esteja claro nas outras respostas, para que serve o número de iterações é o argumento do grande O.

Não é bom para velocidade absoluta, porque isso depende do tempo médio por iteração, que pode diferir entre os métodos por um grande fator.

Por exemplo, há uma tendência a ignorar o custo do cálculo de índices de matriz, e isso pode ser responsável por uma grande fração do tempo da CPU.

ADICIONADO: Além disso, como já apontei em outro lugar, para cada chamada do método, normalmente há um custo de instalação. Então, se as matrizes geralmente não são muito grandes, esse custo de instalação pode ser responsável por uma grande fração do tempo da CPU (de modo que removê-la faria uma grande diferença na velocidade).

Mike Dunlavey
fonte