Código fuente

Intercambiar valores sin variable intermedia

No deja de ser una curiosidad programática un intercambio que se lleve a cabo sin emplear una variable intermedia, que es como suele hacerse y enseñarse en cursos introductorios a la programación. A muchos ni siquiera se les ocurre que sea posible.

¿Por qué necesitaríamos hacer un intercambio en primer lugar, en vez de codificarlo en forma «dura»? Será necesario en cualquier situación donde el intercambio se encuentre condicionado, de forma que no podamos simplemente «cablearlo» en dicho programa.

Con los recursos actuales de memoria, ¿no es caprichoso hacer tal cosa? En realidad sí lo es, aunque existen entornos donde estos son tan escasos que podría valer la pena su uso. Un ejemplo de ellos son los microcontroladores.

Una vez encontrada la justificación, pongamos manos a la obra.

La forma aritmética

La más «primitiva» manera de conseguirlo es la aritmética. En ella sumamos el valor de ambas variables y lo asignamos a una de ellas, con ese nuevo valor y el de la variable restante hacemos operaciones para extraer los valores originales y reasignarlos. Expresado en Python es la siguiente:

# INICIALIZAMOS LAS VARIABLES
a = 20
b = 4

# EL INTERCAMBIO
a += b     # a + b vale 24
b = a - b  # a - b vale 20, b toma su valor final
a -= b     # a - b vale 4, a toma su valor final

# IMPRESIÓN DEL RESULTADO
print("A: ", a, "B: ", b)

Limitaciones u objeciones:

  • Solo tiene sentido en variables numéricas.
  • En general, la suma no puede superar el valor máximo (o ser menor al mínimo) del rango correspondiente al tipo de variable empleado, de lo contrario existiría un overflow (o underflow). En el lenguaje del ejemplo (Python 3) esto no es problema para los enteros, ya que valores por encima (o debajo) del rango normal se convierten automáticamente en un tipo de dato más lento que no impone un límite.
  • En variables de punto flotante puede dar resultados erróneos si la diferencia exacta entre a y b no puede ser expresada en términos de un flotante del mismo tipo.

Soluciones y generalizaciones posibles:

  • Si asumimos que el valor codificado por la secuencia de bits de las variables es un número entero positivo, y aplicamos sumas y restas módulo n (donde n es el valor máximo del rango de esa nueva forma de codificación), el intercambio podría realizarse sin problemas, siempre que las variables sean del mismo tamaño en bits. No queda claro que esto resulte práctico en la gran mayoría de los lenguajes, o que no se usen implícitamente variables extra (que es lo que se pretende evitar).

La forma lógica

Esta es una forma más sofisticada de realizar el intercambio, y también mucho más «limpia». El truco consiste en usar el operador lógico XOR a nivel de bits.

El operador mencionado se define como:

xyx XOR y
000
011
101
110

Su implementación en Python quedaría:

# INICIALIZAMOS LAS VARIABLES
a = 20  # a queda expresado como 10100
b = 4   # b queda expresado como 00100

# EL INTERCAMBIO
a ^= b  # a XOR b vale 10000 (16)
b ^= a  # a XOR b vale 10100 (20), b toma su valor final
a ^= b  # a XOR b vale 00100 (4), a toma su valor final

# IMPRESIÓN DEL RESULTADO
print("A: ", a, "B: ", b)

Limitaciones u objeciones:

  • Las variables deben tener la misma longitud en bits.
  • Lo usual es que solo se pueda aplicar a variables de tipo entero.

Atajos de lenguaje

Algunos lenguajes tienen atajos que permiten realizar un intercambio sin variable intermedia de forma nativa. Un ejemplo es el mismo Python, o incluso Ruby. En ambos casos podemos utilizar su capacidad para realizar asignaciones múltiples. En el primero de los lenguajes mencionados esto queda así:

# INICIALIZAMOS LAS VARIABLES
a = 20
b = 4

# EL INTERCAMBIO
a, b = b, a

# IMPRESIÓN DEL RESULTADO
print("A: ", a, "B: ", b)

En este caso particular el intercambio es muy eficiente, ya que Python simplemente cambia el objeto al que apuntan los nombres a y b, respectivamente.

¿Es eficiente?

¿Cuál de los métodos mencionados anteriormente es más eficiente? Es difícil saber, y depende mucho del lenguaje y tipo de dato a intercambiar. A pesar de ello, me he decidido a hacer una pequeña exploración preliminar sobre tal cuestión en el lenguaje favorito de esta entrada: Python.

Se ha realizado el intercambio un millón de veces para cada uno de los métodos mencionados anteriormente y el tradicional de variable intermedia. El código utilizado para hacer la prueba es el siguiente:

from timeit import timeit

# PREPARACIÓN
setup = """a = 20
b = 4"""

tradicional = """temp = a
a = b
b = temp"""

aritmetico = """a += b
b = a - b
a -= b"""

logico = """a ^= b
b ^= a
a ^= b"""

atajo = """a, b = b, a"""

# EJECUCIÓN
r_t = timeit(tradicional, setup=setup, number=1000000)
r_a = timeit(aritmetico, setup=setup, number=1000000)
r_l = timeit(logico, setup=setup, number=1000000)
r_j = timeit(atajo, setup=setup, number=1000000)

# IMPRESIÓN DEL RESULTADO
print("Tradicional (sec): ", r_t,
      "\nAritmético (sec): ", r_a,
      "\nLógico (sec): ", r_l,
      "\nAtajo (sec): ", r_j)

La salida, que especifica el tiempo utilizado para realizar los intercambios, fue:

Tradicional (sec):  0.05924501300250995 
Aritmético (sec):  0.10236713199992664 
Lógico (sec):  0.20969993399921805 
Atajo (sec):  0.031912190999719314

Como era de esperarse, el sistema por asignación múltiple fue el más rápido, sorprendiendo la lentitud del sistema basado en el XOR. Pero no debe tomarse muy en serio ni debe generalizarse este resultado.

Conclusiones

Aunque los recursos actuales de memoria hacen casi innecesario el uso de técnicas parecidas a las propuestas, no deja de ser un recurso útil bajo condiciones muy específicas. Eso sí, no las usuales de un programador típico. También, y lo más importante, el ejercicio sirve para encender nuestra imaginación y saber que este tipo de intercambio es posible.

Javier
Javier

Maestro en Ciencias de la Computación (UNAM). Durante mucho tiempo interesado en la difusión del pensamiento crítico, la ciencia y el escepticismo. Estudioso de la inteligencia artificial, ciencias cognitivas y temas afines.

Artículos: 54

2 comentarios

  1. No sé Python, pero… ¿el Atajo no es lo que llaman «azúcar de sintaxis» para el tradicional con variable temporal?, es decir, que con la notación de comas no estará Python haciendo trampa y con variables internas hace el cambio.

    • Si es «azucar de sintáxis» como dices. En realidad Python es de tan alto nivel que seguramente cientos de pequeñas variables aparecen y desaparecen tras bambalinas por ahí en cada instrucción aparentemente sencilla (pensemos, por ejemplo, en el recolector de basura invisible al programador).

      Pero la «asignación múltiple» que se ve en el ejemplo es, en realidad, un rollo más complicado: escribir algo como «a, b» es crear una tupla (una estructura de datos de Python) con los objetos apuntados por a y b como elementos. Lo que realmente se está haciendo en la asignación mostrada es crear una tupla, que se asigna a otra con los mismos elementos intercambiados. Las tuplas «origen» y «destino» desaparecen, quedando las etiquetas originales (a, b) con la alteración deseada. Es decir, apuntando al objeto deseado. Al final no se creó ni copió objeto alguno (a parte de las tuplas), tan solo se hace que los nombres a y b apunten al objeto que tenía la otra.

      En Python todo es objeto, donde los nombres y objetos a los que apuntan son de alguna forma «independientes». Concluyendo: si es trampa.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *