[Vari] Contest 16: Intervalli

[gugoXX]

Uno facile e non troppo verboso, giusto per pensare e per vedere l'approccio.
Sia dato un lungo elenco di intervalli della retta reale.

-4.5 +3.2
+2.8 +7.15
-7.3 -9.15

Le coordinate di ciascun intervallo possono anche essere "invertite", ovvero non e' assicurato che il primo valore sia sempre inferiore al secondo.

Si noti come ci possano essere delle SOVRAPPOSIZIONI. In questo esempio il primo e il secondo intervallo sono parzialmente sovrapposti.

Si vuole calcolare la lunghezza totale del dominio coperto, contando le sovrapposizioni una e una sola volta.
Si trascurino gli arrotondamenti dovuti a precisione macchina, e dove possibile si lavori con la struttura piu' precisa possibile,
tenendo conto che l'input sara' contenibile senza errori in un IEEE754 da 64bit (in C il double)

In questo esempio il risultato dovrebbe essere 13.5

Primo File, giusto per tastare il terreno.
http://www.usaupload.net/d/ze7gn00x87b

[Vincenzo1968]

E 'ndirindinghete!!!

C'è già un contest 15(Sudoku):

Contest 1 (http://www.hwupgrade.it/forum/showthread.php?t=1784948)

Contest 2 (http://www.hwupgrade.it/forum/showthread.php?t=1785752)

Contest 3 (http://www.hwupgrade.it/forum/showthread.php?t=1787500)

Contest 4 (http://www.hwupgrade.it/forum/showthread.php?t=1791293)

Contest 5 (http://www.hwupgrade.it/forum/showthread.php?t=1799059)

Contest 6 (http://www.hwupgrade.it/forum/showthread.php?t=1850150)

Contest 7 (http://www.hwupgrade.it/forum/showthread.php?t=1839674)

Proposta (http://www.hwupgrade.it/forum/showthread.php?t=1872715)

Contest 8 (http://www.hwupgrade.it/forum/showthread.php?t=1877648)

Contest 9 (http://www.hwupgrade.it/forum/showthread.php?t=1882576)

Contest 10 (http://www.hwupgrade.it/forum/showthread.php?t=1883750)

Contest 11 (http://www.hwupgrade.it/forum/showthread.php?t=1884158)

Contest 12 (http://www.hwupgrade.it/forum/showthread.php?t=1890800)

Contest 13 (http://www.hwupgrade.it/forum/showthread.php?t=1981159)

Contest 14 (http://www.hwupgrade.it/forum/showthread.php?t=1982858)

Contest 15 (http://www.hwupgrade.it/forum/showthread.php?t=1995326)

:bimbo:

[gugoXX]

Fatto fatto :D:D
Avevo copiaincollato e non avevo modificato.

[Vincenzo1968]

Senti maaaaaaaaaaaaa

un piccolo chiarimento per chi, come me, ne sa poco e niente di matematica?
Che significa lunghezza totale del dominio coperto? Come viene fuori quel 13.5?

Grazie :)

:bimbo:

[gugoXX]

Dunque.
Sei prendi un intervallo tipo
3.2 --> 7.5
questo e' un intervallo della retta reale, che parte dal punto 3.2 e arriva fino a 7.5
La lunghezza di tale intervallo e' 4.3

Un po' come dire: Ho dipinto di bianco la strada a partire dal Kilometro 3.2 fino al Kilometro 7.5
La domanda sarebbe quindi: Quanti Kilometri di strada ho coperto di bianco? 4.3Km finora, appunto.

Aggiungiamo un altro intervallo, quello
10.4 --> 12.7
e la cui lunghezza e' 2.3

E poi un altro ancora, da
11.9 --> 12.9, la cui lunghezza e' 1.0

Potrebbe venire da dire che la lunghezza totale coperta sia da
4.3 + 2.3 + 1.0 = 7.6

E invece no.
Questo ultimo intervallo e' parzialmente sovrapposto all'intervallo precedente. Per un pezzo di strada ho semplicemente ripittato un pochino, ma era gia' bianca, non conta 2 volte.

Riusciamo a coprire quindi tutto il primo
3.2 --> 7.5
poi il secondo
10.4 --> 12.7
e poi del terzo aggiungiamo solo una piccola fettina
12.7 --> 12.9, perche' la prima parte del terzo era gia' coperta precedentemente.
Abbiamo quindi un totale di 4.3 + 2.3 + 0.2 = 6.8

E' OK?


Nell'esempio abbiamo anche coordinate di partenza negative. Un po' come mettere casa mia al centro di una lunghissima strada diritta, e dire che se vado a sinistra ho coordinate negative e a destra coordinate positive.
Per l'esempio dato abbiamo:
-4.5 --> +3.2 Lunghezza = 7.7
Ovvero sono partito a dipingere 4.5KM a sinistra di casa mia, e ho finito 3.2KM a destra di casa mia.

Poi
+2.8 --> +7.15 E gia' qui sovrappoiniamo, quindi vale solo come se fosse da
+3.2 --> 7.15 = 3.95

E infine
-7.3 --> -9.15, ovvero parto da 7.3KM a sinistra e proseguo fino a 9.15 KM a sinistra, senza sovrapporre niente quindi.
La lunghezza conta tutta, ovvero 1.85KM

Totale 7.7 + 3.95 + 1.85 = 13.5

[banryu79]

Così:
[-4.5 +3.2]
[+2.8 +7.15]
rappresentano due intervalli che si sovvrapongono parzialmente quindi prendiamo l'intervallo ricavato dalla loro "unione":
[-4.5 +7.15]

L'altro intervallo specificato:
[-7.3 -9.15]
non si sovrappone a nessun altro intervallo, quindi lo consideriamo di per se.

Ora la lunghezza totale del dominio sarà data dalla somma delle singole lunghezze degli intervalli, a loro volta date dal valore assoluto del risultato della sottrazione del valore minore dal valore maggiore:
[-4.5 +7.15] -> +7.15 - -4.5 -> 11.65 -> abs -> 11.65
e
[-7.3 -9.15] -> -9.15 - -7.3 -> -1.85 -> abs -> 1.85

Lunghezza dominio coperto dagli intervalli: 11.65 + 1.85 = 13.5

Giusto Gugo?

[gugoXX]

Si, esatto.
Figuratevelo come le istruzioni per pittare di bianco la strada, e la domanda appunto su quanta strada totale avete alla fine pittato di bianco.

[Vincenzo1968]

Grazie mille a entrambi per le spiegazioni. Ora è tutto chiaro :)

Un'ultima domanda: i tempi di caricamento dal file non vanno conteggiati, giusto?

[gugoXX]

Grazie mille a entrambi per le spiegazioni. Ora è tutto chiaro :)

Un'ultima domanda: i tempi di caricamento dal file non vanno conteggiati, giusto?

Direi di no.
Certo che se mentre si legge si fa anche altro allora occorre contare, ma se si legge solo il file per poi parsarlo allora va bene tenere i tempi della lettura fuori.

[PGI-Bis]

Per la serie "nutro una grande fiducia in quel che ho scritto", a chi viene

1235792.2454819013


con il file di prova?

[banryu79]

Per la serie "nutro una grande fiducia in quel che ho scritto", a chi viene

1235792.2454819013


con il file di prova?
Sono ancora impelagato in ufficio; questo contest però mi piace e me lo risolverò nel wend, quindi niente soluzione ancora, per fare confronti

Però potresti scriverti uno unit test (:asd: ) dandogli in pasto un file di input "banale" e vedere se i conti tornano

[gugoXX]

Per la serie "nutro una grande fiducia in quel che ho scritto", a chi viene

1235792.2454819013


con il file di prova?

a me viene 380404.063114735
Ma potrei avere sbagliato, ho fatto di corsa.
Magari ho semplicemente sbagliato file, dato che da rospo non ho tenuto il seed del generatore... non potro' mai piu' riprodurlo.
Riscarico e controllo.

[^TiGeRShArK^]

minchia siamo messi bene :asd:
a me viene 299085,567040739
:p

[Vincenzo1968]

Io ho quest'altro risultato:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzione.jpg

Qual è quello giusto?

:bimbo:

[^TiGeRShArK^]

miii passerà alla storia come il contest con il maggior numero di risultati diversi :asd:

[Vincenzo1968]

Ho provato un piccolo file con i dati dell'esempio iniziale di Gugo:


-4.5 3.2
2.8 7.15
-7.3 -9.15


e il risultato, in questo caso, è corretto: 13.5

Il codice sorgente, in C, si può scaricare da qui (http://www.guidealgoritmi.it/public/Contest16.zip).

[^TiGeRShArK^]

quello l'avevo provato pure io ovviamente :p
cmq ho corretto un potenziale piccolo bug, ma il risultato mi esce sempre quello... :boh:
o mi sfugge ancora qualcosa o c'è qualcos'altro che mi sfugge :asd:

EDIT: Minchia.. come al solito è sintetico il tuo codice :p

[Vincenzo1968]

quello l'avevo provato pure io ovviamente :p
cmq ho corretto un potenziale piccolo bug, ma il risultato mi esce sempre quello... :boh:
o mi sfugge ancora qualcosa o c'è qualcos'altro che mi sfugge :asd:


E pure io ho corretto un bug potenziale, ma il risultato è sempre quello. Mah :confused:
Se Gugo non dà la soluzione entro oggi, sambenito per un anno intero :bimbo:


EDIT: Minchia.. come al solito è sintetico il tuo codice :p

:bimbo:

[gugoXX]

Purtroppo ho il codice in ufficio, e ci tornero' solo lunedi' mattina.
Aspettiamo qualcun altro... se troviamo un altro che da un risultato uguale a qualcuno di noi allora e' piu' probabile che sia quello giusto :D:D

Peraltro, giusto per pensare, cosa vi viene fuori da questo, valido?

5 10
16 22
18 9


(E vai di Unit test)

[^TiGeRShArK^]

17....

[rеpne scasb]

■

[^TiGeRShArK^]

oh finalmente due uguali :p

[gugoXX]

Ieee, ci siamo allora, e' il risultato.
Lo do 2 su 5 almeno :D:D

[rеpne scasb]

■

[^TiGeRShArK^]

uff...
sistemato pure io....
avevo fatto il banalissimo errore di mettere l'assegnazione dopo l'if esterno.. :muro:

string[] content = File.ReadAllLines("RealLine.txt");
Stopwatch watch = Stopwatch.StartNew();
char[] separator = new char[] { ' ' };
var orderedIntervals = (from c in content
let tokens = c.Split(separator, StringSplitOptions.RemoveEmptyEntries)
let first = double.Parse(tokens[0])
let second = double.Parse(tokens[1])
select new double[] {
first <= second ? first : second,
first <= second ? second : first
}).OrderBy(e => e[0]).ToArray();

double previousRight = double.NegativeInfinity;
double total = 0.0;
foreach (var interval in orderedIntervals)
{
double left = interval[0];
double right = interval[1];
if (previousRight <= right) {
if (left > previousRight)
{
total += right - left;
}
else
{
total += right - previousRight;
}
previousRight = right;
}
}
watch.Stop();
Console.WriteLine("Il totale è {0}, calcolato in {1}ms", total, watch.ElapsedMilliseconds);
Console.ReadLine();

L'algoritmo che ho usato dovrebbe essere abbastanza self-explanatory :p
l'output è:

Il totale è 380404,063114734, calcolato in 41ms

sul solito windows xp virtualizzato tramite parallels su un macbook pro a 2.4 ghz :p

[Vincenzo1968]

17 pure a me :bimbo:

Per il momento ritiro il mio codice perché mi sono accorto che c'è un bug e il risultato, sul file grosso, non è corretto :bimbo:

[^TiGeRShArK^]

Come algoritmo ho utilizzato un OR logico su numeri float, basandomi sul concetto che se ABS(A[i]-B[i])>K allora e' possibile quantizzare A[i] e B[i] con 'n' stati di lunghezza K. Di fatto ho trasformato dei float in interi, e ne ho fatto l'OR.

Tu che algoritmo hai utilizzato?
ehmm..
dopo aver sostituito CLK_TCK con CLOCKS_PER_SEC, che altrimenti mi dava errore in compilazione, il tuo codice mi va in segmentation fault.. :stordita:
Lo sto usando su Mac Os X Leopard 10.5.7 compilato con XCode....:fagiano:

[rеpne scasb]

■

[gugoXX]

Come algoritmo ho utilizzato un OR logico su numeri float, basandomi sul concetto che se ABS(A[i]-B[i])>K allora e' possibile quantizzare A[i] e B[i] con 'n' stati di lunghezza K. Di fatto ho trasformato dei float in interi, e ne ho fatto l'OR.

Tu che algoritmo hai utilizzato?

Ho mantenuto una lista di intervalli non sovrapposti, e ogni volta che devo valutare un nuovo intervallo cerco tutti i sovrapponibili, li estraggo, li fondo e inserisco il nuovo intervallo nella lista.
Per velocizzare la ricerca dei sovrapposti ho mantenuto 2 Indici, e con un paio di filtri e operazioni insiemistiche riduco l'insieme dei controlli.
Tra il dire e il fare c'e' di mezzo l'Italiano, dato che l'algoritmo in realta' sono una dozzina di righe abbastanza semplici.

[Vincenzo1968]

A me il codice di repne funziona perfettamente:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneRepne.jpg

La macchina è questa:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3


:bimbo:

[^TiGeRShArK^]

Tutto puo' essere. Ho scritto il codice in pochi minuti, e ci saranno sicuramente dei bachi. Allego l'eseguibile per Win32 che funziona sul mio PC, se interessa.
ok, questo va..
mi sa che il problema è che avevo cambiato i punti in virgole nel file originale perchè mi scaramellavo ad utilizzare il CultureInfo :asd:

ci mette 250ms circa sul mio....

[^TiGeRShArK^]

A me il codice di repne funziona perfettamente:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneRepne.jpg

La macchina è questa:



:bimbo:

mmm...
strano che sul mio xp virtualizzato sia così lento quello di repne.... :mbe:
puoi fare girare il mio codice sulla tua macchina per vedere quanto ci mette? :p

[gugoXX]

A me il codice di repne funziona perfettamente:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneRepne.jpg

La macchina è questa:



:bimbo:

Ma il tuo com'e'? L'hai aggiustato?

[Vincenzo1968]

Ma il tuo com'e'? L'hai aggiustato?

No, non l'ho ancora aggiustato. Sui due esempi piccoli il risultato è corretto; sul file grosso no. Evidentemente l'algoritmo non è corretto.

[Vincenzo1968]

mmm...
strano che sul mio xp virtualizzato sia così lento quello di repne.... :mbe:


Boh :confused: Può dipendere dalle ottimizzazioni del compilatore(utilizzo Visual Studio 2008)?


puoi fare girare il mio codice sulla tua macchina per vedere quanto ci mette? :p

Mi dà errore:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger.jpg

EDIT: Riguardando il tuo codice m'è venuto un dubbio atroce: si tratta, per caso, di C# e io sto tentando di eseguirlo con l'interprete Ruby?

EDIT 2: Si, è C# :bimbo: Il risultato(sostituendo, nel file, i punti con le virgole) è questo:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger3.jpg

[rеpne scasb]

■

[PGI-Bis]

Che strano. 17 e 13.5 si, il grosso no. Può essere un errore teorico?

Ho usato un albero BSP. I nodi contengono segmenti. L'idea è quella di prendere i segmenti in entrata e costruire un albero che abbia come valori segmenti che non si sovrappongono. Quando un segmento si sovrappone ad un altro:


------------------
++++++++++++++++


Genero tre segmenti non sovrapposti:


----------oooooooo+++++++++


il segmento centrale viene assegnato al nodo corrente, il segmento sinistro finisce nel sottoalbero sinistro, il segmento destro finisce nel sottoalbero destro.

Se il segmento inserito non si sovrappone a quello del nodo corrente allora il segmento finisce nel sottoalbero destro o sinistro, a seconda che il punto medio del nuovo segmento sia minore o maggiore del punto medio del segmento corrente.

Poichè i nodi dell'albero così costruito contengono segmenti disgiunti il risultato cercato è la somma delle estensioni dei segmenti contenuti in tutti i nodi.

Mi da 13.5, mi da 17 ma non mi da 380404,063114734. Mi perde per strada qualche segmento durante la lettura o è la parte teorica che non quaglia?

[^TiGeRShArK^]

Boh :confused: Può dipendere dalle ottimizzazioni del compilatore(utilizzo Visual Studio 2008)?



Mi dà errore:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger.jpg

EDIT: Riguardando il tuo codice m'è venuto un dubbio atroce: si tratta, per caso, di C# e io sto tentando di eseguirlo con l'interprete Ruby?

EDIT 2: Si, è C# :bimbo: Il risultato(sostituendo, nel file, i punti con le virgole) è questo:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger3.jpg

boh... io ho usato l'eseguibile che ha postato repne..
prova pure tu ad usare quello casomai e vedi se ci sono differenze.....

Si cmq era C#, anche se in effetti avrei dovuto specificarlo dato che nei contest ne uso uno a caso tra C#, python e ruby :asd:
Ad onor del vero questo avevo iniziato a farlo in F#, ma mi sono rotto subito perchè ancora non lo so usare per bene :p

[wingman87]

Che strano. 17 e 13.5 si, il grosso no. Può essere un errore teorico?

Ho usato un albero BSP. I nodi contengono segmenti. L'idea è quella di prendere i segmenti in entrata e costruire un albero che abbia come valori segmenti che non si sovrappongono. Quando un segmento si sovrappone ad un altro:


------------------
++++++++++++++++


Genero tre segmenti non sovrapposti:


----------oooooooo+++++++++


il segmento centrale viene assegnato al nodo corrente, il segmento sinistro finisce nel sottoalbero sinistro, il segmento destro finisce nel sottoalbero destro.

Se il segmento inserito non si sovrappone a quello del nodo corrente allora il segmento finisce nel sottoalbero destro o sinistro, a seconda che il punto medio del nuovo segmento sia minore o maggiore del punto medio del segmento corrente.

Poichè i nodi dell'albero così costruito contengono segmenti disgiunti il risultato cercato è la somma delle estensioni dei segmenti contenuti in tutti i nodi.

Mi da 13.5, mi da 17 ma non mi da 380404,063114734. Mi perde per strada qualche segmento durante la lettura o è la parte teorica che non quaglia?

Il ragionamento mi sembra corretto, siccome ti viene un valore più grande del risultato l'errore potrebbe essere o nella parte che controlla se due segmenti sono sovrapposti (perché se non rileva una sovrapposizione sommerà la stessa parte più di una volta) oppure nella somma degli intervalli (può essere un errore di distrazione).

[gugoXX]

uff...
sistemato pure io....
avevo fatto il banalissimo errore di mettere l'assegnazione dopo l'if esterno.. :muro:

string[] content = File.ReadAllLines("RealLine.txt");
Stopwatch watch = Stopwatch.StartNew();
char[] separator = new char[] { ' ' };
var orderedIntervals = (from c in content
let tokens = c.Split(separator, StringSplitOptions.RemoveEmptyEntries)
let first = double.Parse(tokens[0])
let second = double.Parse(tokens[1])
select new double[] {
first <= second ? first : second,
first <= second ? second : first
}).OrderBy(e => e[0]).ToArray();


Eheh. Mi fa piacere.
Ho creato un mostro...

[^TiGeRShArK^]

Eheh. Mi fa piacere.
Ho creato un mostro...

eh.. m'hai fatto 'nnamorà de linq :p

[gugoXX]

Che strano. 17 e 13.5 si, il grosso no. Può essere un errore teorico?

Ho usato un albero BSP. I nodi contengono segmenti. L'idea è quella di prendere i segmenti in entrata e costruire un albero che abbia come valori segmenti che non si sovrappongono. Quando un segmento si sovrappone ad un altro:


------------------
++++++++++++++++


Genero tre segmenti non sovrapposti:


----------oooooooo+++++++++


il segmento centrale viene assegnato al nodo corrente, il segmento sinistro finisce nel sottoalbero sinistro, il segmento destro finisce nel sottoalbero destro.

Se il segmento inserito non si sovrappone a quello del nodo corrente allora il segmento finisce nel sottoalbero destro o sinistro, a seconda che il punto medio del nuovo segmento sia minore o maggiore del punto medio del segmento corrente.

Poichè i nodi dell'albero così costruito contengono segmenti disgiunti il risultato cercato è la somma delle estensioni dei segmenti contenuti in tutti i nodi.

Mi da 13.5, mi da 17 ma non mi da 380404,063114734. Mi perde per strada qualche segmento durante la lettura o è la parte teorica che non quaglia?

Forse si inciampa quando ci sono 2 o piu' sovrapposizioni

-------- -----------
+++++++++++

[PGI-Bis]

Direi di no, i segmenti vengono aggiunti uno per volta, arriva il primo, arriva il secondo -> zac, scomposizione. Forse infilo qualcosa in sottoalbero destro quando dovrebbe andare in un sinistro o viceversa. A quel punto la sovrapposizione di segmenti va a ramengo. Comunque m'è venuto in mente un altro modo. Se anzichè separare i segmenti li unissimo quando si sovrappongono e tenessimo conto della somma delle estensioni man mano che i segmenti entrano nell'albero - con qualche sottrazione in caso di sovrapposizione con un segmento già calcolato ai fini di quella somma - si potrebbe ottenere il risultato senza dover visitare l'albero alla fine ma semplicemente costruendolo. Mo' provo.

[00pipp00]

Io la risolverei con un algoritmo rais (magari interfacciato con un filtro murm) e poi passerei i risultati a un operatore logico variable in modo da ordinarli senza sovrapposizioni, anche se bisogna stare attenti all'overlowd...

[Vincenzo1968]

Ahò,

ce so' riuscito:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzione2.jpg

La mia macchina:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3


:bimbo:

Edit: Dimenticavo il codice sorgente (http://www.guidealgoritmi.it/public/contest16.zip).

[Vincenzo1968]

Ohé,

compilato col Watcom (http://www.openwatcom.org/index.php/Main_Page) si dimezzano i tempi:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneWatcom.jpg

x Gugo: si potrebbe provare con un file più grosso(diciamo, di centomila righe)?

:bimbo:

[banryu79]

Eccomi, come promesso!
(Come qualcuno saprà non posso connettermi nei wend perchè non ho nessuna connessione a casina, solo dall'ufficio :Prrr:)

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Locale;
import java.util.Scanner;

/**
* Main class for Contest 16 on hwupgrade Forum - sezione Programmazione -
* @author Francesco Baro
*/
public class Main
{
public static void main(String argv[]) throws Exception
{
if (argv.length < 1)
{
throw new Exception("Bisogna indicare il file di input dei dati");
}

long startTime = System.nanoTime();
List<Intervallo> list = Parser.scanFrom(argv[0]);

Collections.sort(list);

Resolver r = new Resolver(list);
r.resolve();
double finalResult = r.getResult();
long estimatedTime = System.nanoTime() - startTime;

System.out.println("Result for input file: " + argv[0] + " is: " + finalResult);
System.out.println("performed " + r.recursionCounter + " recursive calls");
System.out.println("Time, in nanoseconds: " + estimatedTime);
}
}

/**
* rappresenta un intervallo nel dominio dei numeri reali rappresenti
* dal tipo double in Java
*/
class Intervallo implements Comparable<Intervallo>
{
double inizio, fine;

public Intervallo(double d1, double d2)
{
inizio = Math.min(d1, d2);
fine = Math.max(d1, d2);
}

double lenght()
{
return fine - inizio;
}

/**
* Unisce a questo Intervallo quello passato in ingresso. L'unione
* avviene solo se c'e'una sovvrapposizione tra i due Intervalli e
* trasforma questo Intervallo.
* Il presupposto è che questo Intervallo è minore o uguale a quello
* passato in ingresso. Per il criterio di ordinamento tra due Intervalli,
* vedere il metodo compareTo.
* @return true se c'e' stata un'unione, false altrimenti.
*/
boolean join(Intervallo other)
{
boolean joined = false;

if (fine >= other.inizio)
{
fine = Math.max(fine, other.fine);
joined = true;
}

return joined;
}

public int compareTo(Intervallo other)
{
if (inizio < other.inizio)
{
return -1;
}
if (inizio == other.inizio)
{
if (fine < other.fine)
{
return -1;
}
else
if (fine == other.fine)
{
return 0;
}
}
return 1;
}
}


class Parser
{
public static List<Intervallo> scanFrom(String inputFile)
{
List<Intervallo> list = new ArrayList<Intervallo>();

Scanner s = null;
try
{
s = new Scanner(new BufferedReader(new FileReader(inputFile)));
s.useLocale(Locale.US);
while (s.hasNext())
{
double d1 = s.nextDouble();
double d2 = s.nextDouble();
list.add(new Intervallo(d1, d2));
}
}
catch (FileNotFoundException e)
{
System.out.println("Input file: " + inputFile + " don't exist");
}
catch (NoSuchElementException e)
{
System.out.println("Malformed input file: " + inputFile);
System.exit(0);
}
finally
{
if (s != null)
s.close();
}

return list;
}
}


class Resolver
{
Collection<Intervallo> collection;
int recursionCounter = 0;

public Resolver(Collection<Intervallo> sortedCollection)
{
collection = sortedCollection;
}

/**
* risolve gli Intervalli sovvrapposti; la collezione viene modificata per
* contenere solo gli Intervalli singoli (non sovvrapposti). L'iterazione
* esamina e risolve gli Intervalli a coppie adiacenti; puo' quindi essere
* neccessario iterare piu' volte.
*/
public void resolve()
{
recursionCounter++;

boolean doRecursiveCall = false;
boolean singleContinue = false;

Intervallo A = null;
Intervallo B = null;
Iterator<Intervallo> iterator = collection.iterator();

while (iterator.hasNext())
{
if (singleContinue)
{
singleContinue = false;
B = iterator.next();
}
else
{
A = iterator.next();
if (iterator.hasNext()) B = iterator.next();
else break; // raggiunta fine della collezione
}

if (A.join(B))
{
iterator.remove();
doRecursiveCall = true;
}
else
{
A = B;
singleContinue = true;
}
}

if (doRecursiveCall)
resolve();
}

public double getResult()
{
double result = 0;

for (Intervallo i : collection)
result += i.lenght();

return result;
}
}

Il funzionamento dell'algoritmo può essere descritto così:
1 - Parser legge il file di testo prendendo i tokens a due a due e crea una collezione di Intervalli;
2 - Un Intervallo ha due double: 'inizio' e 'fine'. Il valore di 'inizio' è sempre minore o uguale al valore di 'fine';
3 - la lista degli Intervalli messa in ordine ascendente (dove un Itervallo è minore di un altro se ha il punto di 'inizio' strettamente minore del punto di 'inizio' dell'altro oppure lo ha uguale ma ha il punto di 'fine' strettamente minore del punto di 'fine' dell'altro).
3 - La lista viene passata a un Resolver che "risolve" le sovvrapposizioni.
La tecnica (banale) è iterare confrontando gli Intervalli a due a due e passare il secondo della coppia al primo come parametro del metodo 'join'
4 - Il metodo 'join' di un Intervallo accetta un'altro Intervallo e, se esiste una sovvraposizione tra i due, la risolve, modificando se stesso per rappresentare il nuovo Intervallo risultato della "fusione" dei due.
5 - Resolver esegue questa iterazione una o più volte, finchè nella lista degli Intervalli non restano che Intervalli 'unici', ovvero non 'sovvrapposti'.

Esempio di una tipica esecuzione
http://www.freeimagehosting.net/uploads/c90748ba15.jpg (http://www.freeimagehosting.net/)
sul mio sistema:
http://www.freeimagehosting.net/uploads/406fde732c.jpg (http://www.freeimagehosting.net/)

Critiche e consigli sono ben'accetti!
:)

@EDIT:
di solito il tempo si esecuzione mi oscilla tra i 400 e i 700 millisencodi.
@EDIT2:
sì, lo so, sono lento, ma non ho introdotto nessuna ottimizzazione nel codice... questa stesura è stata fatta cercando di essere OO (spero di esserci riuscito), senza pensare alle performance. Probabilmente si può migliorare sotto questo aspetto.

@EDIT3: sono lento perchè istanzio gli Intervalli durante il parsing del file di testo, e quindi ho preso i tempi includendo queste operazioni.

[banryu79]

Minchia, ma è già morto il contest16?
uppette!

[^TiGeRShArK^]

eh non lo so.. :stordita:
io avevo provato a fare qualcosina di diverso, ma poi mi è calato il sonno e ho lasciato stare :asd:

[banryu79]

Io chiederei a gugoXX di postarci il generatore del file di dati oppure di uppare un file da 100.000 o 1.000.000 di righe, così siamo incentivati :D

[gugoXX]

Io chiederei a gugoXX di postarci il generatore del file di dati oppure di uppare un file da 100.000 o 1.000.000 di righe, così siamo incentivati :D

Sisi', posto il generatore, scusate, ma sto cambiando lavoro e ho tantissime cose arretrate da terminare per tempo.


public class LineParser
{
private List<Interval> intervals;

public LineParser()
{
intervals = new List<Interval>();
}

public void Parse(string FName)
{
intervals.Clear();
StreamReader sr = new StreamReader(FName);
string line="";
while ((line = sr.ReadLine()) != null)
{
string[] vals = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
if (vals.Length != 2)
throw new Exception("Error in parsing file");

double d1 = double.Parse(vals[0]);
double d2 = double.Parse(vals[1]);
Interval inv = new Interval(d1, d2);
intervals.Add(inv);
}
}

public double Result()
{
Line ln = new Line();
return ln.GetResult(intervals);
}

public static void ToRandomFile(string FName, int howmany)
{
Random rnd = new Random();
StreamWriter sw = new StreamWriter(FName);
for (int t = 0; t < howmany; t++)
{
double m1 = rnd.NextDouble() * 400000 - 200000;
double lensw = rnd.NextDouble()*1000;
double m2 = m1 + (rnd.NextDouble() * lensw - (lensw/2));
sw.WriteLine("{0} {1}", m1, m2);
}
sw.Close();
}
}

Il generatore e' il metodo statico
LineParser.ToRandomFile

Occorrera' aggiustare un po' le costanti, per non avere troppe sovrapposizioni, oppure troppo poche.

[^TiGeRShArK^]

dove te ne vai di bello? :p

[gugoXX]

dove te ne vai di bello? :p

Mi sposto di qualche centinaio di metri...
Sempre qui in zona nella City.

[banryu79]

Mi sposto di qualche centinaio di metri...
Sempre qui in zona nella City.
Auguri allora per il nuovo lavoro! Spero sia un miglioramento gugo! :)

@Tiger: se hai tempo potresti per piacere indicarmi, rispetto al codice C# postato da gugoXX, quali classi lì utilizzate hanno un corrispettivo nel JDK (perchè purtroppo C# non l'ho mai guardato :stordita:) così mi traduco il generatore?
Sennò genera tu la listona :D

[^TiGeRShArK^]

Per il generatore casuale puoi utilizzare tranquillamente java.util.Random che ha gli stessi metodi, per scrivere sul file va benissimo un normale BufferedWriter se non ricordo male :p

[banryu79]

Per il generatore casuale puoi utilizzare tranquillamente java.util.Random che ha gli stessi metodi, per scrivere sul file va benissimo un normale BufferedWriter se non ricordo male :p
Sì scusa, io mi ero preoccupato perchè nella fretta non avevo controllato che rea solo un metodo quello che ci interessa :D

Eccolo qua, in Java:

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Random;
/**
* Generatore del file di input per il contest 16
* @author obtained from gugoXX, hwupgrade forum - Sezione Programmazione -
*/
public class FileGenerator
{
/** Generator entry point */
public static void main(String[] argv) throws Exception
{
if (argv.length < 1)
{
throw new Exception("Bisogna indicare il file di output dei dati");
}

if (argv.length < 2)
{
throw new Exception("Bisogna indicare il numero di stringhe da produrre");
}

int howmany = 0;
try
{
howmany = Integer.parseInt(argv[1]);
}
catch (NumberFormatException e)
{
throw new Exception("Bad parameter format: must be an integer value", e);
}

FileGenerator.produceRandom(argv[0], howmany);
}

/** Generator */
public static void produceRandom(String file, int howmany)
{
Random r = new Random();
PrintWriter w = null;

try
{
w = new PrintWriter(file);
for (int t = 0; t < howmany; t++)
{
double m1 = r.nextDouble() * 400000 - 200000;
double lensw = r.nextDouble()*1000;
double m2 = m1 + (r.nextDouble() * lensw - (lensw/2));
w.println(m1 + " " + m2);
}
}
catch (FileNotFoundException ex)
{
System.out.println("Il file specificato " + file + "non esiste");
}
finally
{
if (w != null) w.close();
}
}
}


@EDIT:
Ecco, appena provato con 100.000 righe... e vado in crisi... 11 sec.
Bene, appena ho tempo continuo a provare a migliorarlo.

[^TiGeRShArK^]

ehmmm..
non puoi postare il file da 100k che hai provato? :p

[banryu79]

Ecco il file da 100K righe:
http://www.usaupload.net/d/xow3y1culdx

Ecco cosa ottengo:
http://www.freeimagehosting.net/uploads/23ef563bb0.jpg (http://www.freeimagehosting.net/)

[^TiGeRShArK^]

ehmmm..
cosa ottieni? :stordita:
cmq non puoi separare il caricamento in memoria dal parsing?
così puoi predenre i due tempi divisi :p

[Vincenzo1968]

Questi i miei tempi col file da centomila righe postato da Banryu:
http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzione3.jpg

Questi i tempi di Tiger(Ma ho dovuto sostituire, nel file, i punti con le virgole: c'è modo di evitare questa gran camurrìa?):
http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger4.jpg

:bimbo:

[^TiGeRShArK^]

ah ok, ora la vedo l'immagine di banryu che prima non vedevo.. :stordita:
cmq sulla mia macchina ottengo:

Il totale è 400553,152322267, calcolato in 259ms

[^TiGeRShArK^]

Questi i miei tempi col file da centomila righe postato da Banryu:
http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzione3.jpg

Questi i tempi di Tiger(Ma ho dovuto sostituire, nel file, i punti con le virgole: c'è modo di evitare questa gran camurrìa?):
http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger4.jpg

:bimbo:

si, ecco:

CultureInfo culture = new CultureInfo("EN-us");
string[] content = File.ReadAllLines("MyRealLine.txt");
Stopwatch watch = Stopwatch.StartNew();
char[] separator = new char[] { ' ' };
var orderedIntervals = (from c in content
let tokens = c.Split(separator, StringSplitOptions.RemoveEmptyEntries)
let first = double.Parse(tokens[0], culture.NumberFormat)
let second = double.Parse(tokens[1], culture.NumberFormat)
select new double[] {
first <= second ? first : second,
first <= second ? second : first
}).OrderBy(e => e[0]).ToArray();

double previousRight = double.NegativeInfinity;
double total = 0.0;
foreach (var interval in orderedIntervals)
{
double left = interval[0];
double right = interval[1];
if (previousRight <= right)
{
if (left > previousRight)
{
total += right - left;
}
else
{
total += right - previousRight;
}
previousRight = right;
}
}
watch.Stop();
Console.WriteLine("Il totale è {0}, calcolato in {1}ms", total, watch.ElapsedMilliseconds);
Console.ReadLine();

:p

[Vincenzo1968]

Ohè,

col Watcom (http://www.openwatcom.org/index.php/Main_Page) risulta un pochino più veloce:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneWatcom2.jpg

:bimbo:

[banryu79]

cmq non puoi separare il caricamento in memoria dal parsing?
così puoi predenre i due tempi divisi :p

Sì, appena ho tempo lo faccio, oggi ho una giornata di fuoco in ufficio.
Inoltre taglio via cose "inutili" nel codice (tipo usare un oggetto per rappresentare una coppia di valori come un intevallo, visto che istanziarne 100K costicchia) che appesantiscono i tempi.

[^TiGeRShArK^]

sono sceso di una 10ina di ms ma mi sa che il fattore limitante è il quick sort utilizzato dall'orderby di linq che ha prestazioni peggiori rispetto ad esempio all'heap sort....

[^TiGeRShArK^]

rettifico...
la maggior parte del tempo viene persa per il parsing dei double... :fagiano:

...vincenzo ma tu nel tuo codice calcoli il tempo dopo che hai effettuato il parsing, o sbaglio? :stordita:

[banryu79]

rettifico...
la maggior parte del tempo viene persa per il parsing dei double... :fagiano:

...vincenzo ma tu nel tuo codice calcoli il tempo dopo che hai effettuato il parsing, o sbaglio? :stordita:
Mia tempistica dopo aver modificato in modo da caricare in memoria il file e poi partire a contare il tempo passato:

run:
Result for input file: C:\MyRealLine.txt is: 400553.1523222679
performed 19 recursive calls
Time, in milliseconds: 8884
BUILD SUCCESSFUL (total time: 10 seconds)

Praticamente con quest'ordine di grandezza risparmio rozzamente circa 1,5-2 sec.

Se invece non contassi ne caricamento del file ne parsing dei double allora avrei all'incirca questo risultato (praticamente solo ordinamento della lista degli input e algoritmo di risoluzione)

run:
Result for input file: C:\MyRealLine.txt is: 400553.1523222679
performed 19 recursive calls
Time, in milliseconds: 3859
BUILD SUCCESSFUL (total time: 9 seconds)

Comunque lento.

@EDIT:
Evitando di contare anche i tempi presi dal buon merge sort in place del JDK (che si comporta bene nonostante si debba sorbire la logica del compareTo da me scritta) sono lento proprio nella risoluzione:

run:
Result for input file: C:\MyRealLine.txt is: 400553.1523222679
performed 19 recursive calls
Time, in milliseconds: 3439
BUILD SUCCESSFUL (total time: 8 seconds)

Ma infatti non ho tentato niente di 'furbo' per velocizzare.

@EDIT: voglio vedere se riesco a risolvere il problema delle sovvrapposizioni con una sola iterazione.

[Vincenzo1968]

rettifico...
la maggior parte del tempo viene persa per il parsing dei double... :fagiano:

...vincenzo ma tu nel tuo codice calcoli il tempo dopo che hai effettuato il parsing, o sbaglio? :stordita:

Si, infatti il tempo da considerare è quello totale:

0.328 secondi(col Visual Studio)
0.218 secondi(col Watcom)

:bimbo:

Praticamente carico i dati con la funzione DFA(automa a stati finiti) e creo l'albero binario di ricerca ordinato secondo i valori minimi.
Il tempo di calcolo è dato dalla funzione Calcola che attraversa l'albero(InOrder) e, appunto, calcola il risultato. La maggior parte del tempo se ne va nella fase di parsing.

[^TiGeRShArK^]

mmm..
ma col tempo totale mi sa che calcoli anche il caricamento del file tu...
Ora modifico il mio per farmi stampare i due tempi (su xp virtualizzato però) :p

[Vincenzo1968]

mmm..
ma col tempo totale mi sa che calcoli anche il caricamento del file tu...
Ora modifico il mio per farmi stampare i due tempi (su xp virtualizzato però) :p

Si, infatti.

Il tempo totale comprende caricamento dal file, creazione del BST e calcolo del risultato.

[^TiGeRShArK^]

fatto....

Loading and parsing file time: 366ms
Il totale è 400553,152322267, calcolato in 75ms

il codice modificato....

Stopwatch watch = Stopwatch.StartNew();
CultureInfo culture = new CultureInfo("EN-us");
string[] content = File.ReadAllLines("MyRealLine.txt");
char[] separator = new char[] { ' ' };
var orderedIntervals = (from c in content
let tokens = c.Split(separator, StringSplitOptions.RemoveEmptyEntries)
let first = double.Parse(tokens[0], culture.NumberFormat)
let second = double.Parse(tokens[1], culture.NumberFormat)
select new double[] {
Math.Min(first, second),
Math.Max(first, second)
}).ToArray();
Console.WriteLine("Loading and parsing file time: {0}ms", watch.ElapsedMilliseconds);
watch.Reset();
watch.Start();
double previousRight = double.NegativeInfinity;
double total = 0.0;
foreach (var interval in orderedIntervals.OrderBy(e => e[0]))
{
double left = interval[0];
double right = interval[1];
if (previousRight <= right)
{
if (left > previousRight)
{
total += right - left;
}
else
{
total += right - previousRight;
}
previousRight = right;
}
}
watch.Stop();
Console.WriteLine("Il totale è {0}, calcolato in {1}ms", total, watch.ElapsedMilliseconds);
Console.ReadLine();

Lo puoi provare sulla tua macchina vincenzo?
Ora non devi cambiare i punti in virgole :p

[Vincenzo1968]

...
Lo puoi provare sulla tua macchina vincenzo?
Ora non devi cambiare i punti in virgole :p

Eqque qua:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger5.jpg

[^TiGeRShArK^]

:mbe:
strano che su xp virtualizzato mi giri + veloce che sulla tua macchina, mentre prima con il file da 10k elementi accadeva il contrario... :fagiano:
Ma l'hai fatto girare in modalità release? :stordita:
Misteri dell'informatica :p

[Vincenzo1968]

:mbe:
strano che su xp virtualizzato mi giri + veloce che sulla tua macchina, mentre prima con il file da 10k elementi accadeva il contrario... :fagiano:
Ma l'hai fatto girare in modalità release? :stordita:
Misteri dell'informatica :p

Si si,

è in modalità release. Ecco varie prove:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger6.jpg

[^TiGeRShArK^]

allora quelli di parallels mi sa che hanno fatto un'ottimo lavoro con la loro macchina virtuale :p
cmq confermo la "scarsità" dell'algoritmo di ordinamento predefinito del C# che da me ci mette 71 ms sui 75ms totali del calcolo... :stordita:

[marco.r]

Versione haskell.
Ci mette una eternita' a caricare i dati, ma quello e' colpa del linguaggio, non mia :D
I tempi di calcolo sono quasi ragionevoli, 0.800 sulla mia macchina, contro i 0.350 circa della soluzione di vincenzo... o perlomeno penso, visto che ho cercato di forzare la valutazione completa dell'input prima dell'inizio dell'elaborazione, ma non sono sicuro di esserci riuscito...
Il mio metodo introduce maggiori imprecisioni che dovrei sistemare, in ogni caso dovrebbe scalare molto bene col crescere della dimensione del problema (eccezione fatta per il parsing dei float... :S )
Qualcuno ha un dataset piu' grande ?

module Main where
import System.Environment
import Data.Array
import Data.List
import qualified Data.Set as Set
import System.CPUTime

type Value = Float

type Interval = (Value,Value)
mkInterval x y = (x,y)
data Bucket = Empty | Mixed !(Set.Set Interval) | Full deriving(Show)
-- data Bucket = Empty | Mixed [Interval] | Full deriving(Show)

mix = Set.union
-- mix = (++)

getElems = Set.elems
-- getElems = id

mkSingle = Set.singleton
-- mkSingle x = [x]

makePairs :: [Value] -> [Interval]
makePairs [] = []
makePairs (x:y:xs) = (min x y,max x y) : makePairs xs

readPairs :: String -> [Interval]
readPairs text
= let
numbers :: [Value]
numbers = map read $ words text
in
makePairs numbers

merge :: Bucket -> Bucket -> Bucket
merge Full _ = Full
merge _ Full = Full
merge Empty x = x
merge x Empty = x
merge (Mixed xs) (Mixed ys) = {-# SCC "Mixed" #-} Mixed $ mix xs ys

mixIntervals [] xs = xs
mixIntervals xs [] = xs
mixIntervals (x:xs) (y:ys) = if x < y then x : mixIntervals xs (y:ys)
else y : mixIntervals (x:xs) ys


splitInterval :: (Value->Int) -> (Int->Value) -> (Int->Value) ->Interval -> [(Int,Bucket)]
splitInterval bucketOf upperBound lowerBound (low,up)
= let
lb = bucketOf low
ub = bucketOf up
newLb = {-# SCC "newLb" #-} Mixed $ mkSingle (low,min (upperBound lb) up)
newUb = {-# SCC "newUb" #-} Mixed $ mkSingle (max (lowerBound ub) low,up)
in
(lb,newLb) : (ub,newUb) : [ (n,Full) | n <- [lb+1 .. ub-1] ]


coverage :: [Interval] -> Value
coverage [] = 0.0
coverage xs = coverage' 0.0 (fst $ head ss) ss
where
ss = sort xs

coverage' :: Value -> Value -> [Interval] -> Value
coverage' acc lb [] = acc
coverage' acc lb ((l,u):xs)
= coverage' size (max lb u) xs
where
size = acc + (max lb u) - (max lb l)


-- solve :: [Interval] -> Value
solve pairs
= let
minValue = minimum $ map fst pairs
maxValue = maximum $ map snd pairs
numberOfBuckets = max 3 $ length pairs `div` 20
valueRange = maxValue - minValue
bucketOf :: Value -> Int
bucketOf f = {-# SCC "bucketOf" #-} floor $ ( f - minValue ) * (realToFrac (numberOfBuckets )) / valueRange

bucketSize :: Value
bucketSize = valueRange / (realToFrac numberOfBuckets)

lowerBound :: Int -> Value
lowerBound n = {-# SCC "lowerBound"#-} realToFrac n * bucketSize + minValue

upperBound :: Int -> Value
upperBound n = {-# SCC "upperBound"#-} realToFrac (n+1) *bucketSize + minValue

intervals = concatMap (splitInterval bucketOf upperBound lowerBound) pairs
result = accumArray merge Empty (0,numberOfBuckets) intervals

cover Empty = 0
cover Full = bucketSize
cover (Mixed xs) = coverage $ getElems xs
in
sum $ map cover $ elems result

main :: IO ()
main
= do args <- getArgs
contest16 $ head args
return ()

forcePairs [] = []
forcePairs ((x,y):xs) = x `seq` y `seq` forcePairs xs
contest16 filename
= do
time1 <- getCPUTime
text <- readFile filename
let nums = readPairs text
numbers = forcePairs nums `seq` nums
putStr $ "just read " ++ (forcePairs numbers `seq` show (length numbers)) ++ " numbers\n"
time2 <- getCPUTime
putStr "Parse Time : "
putStrLn $ show $ realToFrac (time2 - time1) * 1e-12
time3 <- getCPUTime
let solution = solve $ sort numbers
print solution
time4 <- getCPUTime
putStr "Solution Time : "
putStrLn ( solution `seq` show (realToFrac ( time4 - time3 )* 1e-12))
return solution

[^TiGeRShArK^]

Ma se decidiamo un seed e una dimensione e lo generiamo col codice di gugo o di banryu?
Però forse è meglio decidere prima se usare java o C# per la generazione perchè non sono sicurissimo che il seed generi gli stessi valori per i due linguaggi... :stordita:

[gugoXX]

Preso il codice di Tiger, e modificato poco, aggiunto il parallelismo nella sezione parsing, che e' quella piu' lenta, ottengo

Loading: 40ms
Parsing: 183ms
Il totale è 400553.152322267, calcolato in 70ms

Su un quad core, quindi parsing su 4 thread in parallelo.

Comunque direi che giunti al punto in cui il tempo di parsing e' maggiore del tempo di elaborazione, possiamo dire di avere raggiunto un risultato piu' che decoroso.
Certo, ingrandendo il dominio il parsing dovrebbe risultare sempre meno influente, dato che gli algoritmi trovati dovrebbero essere O(N log N)
Resta che a mio parere abbiamo raggiunto il target.

Mamma, e' sempre piu' difficile trovare problemi che non vengano massacrati da questo gruppo!!!

[!k-0t1c!]

Versione F# leggermente modificata del codice di Tiger (richiede VS2010 beta 1)


open System
open System.IO
open System.Diagnostics

let sortedIntervals (filename:string) =
filename |> File.ReadAllLines
|> Array.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) |> Array.map(double) |> Array.sort in arr.[0], arr.[1])
|> Array.sortBy(fun (a,b) -> a)
|> List.of_array

let rec examine values previousRight total =
match values with
| [] -> total
| (left,right)::remaining-> if right >= previousRight then
if left > previousRight then examine remaining right (total + right - left)
else examine remaining right (total + right - previousRight)
else examine remaining previousRight total

let main() =
let sw = Stopwatch.StartNew()
let intervals = sortedIntervals "MyRealLine.txt"
sw.Stop()
printfn "Caricamento e parsing effettuato in %ims" sw.ElapsedMilliseconds
sw.Reset()
sw.Start()
let res = examine intervals (Double.NegativeInfinity) 0.0
sw.Stop()
printfn "Totale: %f (tempo di esecuzione: %ims)" res sw.ElapsedMilliseconds
Console.ReadKey() |> ignore

do main();;


Il parsing risulta essere molto lento, ma il tempo d'esecuzione sul mio PC (che fa abb schifo) è 3ms e l'eleganza del codice non si batte :)

[shinya]

Versione in Factor (l'algoritmo è quello di Tiger):

USING: accessors kernel math math.intervals math.parser
math.order sequences sorting sorting.slots locals io.files
io.encodings.ascii splitting ;
IN: contest16

: sort-intervals ( seq -- sorted-seq )
{ { from>> <=> } } sort-by ; inline

:: sum-intervals ( total p-right interval -- total p-right )
[let | left [ interval from>> first ]
right [ interval to>> first ] |
p-right right <= [
left p-right > [
right left - total +
] [
right p-right - total +
] if right
] [
total p-right
] if ] ;

: solve-intervals ( seq -- n )
0 -1/0. rot [ sum-intervals ] each drop ; inline

: read-intervals ( filename -- seq )
ascii file-lines [
" " split1 [ string>number ] bi@ sort-pair [a,b]
] map ;

: contest16 ( filename -- solution )
read-intervals sort-intervals solve-intervals ;

Ci sarebbe la funzione 'sum-intervals' da rifattorizzare... cosi fa un pò schifo.

[^TiGeRShArK^]

Versione F# leggermente modificata del codice di Tiger (richiede VS2010 beta 1)


open System
open System.IO
open System.Diagnostics

let sortedIntervals (filename:string) =
filename |> File.ReadAllLines
|> Array.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) |> Array.map(double) |> Array.sort in arr.[0], arr.[1])
|> Array.sortBy(fun (a,b) -> a)
|> List.of_array

let rec examine values previousRight total =
match values with
| [] -> total
| (left,right)::remaining-> if right >= previousRight then
if left > previousRight then examine remaining right (total + right - left)
else examine remaining right (total + right - previousRight)
else examine remaining previousRight total

let main() =
let sw = Stopwatch.StartNew()
let intervals = sortedIntervals "MyRealLine.txt"
sw.Stop()
printfn "Caricamento e parsing effettuato in %ims" sw.ElapsedMilliseconds
sw.Reset()
sw.Start()
let res = examine intervals (Double.NegativeInfinity) 0.0
sw.Stop()
printfn "Totale: %f (tempo di esecuzione: %ims)" res sw.ElapsedMilliseconds
Console.ReadKey() |> ignore

do main();;


Il parsing risulta essere molto lento, ma il tempo d'esecuzione sul mio PC (che fa abb schifo) è 3ms e l'eleganza del codice non si batte :)

ma perchè da me non esiste il metodo di istanza string.Split in F#? :mbe:
sarà la versione vecchia di F# o mi sfugge qualcosa? :stordita:
ho abbandonato la scrittura del codice del contest in F# proprio perchè visual studio non mi vedeva quel metodo... :mbe:

[shinya]

Ok, rifattorizzato!
Guarda mamma! Senza variabili! :Prrr:

USING: accessors kernel math math.intervals math.parser
math.order sequences sorting sorting.slots io.files
io.encodings.ascii splitting tools.time ;
IN: contest16

: sort-intervals ( seq -- sorted-seq )
{ { from>> <=> } } sort-by ; inline

: sum-intervals ( total p-right interval -- total p-right )
[ from>> first ] [ to>> first ] bi
dup [ pick ] dip <= [
[ max ] dip [ swap - + ] keep
] [ 2drop ] if ;

: solve-intervals ( seq -- n )
0 -1/0. rot [ sum-intervals ] each drop ; inline

: read-intervals ( filename -- seq )
ascii file-lines [
" " split1 [ string>number ] bi@ sort-pair [a,b]
] map ;

: contest16 ( filename -- solution )
read-intervals [ sort-intervals solve-intervals ] time ;

[^TiGeRShArK^]

minchia che casino che è il factor, mi si incrociano gli occhi :asd:

[shinya]

minchia che casino che è il factor, mi si incrociano gli occhi :asd:
L'unica funzione cervellotica è 'sum-intervals' perchè ci sono un pò di valori sullo stack e quindi bisogna giocarci un pò... il resto mi sembra abbastanza chiaro, se vuoi posso spiegarlo... anche se credo sia più che altro questione di re-imparare a leggere :)

[^TiGeRShArK^]

L'unica funzione cervellotica è 'sum-intervals' perchè ci sono un pò di valori sullo stack e quindi bisogna giocarci un pò... il resto mi sembra abbastanza chiaro, se vuoi posso spiegarlo... anche se credo sia più che altro questione di re-imparare a leggere :)

appunto, mi sa che è proprio quello il problema..:p
nel primo codice che hai postato con tutte quelle parentesi quadre m'era preso il mal di mare :asd:

[banryu79]

Complimenti per le versioni in Factor e F#, a mio gusto trovo il codice molto elegante :mano:
(Non ci capisco niente perchè non conosco la sintassi e non ho il tempo e la pazienza di mettermeli a leggere con calma, però mi sembrano codice molto compatti ed eleganti).

@shinya: io gradirei la spiegazione discorsiva della tua soluzione :fagiano:

[banryu79]

Per chi voleva un file di input ancora più ampio: file da 1.000.000 di righe (http://www.usaupload.net/d/8uvo0kluak0).
Pesa 18 mega.

[^TiGeRShArK^]

per quello dicevo che era meglio metterci d'accordo su un seed anzichè scambiarci 18 mega di dati :p

[Vincenzo1968]

Vorrei prendere i tempi di tutte le soluzioni postate e stilare una prima classifica.

x marco.r e shinya: che devo fare per compilare ed eseguire le vostre soluzioni? Da dove scarico Haskell e Factor?

x Gugo: puoi postare il codice sorgente?

x !k-0t1c!: io ho installato Visual Studio 2008 e non vorrei che la versione beta di visual studio 10 causasse qualche problema con quella precedente. Puoi gentilmente postare l'eseguibile?

Grazie ;)

[^TiGeRShArK^]

per haskell io se non sbaglio avevo usato winhugs ai tempi, ma sarebbe meglio chiedere a marco una conferma mi sa :p

[shinya]

(Non ci capisco niente perchè non conosco la sintassi...
In Factor non c'è sintassi, sono tutte funzioni di una qualche libreria :)
@shinya: io gradirei la spiegazione discorsiva della tua soluzione :fagiano:
Cercherò di spiegarmi senza scrivere un tutorial sul linguaggio, ma non assicuro niente. Giusto una premessa...

Factor è un linguaggio concatenativo. In termini generali vuol dire che si parla di 'function composition' e non di 'function application'. In altri termini vuol dire che c'è uno stack e un programma è definito da un insieme di funzioni che prende valori dallo stack e/o rilascia valori sullo stack.
Il "comportamento" di una funzione lo puoi vedere dalla stack effect declaration (la roba tra parentesi tonde):

: add-two ( x -- y ) ...
'add-two' è una funzione che prende un valore dallo stack (indicato da 'x') e ne lascia un altro (indicato da 'y').
Potrebbe essere implementata cosi:
: add-two ( x -- y ) 2 + ;
Cosa succede? Beh, 'add-two' si aspetta un valore sullo stack, quindi aggiunge '2' allo stack e poi invoca la funzione '+' che prende due valori dallo stack e ne rilascia uno. Ci sono due elementi importanti: '2' è un literal e '+' è una funzione. I literal vengono aggiunti allo stack, le funzioni invece "trasformano" lo stack. In Factor c'è un altro elemento, le quotation. Tutta quella roba tra parentesi quadre, presente?
Quotation. E' sostanzialmente una funzione anonima, che invece di essere eseguita, viene aggiunta allo stack (è il meccanismo con cui vengono implementate le closure, tra le altre cose).

Fine premessa.
L'algoritmo è quello di Tigershark, nè più nè meno. Il "main" è la funzione "contest16" ovviamente, che fa 3 cose in sequenza. Legge dal file (read-intervals), ordina gli intervalli (sort-intervals) e risolve il problema (solve-intervals). Questo è il modo in cui va letto il programma. In sequenza. Ogni funzione non fa altro che trasformare qualche valore in qualcos'altro per preparare l'input della funzione successiva.

'read-intervals' legge dal file tutte le righe in memoria, e cicla sopra di esse (map applica una funzione ad ogni elemento di una collection, come in tutti gli altri linguaggi funzionali). Quello che fa la quotation che viene passata a map è solo splittare in due la riga, trasformare le due stringhe in numeri, ordinarli e costruire un intervallo. La funzione '[a,b]' non è una quotation, è una funzione con un nome strambo. Costruisce un oggetto 'interval', che sta in una libreria ('math.interval') e rappresenta un qualcosa che va da un punto 'x' a un punto 'y'. A questo punto abbiamo una lista di intervalli.

'sort-intervals' ordina la lista di intervalli in base al campo 'from' dell'oggetto che rappresenta l'intervallo. La struttura degli intervalli la si può leggere nella documentazione, non c'è molto da spiegare. :) Comunque, dopo questa funzione abbiamo una lista ordinata di intervalli.

'solve-intervals' aggiunge due valori allo stack come prima cosa. 0 e "meno infinito" (-1/0. rappresenta proprio -inf), che sono il "total" e il "previousRight" del codice di Tigershark. Questi valori faranno da accumulatori nel ciclo successivo. Quale ciclo? 'each' prende una collection e una funzione come parametri e passa ogni elemento della lista alla funzione.

'sum-intervals' è quella cervellotica. Non c'è molto da spiegare in realtà, per convincersi del suo funzionamento non c'è altro modo se non prendere un foglietto di carta e vedere lo stato dello stack ad ogni operazione. dup, pick, swap, drop sono tutte funzioni che prendono dei valori dallo stack e li ridispongono sullo stack.
La funzione prende tre valori, il totale, il previousRight e l'intervallo corrente. Estrae 'from' e 'to' dall'intervallo e fa un pò di casino in modo da lasciare sullo stack il nuovo 'totale' e il nuovo 'previousRight'. Alla fine 'solve-intervals' chiama 'drop' sull'ultimo valore (l'ultimo previousRight) e rimane solo il totale sullo stack. Fine della storia. :)

Per capire meglio (forse), puoi vedere una funzione come una bacchetta magica che tocca lo stack e lo trasforma in qualcos'altro... *zapp!* :)

[Vincenzo1968]

Ho provato a compilare il codice di Marco.r ma ho i seguenti errori:

http://www.guidealgoritmi.it/images/ImgForums/Contest16ErroreMarcoR.jpg

Haskell l'ho scaricato da qui:

http://www.haskell.org/

[Vincenzo1968]

Questi i miei tempi sul file da un milione di righe postato da Banryu:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzione4.jpg

questi i tempi di Tiger:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneTiger7.jpg

La macchina è questa:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

[shinya]

x marco.r e shinya: che devo fare per compilare ed eseguire le vostre soluzioni? Da dove scarico Haskell e Factor?
Factor per windows lo trovi qua http://builds.factorcode.org/download?os=winnt&cpu=x86.32
Io uso una versione compilata da me prendendo gli ultimi sorgenti dal repository... ma probabilmente la build che trovi li è abbastanza aggiornata.
Ho modificato il codice nell'altro messaggio in modo che stampi una serie di statistiche (c'è della roba relativa al garbage collector, oltre al tempo impiegato) lasciando fuori il tempo di lettura del file.

Per usarlo:
Crei un file "contest16.factor" e ci copi il codice.
Lo metti qui "<dove-hai-installato-factor>/work/contest16/contest16.factor"
Doppio-click su 'factor.exe' e ti lancia il listener.
Poi scrivi:
USE: contest16 <invio>
"file-di-test.txt" contest16 <invio>

"file-di-test.txt" deve stare nella stessa directory di factor.exe
Il codice viene compilato nativamente al volo, quindi non ci dovrebbe essere bisogno di creare un eseguibile... anche se si può fare comunque...

[!k-0t1c!]

@Tiger: sicuramente string.Split funziona, almeno da F# 1.9.6.2 (Sept. CTP)
detto questo sulla versione vecchia non potresti usare Array.Parallel

@Vincenzo: VS2010 vive benissimo side by side con vs2008 (io li ho tutti e due installati e nessun problema), e anche se compilassi un eseguibile ti servirebbe .NET 4 beta1, disponibile solo con VS2010 (per ovvie ragioni). Inoltre se la mettiamo sulle performance preferisco rivedere 1attimo il codice e strizzare qualche decimo di secondo in meno ;) vedrò se trovo il tempo domani

[banryu79]

In Factor non c'è sintassi, sono tutte funzioni di una qualche libreria :)

Cercherò di spiegarmi senza scrivere un tutorial sul linguaggio, ma non assicuro niente. Giusto una premessa...

[cut...]

Encomiabile spiegazione, grazie infinite!
Seguendo passo-passo quello che hai scritto con codice sempre accanto ho *quasi* *capito* tutti i singoli passi.

In effetti ammiravo la "sintesi ordinata" del codice postato della tua soluzione che mi trasmette quel senso di eleganza che apprezzo in un sorgente: però sospettavo fosse dovuto ad una "densità" specifica molto più alta di quelle a cui sono abituato.

L'atto di seguire il codice in Factor mi ha portato a vedere il problema da una diversa prospettiva, anche se credo di essermi mentalmente aggrappato più agli aspetti procedurali che al resto, quindi della parte funzionale della cosa mi resta più che altro un 'senso di esotico'.

[^TiGeRShArK^]

Io comunque continuo a preferire la versione C# e quella F# rispetto a quelle Haskell e Factor... :stordita:

[banryu79]

@!k-0t1c!: se avrai tempo potresti spiegare la 'examine' della tua soluzione?
Mi intrippo un po' perchè non conosco il linguaggio e mi perdo a capire la ricorsione...

@Tiger:

Io comunque continuo a preferire la versione C# e quella F# rispetto a quelle Haskell e Factor...

Ammetto che quella Haskell manco l'ho letta, scoraggiato dalla lunghezza rispetto le altre due (considerando che non conosco il linguaggio, poche righe sono più psicologicamente incoraggianti, ecco!).

[Vincenzo1968]

Factor per windows lo trovi qua http://builds.factorcode.org/download?os=winnt&cpu=x86.32
Io uso una versione compilata da me prendendo gli ultimi sorgenti dal repository... ma probabilmente la build che trovi li è abbastanza aggiornata.
Ho modificato il codice nell'altro messaggio in modo che stampi una serie di statistiche (c'è della roba relativa al garbage collector, oltre al tempo impiegato) lasciando fuori il tempo di lettura del file.

Per usarlo:
Crei un file "contest16.factor" e ci copi il codice.
Lo metti qui "<dove-hai-installato-factor>/work/contest16/contest16.factor"
Doppio-click su 'factor.exe' e ti lancia il listener.
Poi scrivi:
USE: contest16 <invio>
"file-di-test.txt" contest16 <invio>

"file-di-test.txt" deve stare nella stessa directory di factor.exe
Il codice viene compilato nativamente al volo, quindi non ci dovrebbe essere bisogno di creare un eseguibile... anche se si può fare comunque...

Ok, grazie mille ;)

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneShinya.jpg

[shinya]

Umh... ma i tempi non li stampa? Hai preso l'ultima versione?
Questa qua dico: http://www.hwupgrade.it/forum/showpost.php?p=28054461&postcount=82

[Vincenzo1968]

I tempi di Shinya sul file da un milione di righe:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneShinya2.jpg

[^TiGeRShArK^]

@!k-0t1c!: se avrai tempo potresti spiegare la 'examine' della tua soluzione?
Mi intrippo un po' perchè non conosco il linguaggio e mi perdo a capire la ricorsione...

ci provo io per il poco che conosco F# :p

let rec examine values previousRight total =
match values with
| [] -> total
| (left,right)::remaining-> if right >= previousRight then
if left > previousRight then examine remaining right (total + right - left)
else examine remaining right (total + right - previousRight)
else examine remaining previousRight total

La parola chiave rec definisce una funzione ricorsiva chiamata examine che riceve in input due parametri: values e previousRight.
A questo punto effettua un match dei valori di ritorno della funzione (vedilo come una specie di if) restituendo total quando la funzione ha completato l'esecuzione e in values si ritrova una lista vuota.
invece nei passi precedenti estrae ogni elemento left e right da values in una tupla e lo aggiunge in testa alla lista remaining e quindi esegue l'if con le varie chiamate ricorsive....

Ho solo qualche dubbio sull'inserimento in testa di left e right in remaining e l'applicazione dell'operatore -> (che dovrebbe essere l'equivalente di => del LINQ) :stordita:

[shinya]

I tempi di Shinya sul file da un milione di righe:
28 secondi!?! Uhhh... L-E-N-T-O!!! :(

[banryu79]

@TigerShark: perfetto grazie, almeno ho capito la tecnica!
P.S.: appena ho tempo continuo, volevo proporre una versione che fa uso di un binary red black tree... se ce la fo.

[shinya]

Adesso dovrebbe essere molto più veloce... sul mio pc stiamo a 5 secondi circa dai 30 di prima (per il file gigante, senza contare la lettura da file)! E ho guadagnato anche qualche riga di codice :)

Vincenzo, se vuoi riprovare con questo...
Forse su linux le prestazioni possono essere migliori...Factor per windows è compilato via cygwin, che non è che sia proprio il massimo.

USING: arrays kernel math math.parser math.order sequences
sorting io.files io.encodings.ascii splitting tools.time ;
IN: contest16

: sum-intervals ( tot prev-right interval -- tot prev-right )
[ first ] [ second ] bi
dup [ pick ] dip <= [
[ max ] dip [ swap - + ] keep
] [ 2drop ] if ;

: solve-intervals ( seq -- n )
0 -1/0. rot [ sum-intervals ] each drop ;

: string>pair ( str -- pair )
" " split1 [ string>number ] bi@ sort-pair 2array ; inline

: read-intervals ( filename -- seq )
ascii file-lines [ string>pair ] map ;

: contest16 ( filename -- solution )
read-intervals [ natural-sort solve-intervals ] time ;

[Vincenzo1968]

Adesso dovrebbe essere molto più veloce... sul mio pc stiamo a 5 secondi circa dai 30 di prima (per il file gigante, senza contare la lettura da file)! E ho guadagnato anche qualche riga di codice :)

Vincenzo, se vuoi riprovare con questo...
Forse su linux le prestazioni possono essere migliori...Factor per windows è compilato via cygwin, che non è che sia proprio il massimo.
...


Eqque qua:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneShinya3.jpg

[Vincenzo1968]

Uh!

chiedo venia! Nel post precedente ho preso i tempi sul file piccolo(quello da centomila righe).
Questi sono i tempi sul file da un milione di righe:

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneShinya4.jpg

[marco.r]

Ho provato a compilare il codice di Marco.r ma ho i seguenti errori:

http://www.guidealgoritmi.it/images/ImgForums/Contest16ErroreMarcoR.jpg

Haskell l'ho scaricato da qui:

http://www.haskell.org/

Dovrebbe funzionare senza problemi con il comando

ghc --make Main.hs

dove Main.hs e' il nome del file


edit: per l'esecuzione

Main.exe numeri.txt

dove numeri.txt e' il file con i valori

[marco.r]

@!k-0t1c!: se avrai tempo potresti spiegare la 'examine' della tua soluzione?
Mi intrippo un po' perchè non conosco il linguaggio e mi perdo a capire la ricorsione...

@Tiger:

Ammetto che quella Haskell manco l'ho letta, scoraggiato dalla lunghezza rispetto le altre due (considerando che non conosco il linguaggio, poche righe sono più psicologicamente incoraggianti, ecco!).

La versione haskell e' un attimo elaborata, visto che l'implementazione "semplice" e' eccessivamente lenta. Per confronto, questa e' l'implementazione n log n che dovrebbe corrispondere alle soluzioni degli altri
module Main where

import Data.List
import System.Environment
import System.CPUTime

solve :: [(Float,Float)] -> Float
solve ns = solve' (fst $ head ns) ns

solve' :: Float -> [(Float,Float)] -> Float
solve' _ [] = 0
solve' lb ((l,u):xs) = (max lb u) - (max lb l) + solve' (max lb u) xs

pairs [] = []
pairs (x:y:xs) = (min x y,max x y) : pairs xs

--

forceValues [] = []
forceValues (x:xs) = x `seq` forceValues xs

main
= do args <- getArgs
text <- readFile (head args)
time1 <- getCPUTime
let numbers :: [Float]
numbers = map read $ words text
putStr $ seq (forceValues numbers) "Parse time :"
time2 <- getCPUTime
putStrLn $ show $ realToFrac (time2-time1) * 1e-12
print $ solve $ sort $ pairs numbers
time3 <- getCPUTime
putStr "Solve time: "
putStr $ show $ realToFrac (time3-time2) * 1e-12

La maggior parte del codice e' I/O e un tentativo di separare la computazione del parser da quella del solutore, l'algoritmo sono le sei righe tra solve e pairs piu' in alto.

[shinya]

L'atto di seguire il codice in Factor mi ha portato a vedere il problema da una diversa prospettiva, anche se credo di essermi mentalmente aggrappato più agli aspetti procedurali che al resto, quindi della parte funzionale della cosa mi resta più che altro un 'senso di esotico'.
Come per tutte le forme di stregoneria, ci vuole un pò di tempo per entrare nella nuova mentalità :)

[banryu79]

Come per tutte le forme di stregoneria, ci vuole un pò di tempo per entrare nella nuova mentalità :)
Dici che, visto il background javesco, potrei muovere dei primi cauti passi andando a conoscere Scala?

P.S.: la soluzione con l'albero binario non ce l'ho, perchè riesco a costruire l'albero, ma poi sbaglio qualcosa nella risoluzione delle sovvrapposizioni...


La maggior parte del codice e' I/O e un tentativo di separare la computazione del parser da quella del solutore, l'algoritmo sono le sei righe tra solve e pairs piu' in alto.

Potresti spiegarmi come si deve interpretare la dichiarazione di una funzione?

solve :: [(Float,Float)] -> Float
solve ns = solve' (fst $ head ns) ns

solve' :: Float -> [(Float,Float)] -> Float
solve' _ [] = 0
solve' lb ((l,u):xs) = (max lb u) - (max lb l) + solve' (max lb u) xs

Di solve capisco che prende due Float e torna un Float; per solve' non sono sicuro del significato del primo Float ->

[!k-0t1c!]

Versione F# leggermente migliorata (usando il sorting di LINQ dato che Array.sort fa due copie dell'input durante il sorting e su input grandi risulta improponibilmente lento).


open System
open System.IO
open System.Linq
open System.Diagnostics

let sortedIntervals (filename:string) =
(filename |> File.ReadAllLines
|> Array.Parallel.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) |> Array.map(double) |> Array.sort in arr.[0], arr.[1])).OrderBy(new Func<_,_>(fun (a,_) -> a))
|> List.of_seq

let rec examine values previousRight total =
match values with
| [] -> total
| (left,right)::remaining-> if left >= previousRight then examine remaining right (total + right - left)
elif right >= previousRight then examine remaining right (total + right - previousRight)
else examine remaining previousRight total

let main() =
let sw = Stopwatch.StartNew()
let intervals = sortedIntervals "MyRealLine.txt"
sw.Stop()
printfn "Caricamento e parsing effettuato in %ims" sw.ElapsedMilliseconds
sw.Reset()
sw.Start()
let res = examine intervals (Double.NegativeInfinity) 0.0
sw.Stop()
printfn "Totale: %f (tempo di esecuzione: %ims)" res sw.ElapsedMilliseconds
Console.ReadKey() |> ignore

do main();;

Il tempo di parsing sul file da 100K righe è migliorato del 66% ed il tempo di processing è fisso a 3ms.

@banryu: la funzione examine (in questa versione) non fa altro che questo:

controlla che values non sia una lista vuota
se è vuota ritorna il totale passato in argomento (solitamente dalla chiamata ricorsiva precedente)
altrimenti scompatta la tuple in testa alla lista nei valori left e right e crea una variabile (remaining) che indica la parte restante della lista, eccetto il valore in testa
esamina left e right come richiesto per il problema e a seconda delle comparazioni la chiamata ricorsiva avrà come argomenti un nuovo totale adeguatamente aggiornato ed un nuovo punto massimo raggiunto a destra

[marco.r]

Potresti spiegarmi come si deve interpretare la dichiarazione di una funzione?

solve :: [(Float,Float)] -> Float
solve ns = solve' (fst $ head ns) ns


solve e' una funzione che prende una lista di coppie di float, e ritorna un float
se a e b sono tipi, allora (a,b) rappresenta la 2-upla con i due tipi, mentre [ a ] rappresenta la lista con elementi di tipo a.


solve' :: Float -> [(Float,Float)] -> Float
solve' _ [] = 0
solve' lb ((l,u):xs) = (max lb u) - (max lb l) + solve' (max lb u) xs
[/CODE]
Di solve capisco che prende due Float e torna un Float; per solve' non sono sicuro del significato del primo Float ->
solve' prende un Float, una lista di coppie di Float e ritorna un Float.

(Tecnicamente solve' primo e' una funzione che prende come argomento un Float e ritorna una funzione che prende come argomento un una lista di coppie di float e ritorna un float, ma son dettagli :D)

In pratica quello che fa float' e' la seguente cosa
prende come argomento la lista ordinata di intervalli da sommare, e il margine di tutti gli intervalli calcolati finora. In pratica somma ricorsivamente le lunghezze degli intervalli, ma si porta dietro il margine dell'intervallo coperta piu' a desra, in modo da non sovrapporcisi.

[shinya]

Dici che, visto il background javesco, potrei muovere dei primi cauti passi andando a conoscere Scala?
Se ti incuriosisce Scala, provalo! Io non lo conosco quindi non ti so dire...

Personalmente se dovessi scegliere un linguaggio nuovo da imparare sarei per Factor o Clojure (se vuoi restare su JVM e usare le librerie che già conosci).

Comunque non ti devi spaventare, anch'io vengo da Java (e C prima) e a parte i primi momenti di "OH-MMIO-DDIOOO" con Factor, trovo che il paradigma concatenativo sia in realtà molto potente ed espressivo. Non è cosi difficile come può sembrare all'inizio :)

[Vincenzo1968]

Dovrebbe funzionare senza problemi con il comando

ghc --make Main.hs

dove Main.hs e' il nome del file


edit: per l'esecuzione

Main.exe numeri.txt

dove numeri.txt e' il file con i valori

Vero è.
Ecco i risultati(purtroppo va in stack overflow sul file grosso):

http://www.guidealgoritmi.it/images/ImgForums/Contest16soluzioneMarcoR.jpg

[banryu79]

@banryu: la funzione examine (in questa versione) non fa altro che questo:

controlla che values non sia una lista vuota
se è vuota ritorna il totale passato in argomento (solitamente dalla chiamata ricorsiva precedente)
altrimenti scompatta la tuple in testa alla lista nei valori left e right e crea una variabile (remaining) che indica la parte restante della lista, eccetto il valore in testa
esamina left e right come richiesto per il problema e a seconda delle comparazioni la chiamata ricorsiva avrà come argomenti un nuovo totale adeguatamente aggiornato ed un nuovo punto massimo raggiunto a destra

Ok, sei stato chiarissimo e finalmente ho capito l'essenza della tua examine :)

@marco.r:
ok, grazie anche a te, con le spiegazioni a corredo dei sorgenti è più abbordabile capire il significato dei sorgenti stessi (e quindi l'algoritmo) anche per un profano come me :)

[banryu79]

Comunque non ti devi spaventare, anch'io vengo da Java (e C prima) e a parte i primi momenti di "OH-MMIO-DDIOOO" con Factor, trovo che il paradigma concatenativo sia in realtà molto potente ed espressivo. Non è cosi difficile come può sembrare all'inizio :)
Sì, così "a muzzo" mi pare che come paradigma quello funzionale di questi linguaggi sia buono per creare algoritmi specifici; mentre la prospettiva OO con i suoi design pattern e le librerie OO create con questo tipo di struttura portante mi pare più indicato per gestire la complessità che si viene a creare nel momento in cui si assembla il "modello" con la rappresentazione e gestione di input output via interfacce grafiche, oppure per gestire i diversi layer di astrazione di una libreria.
Almeno questa è l'impressione di massima che ho al momento.