En programación de computadoras , el acto de intercambiar dos variables se refiere a intercambiar mutuamente los valores de las variables. Por lo general, esto se hace con los datos en la memoria . Por ejemplo, en un programa , se pueden definir dos variables así (en pseudocódigo ):
elemento_datos x: = 1elemento_datos y: = 0swap (x, y);
Después de realizar swap (), x contendrá el valor 0 e y contendrá 1; sus valores han sido intercambiados. Esta operación puede generalizarse a otros tipos de valores, como cadenas y tipos de datos agregados . Los tipos de comparación utilizan intercambios para cambiar las posiciones de los datos.
En muchos lenguajes de programación, la función de intercambio está incorporada. En C ++ , se proporcionan sobrecargas que permiten a std :: swap intercambiar algunas estructuras grandes en tiempo O (1).
Usando una variable temporal
El método más simple y probablemente más utilizado para intercambiar dos variables es usar una tercera variable temporal :
definir swap (x, y) temp: = x x: = y y: = temp
Si bien esto es conceptualmente simple y en muchos casos la única forma conveniente de intercambiar dos variables, utiliza memoria adicional. Aunque esto no debería ser un problema en la mayoría de las aplicaciones, los tamaños de los valores que se intercambian pueden ser enormes (lo que significa que la variable temporal también puede ocupar mucha memoria), o es posible que la operación de intercambio deba realizarse muchas veces, como en algoritmos de clasificación.
Además, intercambiar dos variables en lenguajes orientados a objetos como C ++ puede implicar una llamada al constructor de clase y al destructor de la variable temporal, y tres llamadas al constructor de copia . Algunas clases pueden asignar memoria en el constructor y desasignarla en el destructor, creando así costosas llamadas al sistema. Los constructores de copia para clases que contienen una gran cantidad de datos, por ejemplo, en una matriz , pueden incluso necesitar copiar los datos manualmente.
Intercambio de XOR
El intercambio de XOR utiliza la operación XOR para intercambiar dos variables numéricas. Generalmente se promociona que es más rápido que el método ingenuo mencionado anteriormente; sin embargo, tiene desventajas . El intercambio de XOR se usa generalmente para intercambiar tipos de datos de bajo nivel, como enteros . Sin embargo, en teoría, es capaz de intercambiar dos valores cualesquiera que puedan representarse mediante cadenas de bits de longitud fija .
Intercambiar mediante suma y resta
Este método intercambia dos variables sumando y restando sus valores. Rara vez se utiliza en aplicaciones prácticas, principalmente porque:
- Solo puede intercambiar variables numéricas; Puede que no sea posible o lógico sumar o restar tipos de datos complejos, como contenedores .
- Al intercambiar variables de un tamaño fijo, el desbordamiento aritmético se convierte en un problema.
- Generalmente, no funciona para valores de punto flotante, porque la aritmética de punto flotante no es asociativa .
Intercambio de contenedores
Los contenedores que asignan memoria del montón utilizando punteros se pueden intercambiar en una sola operación, intercambiando los punteros solos. Esto generalmente se encuentra en lenguajes de programación que admiten punteros, como C o C ++ . La biblioteca de plantillas estándar sobrecarga su función de intercambio incorporada para intercambiar el contenido de los contenedores de manera eficiente de esta manera. [1]
Como las variables de puntero suelen tener un tamaño fijo (p. Ej., La mayoría de las computadoras de escritorio tienen punteros de 64 bits de longitud) y son numéricas, se pueden intercambiar rápidamente mediante intercambio XOR .
Asignación paralela
Algunos lenguajes, como Ruby o Python, admiten asignaciones paralelas , lo que simplifica la notación para intercambiar dos variables:
a, b = b, a
Esta es la abreviatura de una operación que involucra una estructura de datos intermedia: en Python, una tupla; en Ruby, una matriz.
Javascript 6+ admite operadores de desestructuración que hacen lo mismo:
[a, b] = [b, a];
Facilitación del intercambio en computadoras modernas
Instrucciones dedicadas
Debido a las muchas aplicaciones de intercambio de datos en las computadoras, la mayoría de los procesadores ahora brindan la capacidad de intercambiar variables directamente a través de instrucciones integradas. Los procesadores x86 , por ejemplo, incluyen una instrucción XCHG para intercambiar dos registros directamente sin requerir que se utilice un tercer registro temporal. A -y-swap comparar instrucción se incluso proporciona en algunas arquitecturas de procesador, que se compara y condicionalmente intercambia dos registros. Esto se utiliza para apoyar las técnicas de exclusión mutua .
XCHG puede no ser tan eficiente como parece. Por ejemplo, en los procesadores x86 , XCHG bloqueará implícitamente el acceso a cualquier operando en la memoria para garantizar que la operación sea atómica y, por lo tanto, puede que no sea eficiente al intercambiar memoria. Dicho bloqueo es importante cuando se utiliza para implementar la sincronización segura para subprocesos, como en los mutex . Sin embargo, un XCHG suele ser la forma más rápida de intercambiar dos palabras del tamaño de una máquina que residen en los registros . El cambio de nombre de registros también se puede utilizar para intercambiar registros de manera eficiente.
Ejecución paralela
Con el advenimiento de la canalización de instrucciones en las computadoras modernas y los procesadores de múltiples núcleos que facilitan la computación en paralelo , se pueden realizar dos o más operaciones a la vez. Esto puede acelerar el intercambio utilizando variables temporales y darle una ventaja sobre otros algoritmos. Por ejemplo, el algoritmo de intercambio XOR requiere la ejecución secuencial de tres instrucciones. Sin embargo, al usar dos registros temporales, dos procesadores que se ejecutan en paralelo pueden intercambiar dos variables en dos ciclos de reloj:
Paso 1 Procesador 1: temp_1: = X Procesador 2: temp_2: = YPaso 2 Procesador 1: X: = temp_2 Procesador 2: Y: = temp_1
Esto usa menos instrucciones; pero pueden estar en uso otros registros temporales y se necesitan cuatro instrucciones en lugar de tres. En cualquier caso, en la práctica esto no podría implementarse en procesadores separados, ya que viola las condiciones de Bernstein para la computación en paralelo. No sería factible mantener los procesadores lo suficientemente sincronizados entre sí para que este intercambio tuviera una ventaja significativa sobre las versiones tradicionales. Sin embargo, se puede utilizar para optimizar el intercambio de un solo procesador con varias unidades de carga / almacenamiento.
Referencias
- ^ [1]