featured image

Tras ver la definición de la función global:random_exit_name/3 la cual sugiere la eliminación de un proceso y la asignación de otro a un nombre para evitar colisiones, ¿qué pasaría si la elección estuviese en más de dos elementos?

Es decir, si tenemos una lista con 10 elementos, por ejemplo, y queremos aplicar ese algoritmo de elección podríamos emplear lists:foldl/3 para poner a cada elemento a competir y obtener así el ganador:

Competitors = lists:seq(1, 10),
lists:foldl(fun(NewCandidate, OldWinner) ->
    case rand:uniform(2) of
        1 -> NewCandidate;
        2 -> OldWinner
    end
end, hd(Competitors), tl(Competitors)).

Tras ejecutar el código varias veces nos encontramos que casi siempre ganan los números más altos, es muy difícil que el número 1 llegue a ganar y sacando estadísticas vemos…

01  02  03  04  05  06  07  08  09  10
 1   1   0   0   0   0   0   0   0   0
 2   2   1   0   0   0   0   0   0   0
 3   3   2   1   0   0   0   0   0   0
 4   4   3   2   1   0   0   0   0   0
 5   5   4   3   2   1   0   0   0   0
 6   6   5   4   3   2   1   0   0   0
 7   7   6   5   4   3   2   1   0   0
 8   8   7   6   5   4   3   2   1   0
 9   9   8   7   6   5   4   3   2   1

El competidor con el número 1 tendría que realizar 9 enfrentamientos para poder llegar a ser ganador. Cada enfrentamiento sitúa su estadística de ganar en 50%. La estadística para 9 enfrentamientos sería 0,1953%. Mientras que el número 10 tiene 50% de probabilidades de ser ganador.

Si queremos ser justos con el pobre 1, habría que hacer un esquema de competición justa. Por ejemplo, limitamos los competidores a 8 (para tener potencia de 2), y partimos la lista en 2, enfrentamos a los de una lista con los otros y obtenemos a los ganadores, y repetimos el proceso hasta que solo quede un ganador. El código sería:

Competitors = lists:seq(1,8),
Select = fun(A, B) ->
            io:format("fight ~p vs ~p~n", [A, B]),
            case rand:uniform(2) of
                1 -> A;
                2 -> B
            end
        end,
Fight = fun Fight([A,B]) ->
                Select(A, B);
            Fight(List) ->
                {List1, List2} = lists:split(length(List) div 2, List),
                ZipList = lists:zip(List1, List2),
                Winners = [ Select(A, B) || {A, B} <- ZipList ],
                io:format("winners => ~p~n", [Winners]),
                Fight(Winners)
        end,
Fight(Competitors).

Este esquema ya es más justo y nos deja la ejecución…

> Fight(Competitors).
fight 1 vs 5
fight 2 vs 6
fight 3 vs 7
fight 4 vs 8
winners => [1,2,3,4]
fight 1 vs 3
fight 2 vs 4
winners => [1,2]
fight 1 vs 2
1

Ahora el 1 sí tiene más opciones de ganar. La probabilidad con 8 competidores es de 12,5% para cada uno de ellos.

Pero como estamos en el más difícil todavía… vamos a aprovechar la estructura que nos otorga Erlang y vamos a realizar el algoritmo en forma de servidores con el esquema map-reduce. Tendremos un servidor para recibir las listas y resultados. El servidor se encargará de obtener la lista partirla y generar un proceso hijo para cada una de las particiones. Los procesos hijos enviarán resultados y el servidor se encargará de obtener los resultados en una lista y volver a realizar el mismo proceso hasta recibir un solo resultado:

SendWinner = fun(Parent, A, B) ->
    case rand:uniform(2) of
        1 -> Parent ! {winner, A};
        2 -> Parent ! {winner, B}
    end
end,
SplitList = fun(List) ->
    M = length(List) div 2,
    lists:split(M, List)
end,
SplitAndSelect = fun Solve(Parent, [A, B]) ->
                        io:format("fight ~p vs ~p~n", [A, B]),
                        SendWinner(Parent, A, B);
                     Solve(Parent, Elements) ->
                        {List1, List2} = SplitList(Elements),
                        spawn_link(fun() -> Solve(Parent, List1) end),
                        Solve(Parent, List2)
                 end,
Loop = fun Loop(Data) ->
    receive
        {list, Elements} ->
            Parent = self(),
            spawn_link(fun() ->
                SplitAndSelect(Parent, Elements)
            end),
            Loop([]);
        {winner, D} ->
            Loop([D|Data])
    after 500 ->
        case length(Data) =:= 1 of
            true ->
                io:format("winner is ~p~n", Data);
            false ->
                io:format("winners are ~p~n", [Data]),
                self() ! {list, Data},
                Loop([])
        end
    end
end,
Elements = lists:seq(1, 8),
Init = fun() -> self() ! {list, Elements}, Loop([]) end.
Init().

He querido que el código sea a modo de expresión para poder ejecutarlo directamente en la consola. Para ejecutarlo una y otra vez solo nos hace falta la última línea:

Init().
fight 3 vs 4
fight 7 vs 8
fight 1 vs 2
fight 5 vs 6
winners are [5,1,7,4]
fight 7 vs 4
fight 5 vs 1
winners are [1,7]
fight 1 vs 7
winner is 1
ok

Init().
fight 3 vs 4
fight 7 vs 8
fight 1 vs 2
fight 5 vs 6
winners are [6,2,7,3]
fight 7 vs 3
fight 6 vs 2
winners are [6,3]
fight 6 vs 3
winner is 6
ok

Podemos ver una salida por pantalla muy similar a nuestro ejemplo secuencial anterior.

¿Te animas a reescribir el código en modo declarativo dentro de módulos en Erlang? ¿Prefieres ver el código cómo quedaría con Elixir? ¿En lugar de tiempo emplearías otro método de sincronización?, ¡Déjanos tu comentario!