Реализации алгоритмов/Мультиметод

Мультиме́тод (англ. multimethod) или мно́жественная диспетчериза́ция (англ. multiple dispatch) — механизм, позволяющий выбрать одну из нескольких функций в зависимости от динамических типов или значений аргументов.

Common Lisp

В языке с поддержкой мультиметодов, таком, как Common Lisp, код выглядел бы вот так:

(defgeneric collide (x y))

(defmethod collide ((x asteroid) (y asteroid))
  ;;астероид сталкивается с астероидом
  )

(defmethod collide ((x asteroid) (y spaceship))
  ;;астероид сталкивается с космическим кораблем
  )

(defmethod collide ((x spaceship) (y asteroid))
  ;;космический корабль сталкивается с астероидом
  )

(defmethod collide ((x spaceship) (y spaceship))
  ;;космический корабль сталкивается с космическим кораблем
  )

C#

Реализация на C# 4.0, с использованием dynamic-типов:

class Program
{
  class Thing { }
  class Asteroid : Thing { }
  class Spaceship : Thing { }

  static void CollideWithImpl(Asteroid x, Asteroid y) 
  {
    // астероид сталкивается с астероидом
  }

  static void CollideWithImpl(Asteroid x, Spaceship y) 
  {
    // астероид сталкивается с космическим кораблем
  }

  static void CollideWithImpl(Spaceship x, Asteroid y) 
  {
    // космический корабль сталкивается с астероидом
  }

  static void CollideWithImpl(Spaceship x, Spaceship y) 
  {
    // космический корабль сталкивается с космическим кораблем
  }

  static void CollideWith(Thing x, Thing y)
  {
    dynamic a = x;
    dynamic b = y;
    CollideWithImpl(a, b);
  }

  static void Main(string[] args)
  {
    var asteroid = new Asteroid();
    var spaceship = new Spaceship();
    CollideWith(asteroid, spaceship);
    CollideWith(spaceship, spaceship);
  }
}

В данном случае, естественно, следует отличать мультиметоды от статической перегрузки, так как, в отличие от последней, диспетчеризация происходит в рантайме.

В объектно-ориентированных языках, не поддерживающих синтаксис мультиметодов, множественную диспетчеризацию можно реализовать посредством виртуальных методов.

Пример двойной диспетчеризации на языке Java

public abstract class Thing {
    public abstract void collide(Thing thing);

    protected abstract void collideWithAsteroid(Asteroid asteroid);
    protected abstract void collideWithSpaceship(Spaceship spaceship);
}

public class Asteroid extends Thing {
    @Override
    public void collide(Thing thing) {
        // Вторая диспетчеризация
        thing.collideWithAsteroid(this);
    }

    @Override
    protected void collideWithAsteroid(Asteroid asteroid) {
        // астероид сталкивается с астероидом
    }

    @Override
    protected void collideWithSpaceship(Spaceship spaceship) {
        // космический корабль сталкивается с астероидом
    }
}

public class Spaceship extends Thing {
    @Override
    public void collide(Thing thing) {
        // Вторая диспетчеризация
        thing.collideWithSpaceship(this);
    }

    @Override
    protected void collideWithAsteroid(Asteroid asteroid) {
        // астероид сталкивается с космическим кораблем
    }

    @Override
    protected void collideWithSpaceship(Spaceship spaceship) {
        // космический корабль сталкивается с космическим кораблем
    }
}

public class Main {
    public static void main(String[] args) {
        Asteroid asteroid = new Asteroid();
        Spaceship spaceship = new Spaceship();
        asteroid.collide(spaceship);
        spaceship.collide(spaceship);
    }
}

C++

/* Пример, использующий сравнение типов во время выполнения */
void Asteroid::collide_with(Thing * other) {
  Asteroid * other_asteroid = dynamic_cast<Asteroid*>(other);
  if (other_asteroid) {
      // deal with asteroid hitting asteroid
      return;
  }
  Spaceship * other_spaceship = dynamic_cast<Spaceship*>(other);
  if (other_spaceship) {
      // deal with asteroid hitting spaceship
      return;
  }
}
void Spaceship::collide_with(Thing * other) {
  Asteroid * other_asteroid = dynamic_cast<Asteroid*>(other);
  if (other_asteroid) {
      // deal with spaceship hitting asteroid
      return;
  }
  Spaceship * other_spaceship = dynamic_cast<Spaceship*>(other);
  if (other_spaceship) {
      // deal with spaceship hitting spaceship
      return;
  }
}

или:

/* Пример, использующий полиморфизм и перегрузку методов */
void Asteroid::collide_with(Thing * other) {
  other->collide_with(this);
}
void Asteroid::collide_with(Asteroid * other) {
  // deal with asteroid hitting asteroid
}
void Asteroid::collide_with(Spaceship * other) {
  // deal with asteroid hitting spaceship
}
void Spaceship::collide_with(Thing * other) {
  other->collide_with(this);
}
void Spaceship::collide_with(Spaceship * other) {
  // deal with spaceship hitting spaceship
}
void Spaceship::collide_with(Asteroid * other) {
  // deal with spaceship hitting asteroid
}

Python

С помощью модуля multimethods.py (из Gnosis Utils):

from multimethods import Dispatch

class Asteroid(object): pass
class Spaceship(object): pass

def asteroid_with_spaceship(a1, s1): print "A-><-S"
def asteroid_with_asteroid(a1, a2): print "A-><-A"
def spaceship_with_spaceship(s1, s2): print "S-><-S"

collide = Dispatch()
collide.add_rule((Asteroid, Spaceship), asteroid_with_spaceship)
collide.add_rule((Asteroid, Asteroid), asteroid_with_asteroid)
collide.add_rule((Spaceship, Spaceship), spaceship_with_spaceship)
collide.add_rule((Spaceship, Asteroid), lambda x,y: asteroid_with_spaceship(y,x))

a, s1, s2 = Asteroid(), Spaceship(), Spaceship()

collision1 = collide(a, s1)[0]
collision2 = collide(s1, s2)[0]

С помощью модуля multipledispatch (https://pypi.python.org/pypi/multipledispatch/) получается намного более простой синтаксис:

from multipledispatch import dispatch

class Asteroid(object): pass
class Spaceship(object): pass

@dispatch(Asteroid, Spaceship)
def collide(a1, s1): print "A-><-S"

@dispatch(Asteroid, Asteroid)
def collide(a1, a2): print "A-><-A"

@dispatch(Spaceship, Spaceship)
def collide(s1, s2): print "S-><-S"

a, s1, s2 = Asteroid(), Spaceship(), Spaceship()

collision1 = collide(a, s1)
collision2 = collide(s1, s2)

Ruby

С помощью модуля Vlx-multi:

require 'vlx_multi'

class Asteroid
end


class Spaceship
end

vlxm(:collide, Asteroid, Asteroid) do |_1,_2|
  puts 'A-><-A'
end


vlxm(:collide, Asteroid, Spaceship) do |_1,_2|
  puts 'A-><-S'
end

vlxm(:collide, Spaceship, Asteroid ) do |_1,_2|
  puts 'S-><-A'
end

vlxm(:collide, Spaceship, Spaceship ) do |_1,_2|
  puts 'S-><-S'
end


s = Spaceship.new
a = Asteroid.new

collide(a,s)
collide(s,s)
collide(s,a)
collide(a,a)