se (seq1 == seq2) versus se (str1.length () == str2.length () && seq1 == seq2)

Question

Eu vi um segundo em outro é o código e suponho que esta comparação comprimento ter sido feito para aumentar a produtividade de código. Foi utilizado em um analisador para uma linguagem de script com um dicionário específico: as palavras são de 4 a 24 letras com a média de 7-8 lettets, alfabeto inclui 26 letras latino-plus "@", "$" e "_".

comparação Comprimento foram usadas para escapar == operador trabalhar com strings STL, que, obviamente, leva mais tempo, então comparação inteiro simples. Mas na distribuição primeira letra mesmo tempo no dicionário dada é simplesmente maior do que uma distribuição de tamanho palavras, então duas primeiras letras de cordas comparando será geralmente mais frequentemente diferente, do que os tamanhos de que as cordas. Isso torna a comparação comprimento desnecessário.

Eu corri já alguns testes e isso é o que eu descobri: Ao testar duas seqüências aleatórias de comparação milhões de vezes, segundo caminho é muito mais rápido, então a comparação comprimento parece ser útil. Mas, em um projeto de trabalho que funciona mesmo mais lento em um modo de depuração e insufficiantly mais rápido em um modo de versão.

Então, minha pergunta é: por comparação comprimento pode prender a comparação e por isso pode retardá-lo

UPD: Eu não gosto dessa segunda maneira também, mas tinha sido feito por uma razão, suponho, e eu me pergunto, o que é esta razão

.

UPD2: Sério, a questão não é como fazer melhor. Não estou mesmo usando cordas STL neste caso anymore. Não é de admirar que a comparação comprimento é desnecessário e errado etc. A maravilha é - realmente tende a funcionar um pouco melhor em um determinado teste. Como isso é possível?

Answer 1

Em seu teste aleatório as cordas poderiam ter sido longo o suficiente para mostrar o ganho, enquanto no seu caso real, você pode lidar com cordas mais curtas e o fator constante de dois comparação não é compensada por qualquer ganho em não realizar a parte de comparação de seqüência de o teste.

Answer 2

Se isso importasse, assumir que a sua biblioteca fiz isso já. Não estrague o seu código desta forma para micro-otimizações a menos que realmente importa.

Answer 3

Quando pode curto-circuito ser benéfico

otimizações de curto-circuito pode ser útil apenas quando:

• o custo da comparação é baixa em comparação com o custo do teste completo
• a comparação muitas vezes resulta em curto-circuito

Matematicamente, seja S custo da condição curtos-circuitos, custo F de estado cheio, e P seja por cento dos casos em que acontece curtos-circuitos (condição completa não é necessária).

O custo médio de embalagem original (sem curto-circuito) é F

O custo médio de optimização curtos-circuitos é S + F * (1-P)

Portanto, se a otimização é ter qualquer benefício em tudo, a seguir deve aplicar:

S + F * (1-P)

i.

S

Cordas custo comparação

Além disso, você escreveu:

que, obviamente, leva mais tempo, então comparação inteiro simples.

Este não é óbvia a todos. Os termina comparação de string quando a primeira diferença é encontrada, portanto, dependendo do que cordas de processar, pode terminar em primeiro ou segundo personagem na grande maioria dos casos. Além disso, a comparação pode ser optimizado mesmo para as cadeias mais longas por primeiros DWORDS comparando (4 caracteres ao mesmo tempo), desde que haja dados suficientes em ambas as cadeias.

Seu caso

A principal diferença entre os dados de teste aleatório e scripts de análise são os dados reais estão longe de ser aleatória. O analisador é mais provável determinista, e uma vez que corresponde, não se compara mais. Mesmo os dados de script não são aleatórias - algumas palavras-chave são susceptíveis de ser usados ??muito mais do que outros. Se o analisador é construído de tal forma ele verifica mais comumente usado palavras-chave em primeiro lugar, um número surpreendentemente elevado de comparações pode precisar a plena comparar a ser feito, tão cheio comparar sempre precisa ser feito quando a corda é correspondente.

Answer 4

Geralmente, você deve deixar isso para o STL e não se preocupar com isso.

No entanto, se esta é uma área que você precisa para otimizar (o que eu duvido seriamente), e se você entender a distribuição de distribuição de letra / comprimento de suas cordas, você pode derivar uma nova classe de corda, e sobrecarregar o operador == para realizar o teste de igualdade da forma mais eficiente para a sua aplicação. (Comprimento primeiro, primeiro caractere em primeiro lugar, para a frente, para trás, o que for).

Isso seria melhor do que ter o 'otimização' espalhados por todo o seu código.

Answer 5

A implementação do operador std :: string == não tem nenhuma maneira de saber se seria mais rápido para verificar o comprimento primeira ou começar a verificar caracteres. Claramente verificar o comprimento é um desperdício para cordas do mesmo comprimento. Portanto, diferentes implementações de STL estão propensos a realizar de forma diferente.

Só colocar a verificação de comprimento explícito em como otimização final (claramente comentou como tal), e somente se seus confirma profiler o benefício.

Answer 6

comparação comprimento não faz qualquer sentido para mim .. usando o operador de comparação é suficiente

Answer 7

disparar a sua implementação de STL. Não deve importar

Answer 8

A comparação comprimento é lá para tentar alguma otimização de curto-circuito.

Estou assumindo a comparação comprimento é mais rápido do que a cadeia completa comparar, por isso, se que pode eliminar 99% de desencontros, vai ser mais rápido do que fazendo a cadeia completa comparar cada tempo.

O código irá executar a comparação comprimento, vai falhar, então ele irá ignorar a cadeia completa comparar e pular o código.

Answer 9

O comprimento do std :: string é bastante provável um membro do objeto std :: string. Em comparação, o primeiro caractere pode muito bem ser na pilha. Isso significa que, comparando o comprimento da corda melhora a localidade de referência. Claro que, com a otimização de curto corda isso se torna ainda mais complexa - Lhs[0] pode estar na pilha enquanto Rhs[0] está na pilha

.