Alcune osservazioni sull’algoritmo di copertura di un segmento
Sembra che oramai si sia instaurata una sorta di simbiosi tra questo blog e quello di Eineki; questo articolo infatti trae spunto dal suo ultimo golf programming contest e dai due algoritmi che ho analizzato come candidati alla soluzione.
Il problema da risolvere è abbastanza intuitivo; dato un set di segmenti identificati da coppie di interi [inizio, fine] bisogna fondere tra loro i segmenti che si sovrappongono.
Primo Algoritmo:
La mia prima idea (anche se alcuni molti credits vanno a Niji) è stata quella di spostare ad uno ad uno i segmenti dal set di input a quello di output; durante questa procedura ogni segmento che si sovrappone ai rimanenti del set di input viene fuso ed il risultato spostato in output. Alla fine di un intero ciclo di spostamento nel set di output trovano posto un numero di segmenti minore o uguale a quelli presenti nel set di input a seconda del numero di fusioni.
Con un numero di segmenti minore rispetto a quello del set di input l’algortimo procede ad un nuovo ciclo di spostamento, se invece il numero dei segmenti è lo stesso allora significa che non vi sono più fusioni da effettuare e che quindi quanto contenuto in output rappresenta il risultato definitivo.
Questo algoritmo, che in un primo momento mi era sembrato di una complessità non riducibile, si è invece rivelato computazionalmente molto più impegnativo del secondo, del quale ho tentato anche un implementazione in Erlang.
Secondo Algoritmo:
La differenza principale di questa procedura (per la quale devo ringraziare Fabio) rispetto alla precedente è l’introduzione di un elemento di ordinamento che riassetta il set di input organizzando i segmenti come se fossero poggiati su di una immaginaria linea retta. A questo punto avendo tutti i segmenti ordinati (supponiamo che [A,B,C,D] siano 4 segmenti) è possibile confrontarli a coppie di due ( A e B, B e C, ecc..) fondendo la coppia quando necessario (se A e B si sovrappongono in B dovrà essere riportato il risultato della fusione tra i due).
L’implementazione che ho sviluppato è lungi dall’essere perfetta in quanto denota tutte le mie carenze nei confronti di Erlang, del quale stò cercando di apprendere i segreti, ma dovrebbe essere sufficiente a rendere l’idea:
-module(coverage).
-export([sort_cover/1]).
-import(lists,[sort/2,foldl/3]).
sort_cover(A) -> lists:foldl(
fun([E1,E2],[[H1,H2]|T]) ->
if
((E1 >= H1) and (E1 =< H2)) or ((E2 >= H1) and (E2 =< H2)) -> [[
if
E1 >= H1 -> H1;
true -> E1
end,
if
E2 >= H2 -> E2;
true -> H2
end
]|T];
true -> [[E1,E2]|[[H1,H2]] ++ T]
end
end, [[-1,-1]],
lists:sort( fun([K,I],[L,M]) -> (K < L) or ((K >= L) and (I =< M)) end, A)).
La caratteristica migliore di questo algoritmo è sicuramente la sua bassa complessità: O(nlogn); l'operazione computazionalmente più costosa è infatti il sort.
Tags: Copertura di un segmento, Erlang