[C] Algoritmo swap sem variável auxiliar - Tutoriais - Portugal-a-Programar
[C] Algoritmo swap sem variável auxiliar
Por Cypher, 3 de Setembro de 2007 em Tutoriais
Algoritmos de troca convencionais necessitam de uma variável de armazenamento temporário. Este tipo de algoritmo pode fazer o programador cair em uma armadilha: imagine que um inteiro possa guardar números de 0 até 100. Se x for igual a 70 e y for igual a 100, será passado o limite de armazenamento da variável.
Usando o algoritmo XOR Swap, esse tipo de problema não ocorre e nenhum armazenamento temporário é necessário. O algoritmo é o seguinte:
1. x := x XOR y
2. y := x XOR y
3. x := x XOR y
onde R1 e R2 são registradores e a operação XOR coloca o resultado no primeiro argumento. Para programadores assembly esse algoritmo é particularmente interessante por sua eficiência e performance. Ele elimina o uso de registrador intermediário, que é um recurso limitado em programação em linguagem de máquina. Ele também elimina dois ciclos de acesso à memória, que são caros se comparados com uma operação no registrador
1. X = x ⊕ y, Y = y
2. Y = x ⊕ y, Y = x ⊕ y ⊕ y = x
3. X = x ⊕ y ⊕ x = y, Y = x
* x ^= *y;
* y ^= *x;
/* Versão compacta: *x^=*y^=*x^=*y; */
Edit: ja alterei o código! estava incorrecto o Triton já me tinha avisado só que não tive tempo...
Interessante, mas é preciso ter em atenção que só funciona para números inteiros. Para floating-point ou strings, usa-se o método convencional (com a variável que armazena temporariamente o valor de uma das variáveis a trocar).
Segundo li na Wikipedia inglesa, qualquer compilador moderno, com as devidas optimizações ligadas, consegue detectar um código de swap com variável temporária e optimizar para código mais rápido ainda que este.
Apesar de conhecer esta forma, utilizo sempre o swap com variavel temporária por ser mais intuitivo.
Supostamente esta técnica é um pouco mais rápida do que o swap com variável temporária.
Muito interessante, já me aconteceu de ter 2 porções de código em que usando a supostamente mais rápida, na realidade o programa fica mais lento. Talvez seja uma explicação
Só uma coisa, o código não está errado ? Não deveria ser:
Só uma coisa, o código não está errado ?
Está, já tinha avisado o Cypher em relação a isso.
Bem para saber isso, só sabendo o tempo que demora a execução de cada tarefa, xor ou cópia de registos. A grande vantagem deste método é mesmo não precisar de variàvel auxiliar, e numa situação em que tenhas os registos todos ocupados este método é claramente mais rápido uma vez que com o método de variável temporária irias ter que aceder à memória.
Tanto quando sei, qualquer operação ao nivel dos bits ( And , Or , Xor , Shifts ) é extremamente rápida por existem no processador circuitos que fazem isto directamente.
Eu penso que o tempo de alocar uma nova variável e a cópia de registos deveria ser mais lento.
Já não digo que "é mais lento" devido aquilo que o Triton referiu
PS: Só para explicar a razão de não usar esta forma: este código não é intuitivo... se fosse rever uma porção de código feita há uns meses, provavelmente não me ia lembrar que aquilo era um swap (a menos que o utilizasse muitas vezes)
A família de processadores x86 tem uma instrução chamada XCHG que faz a troca de valores entre registos directamente.
Modern optimizing compilers work by translating the code they are given into an internal flow-based representation which they transform in many ways before producing their machine-code output. These compilers are more likely to recognize and optimize a conventional (temporary-based) swap than to recognize the high-level language statements that correspond to a XOR swap. Many times, what is written as a swap in high-level code is translated by the compiler into a simple internal note that two variables have swapped memory addresses, rather than any amount of machine code. Other times, when the target architecture supports it, the compiler can use a single XCHG (exchange) instruction which performs the swap in a single operation.