He oído de un amigo mío que el mejor algoritmo para el intercambio es "(a^= b^= a^= b)" donde ayb son dos enteros que se intercambiarán. pero cuando apliqué esto usando el lenguaje c causó un bloqueo. ¿alguien de ustedes puede explicar la posible razón para eso? por favor sugiera el mejor algoritmo para el intercambio. gracias !!!! chicos me gustaría saber el motivo de la falla.¿el mejor algoritmo para el intercambio?
este truco de intercambio a veces es peligroso, he visto un programa de quicksort incorrecto al usar este intercambio genera resultados incorrectos. Pero un intercambio habitual genera un programa correcto.
Respecto a la velocidad, el compilador a veces genera código más rápido si usamos una variable tmp.
uso tmp = a; a = b; b = tmp;
gracias @yin me gustaría saber por qué mi truco es muy peligroso? –
XOR swap ('a^= b^= a^= b') solo funcionará en enteros (y punteros). El intercambio XOR cambiará tanto 'a' como' b' a 0 si son iguales. – LiraNuna
Suponga que 'a' y' b' son punteros que apuntan a la misma cosa. Luego '(* a)^= (* b)^= (* a)^= (* b)' pondrá a cero el valor. En C++ si se trata de referencias, puede hacer esto sin la desreferencia. Pero la verdadera razón para usar lo que @Yin Zhu sugiere es que su código debe ser claro, y no debe preocuparse por una micro-optimización como esta. – rlbond
uso de esta lógica de valores numéricos:
int a = 10, b =5 ;
a = a-b;
b = b+a ; // b gets the original value of a
a = b - a; // a gets the original value of b
printf ("value : %d %d \n",a ,b) ;
¿Qué pasa cuando se '' a 'INT_MAX', y' 'B' es INT_MIN'? En otras palabras, 'a-b' puede desbordarse/subdesbordarse. –
@Alok: a pesar del desbordamiento, aún dará la respuesta correcta con aritmética envolvente. – dan04
@ dan04: no se garantiza el envolvente - en C/C++ el desbordamiento entero es UB. –
Ver http://en.wikipedia.org/wiki/Swap_(computer_science).
El uso de una variable temporal genera más sobrecarga, pero es más estable que el algoritmo de intercambio XOR y la computación en paralelo lo hace más rápido que el intercambio XOR.
Consulte el primer ejemplo de código de http://www.ibm.com/developerworks/linux/library/l-metaprog1.html para una implementación sólida del uso de una variable temporal para el intercambio.
¿por qué genera más sobrecarga para la solución de variable temporal? El intercambio XOR también crea más sobrecarga de cómputo también. – phoxis
a^=b^=a^=b; probablemente se cuelgue debido a que invoca el comportamiento indeterminado de . La regla que rompe es que modifica a dos veces sin un punto de secuencia intermedio. Se puede fijar mediante la inserción de algunos puntos de secuencia - por ejemplo, con el operador coma:
a ^= (b ^= a ^= b, b);`
O por dividirlo en varias instrucciones:
b ^= a ^= b; a ^= b;
Sigue siendo, sin embargo, por lo general una mala método para intercambiar variables: varias de las otras respuestas y comentarios explican adecuadamente por qué.
Escriba el código que es más rápido de leer por el ser humano. Y confía en la capacidad de los compiladores para generar mejores códigos la mayor parte del tiempo. Haz un perfil para ver si este es el único lugar para mejorar la velocidad. Luego aplique las soluciones XOR enumeradas muchas veces arriba, puede que no funcione en todas partes.
No puedo creer que esto sea siquiera una pregunta sobre SO. ¿Qué pasa con 'std :: swap'? –
@BillyONeal: desde std :: swap es C++ y esta pregunta está etiquetada con C. – LiraNuna
OK - Perdón - Permíteme cambiar eso a "¿Qué pasa con la simple implementación simple típica de' std :: swap'? 'T temp = one; one = two; two = temp; '? En serio - si swap es un limitador de velocidad de su programa, entonces tiene un problema que me gustaría tener. –