Forum: Italian Ruby user group [OT] refactoring di problemi - Was: un insieme casuale la cu

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
D8fb06dfc08a477ecb0a76ffdbff3475?d=identicon&s=25 Chiaro Scuro (chiaroscuro)
on 2007-02-28 02:31
(Received via mailing list)
On 2/27/07, Matteo Vaccari <vaccari@pobox.com> wrote:
>
> Cool Chiaro, bella soluzione.


cheers :-)

all'inizio pensavo fosse un problema di aggiustamento iterativo del
risultato e a avevo pensato addirittura agli algoritmi genetici. su trm
c'era quell'articolo di intinig che cercava appunto di trovare gli
addendi
che dessero un certo risultato finale usando gli algoritmi genetici.

poi mi si è accesa la lampadina, ma qui la butto in pasto ai più meta-geek
della ML.. perchè benchè i due problemi siano equivalenti (distribuire X
risorse su Y giorni == tagliare una baguette lunga X in Y fette di
lunghezza
casuale) uno è facile da risolvere e l'altro ti porta a un vicolo cieco?

ci sono studi su questo?  sul fare reframing dei problemi per
rifattorizzarli a uno stato dove siano triviali da risolvere?
C01072ccffb1f2d23f8b5f686e5b106a?d=identicon&s=25 gabriele renzi (Guest)
on 2007-02-28 09:19
(Received via mailing list)
--- chiaro scuro <kiaroskuro@gmail.com> wrote:


> ci sono studi su questo?  sul fare reframing dei
> problemi per
> rifattorizzarli a uno stato dove siano triviali da
> risolvere?

meta reframing: se trasformo la domanda in "ci sono
studi sulla riduzione di un problema ad un altro?" la
risposta sarebbe "si, tutta l'informatica teorica".

A parte questo, l'unico modo di affrontare il problema
in modo alternativo (che mi viene in mente) è: pensa a
quali strutture dati sarebbero adatte o inventane una.

 Come dicono in perl-landia, se i dati non
corrispondono alla tua funzione, cambiali (es:
shwartzian transform)

--
icq:     #69488917
blog it: http://riffraff.blogsome.com
blog en: http://www.riffraff.info



___________________________________________________________
Copy addresses and emails from any email account to Yahoo! Mail - quick,
easy and free. http://uk.docs.yahoo.com/trueswitch2.html
4c8f1734faea8b7b2db0ea4bf4ebbf66?d=identicon&s=25 Matteo Vaccari (Guest)
on 2007-02-28 14:13
(Received via mailing list)
On 2/28/07, gabriele renzi <surrender_it@yahoo.it> wrote:
> studi sulla riduzione di un problema ad un altro?" la
> risposta sarebbe "si, tutta l'informatica teorica".

Giusto.  Tutta la matematica, in realtà :)
D8fb06dfc08a477ecb0a76ffdbff3475?d=identicon&s=25 Chiaro Scuro (chiaroscuro)
on 2007-02-28 14:25
(Received via mailing list)
On 2/28/07, Matteo Vaccari <vaccari@pobox.com> wrote:
>
> > meta reframing: se trasformo la domanda in "ci sono
> > studi sulla riduzione di un problema ad un altro?" la
> > risposta sarebbe "si, tutta l'informatica teorica".
>
> Giusto.  Tutta la matematica, in realtà :)


si, ma in quel caso perchè un problema era più facile da risolvere
dell'altro? mi sembravano matematicamente identici, ma rivestiti di
metafore
differenti.
Aea9ee14e387a68f5cd63048a0ba9266?d=identicon&s=25 david (Guest)
on 2007-02-28 15:14
(Received via mailing list)
Anche secondo me la soluzione è bella. Non l'ho ancora capito del
   tutto e non ho ancora finito di tradurre quello che ho capito in
   codice; ho capito che la soluzione è lì, quindi son tranquillo...
   :-)
   "girare la frittata" in quel modo lì è una delle cose più belle del
   essere umano. Ci vuole intelligenza per estrarre *solo* gli elementi
   fondamentali e trasportarli in un altro contesto, auspicabilmente
   chiarificatore.
   chiaro scuro wrote:

     On 2/27/07, Matteo Vaccari [1]<vaccari@pobox.com> wrote:

     Cool Chiaro, bella soluzione.

     cheers :-)
     all'inizio pensavo fosse un problema di aggiustamento iterativo del
     risultato e a avevo pensato addirittura agli algoritmi genetici. su
     trm
     c'era quell'articolo di intinig che cercava appunto di trovare gli
     addendi
     che dessero un certo risultato finale usando gli algoritmi
     genetici.
     poi mi si è accesa la lampadina, ma qui la butto in pasto ai più
     meta-geek
     della ML.. perchè benchè i due problemi siano equivalenti
     (distribuire X
     risorse su Y giorni == tagliare una baguette lunga X in Y fette di
     lunghezza
     casuale) uno è facile da risolvere e l'altro ti porta a un vicolo
     cieco?
     ci sono studi su questo?  sul fare reframing dei problemi per
     rifattorizzarli a uno stato dove siano triviali da risolvere?
     _______________________________________________
     Ml mailing list
     [2]Ml@lists.ruby-it.org
     [3]http://lists.ruby-it.org/mailman/listinfo/ml

--
"Our enemies are innovative and resourceful, and so are we. They never
stop thi
nking about new ways to harm our country and our people, and neither do
we." -
George W. Bush, Washington, D.C., Aug. 5, 2004

References

   1. mailto:vaccari@pobox.com
   2. mailto:Ml@lists.ruby-it.org
   3. http://lists.ruby-it.org/mailman/listinfo/ml
4c8f1734faea8b7b2db0ea4bf4ebbf66?d=identicon&s=25 Matteo Vaccari (Guest)
on 2007-02-28 23:26
(Received via mailing list)
On 2/28/07, chiaro scuro <kiaroskuro@gmail.com> wrote:
> dell'altro? mi sembravano matematicamente identici, ma rivestiti di metafore
> differenti.

Forse l'insight è di non considerare il problema come "trovare un
insieme di numeri la cui *somma* sia N", ma "trovare un insieme di
numeri che rappresentano *frazioni* di N".  Cioè se dimentichi la
somma inizi a ragionare per frazioni diventa più facile.  Nel primo
caso ci sono infinite maniere di scegliere un array di numeri la cui
somma è sbagliata.  Nel secondo caso ogni soluzione è valida, non c'è
maniera di scegliere un numero fra 0 e 1 che non rappresenti una
frazione di N.

E' vero, una volta che riformuli il problema nella maniera giusta la
difficoltà sparisce.  Le cose geniali sono le più semplici.  Le cose
semplici sono le più geniali.

M
D8fb06dfc08a477ecb0a76ffdbff3475?d=identicon&s=25 Chiaro Scuro (chiaroscuro)
on 2007-03-09 12:02
(Received via mailing list)
il "pensare per frazioni" o per rapporti di Matteo mi ha messo la pulce
nell'orecchio e ho trovato una soluzione più elegante senza bisogno di
baguette.

se dovete dividere una quantità T tra n recipienti R1.. Rn e la quantità
contenuta in ogni recipiente è casuale allora basta la seguente ricetta:

contenuto R(x) = numero random tra 0 e T

questo però ti dà un totale probabilemente maggiore di T.

a questo punto normalizzi dividendo tutto per la somma di tutti gli R..
nessun bisogno di sorting dei tagli sulla baguette.. la randomicità di
ogni
R è commensurabile con quella degli altri e il totale da T come voluto.

chi sa qualcosa di statistica mi spiega perchè funziona? quello che
capisco
è che l' "ordine di randomicità" dei tagli della baguette e degli R(x)
normalizzati è lo stesso.  Non riesco però a esprimerlo in termini
matematici e a derivare un'algebra che mi dice che i due problemi sono
identici e che mi permette di giungere alla soluzione del problema step
by
step (e come cacchio inserisco il sorting in un'algebra??).

On 2/28/07, Matteo Vaccari <vaccari@pobox.com> wrote:
> caso ci sono infinite maniere di scegliere un array di numeri la cui
> Ml@lists.ruby-it.org
> http://lists.ruby-it.org/mailman/listinfo/ml
>



--
-- Kia

therubymine.com | be a miner
Db3bb695675f86a74002addc9c1c7267?d=identicon&s=25 Francesco Cioffi (Guest)
on 2007-03-09 18:08
(Received via mailing list)
L'ultimo post mi ha fatto venir voglia di provare...

Allego il codice Ruby di una possibile soluzione al problema
originario commentato con le spiegazioni.


FC
Aea9ee14e387a68f5cd63048a0ba9266?d=identicon&s=25 david (Guest)
on 2007-03-09 19:37
(Received via mailing list)
Questo è ottimo. Mi ha permesso di finire il programma e c'ho una
   manciata di utenti felici. Grazie a te chiaro-scuro!
   :-)
   chiaro scuro wrote:

     il "pensare per frazioni" o per rapporti di Matteo mi ha messo la
     pulce
     nell'orecchio e ho trovato una soluzione più elegante senza bisogno
     di
     baguette.
     se dovete dividere una quantità T tra n recipienti R1.. Rn e la
     quantità
     contenuta in ogni recipiente è casuale allora basta la seguente
     ricetta:
     contenuto R(x) = numero random tra 0 e T
     questo però ti dà un totale probabilemente maggiore di T.
     a questo punto normalizzi dividendo tutto per la somma di tutti gli
     R..
     nessun bisogno di sorting dei tagli sulla baguette.. la randomicità
     di ogni
     R è commensurabile con quella degli altri e il totale da T come
     voluto.
     chi sa qualcosa di statistica mi spiega perchè funziona? quello che
     capisco
     è che l' "ordine di randomicità" dei tagli della baguette e degli
     R(x)
     normalizzati è lo stesso.  Non riesco però a esprimerlo in termini
     matematici e a derivare un'algebra che mi dice che i due problemi
     sono
     identici e che mi permette di giungere alla soluzione del problema
     step by
     step (e come cacchio inserisco il sorting in un'algebra??).
     On 2/28/07, Matteo Vaccari [1]<vaccari@pobox.com> wrote:

     > si, ma in quel caso perchè un problema era più facile da
     risolvere
     > dell'altro? mi sembravano matematicamente identici, ma rivestiti
     di
     metafore
     > differenti.
     Forse l'insight è di non considerare il problema come "trovare un
     insieme di numeri la cui *somma* sia N", ma "trovare un insieme di
     numeri che rappresentano *frazioni* di N".  Cioè se dimentichi la
     somma inizi a ragionare per frazioni diventa più facile.  Nel primo
     caso ci sono infinite maniere di scegliere un array di numeri la
     cui
     somma è sbagliata.  Nel secondo caso ogni soluzione è valida, non
     c'è
     maniera di scegliere un numero fra 0 e 1 che non rappresenti una
     frazione di N.
     E' vero, una volta che riformuli il problema nella maniera giusta
     la
     difficoltà sparisce.  Le cose geniali sono le più semplici.  Le
     cose
     semplici sono le più geniali.
     M
     _______________________________________________
     Ml mailing list
     [2]Ml@lists.ruby-it.org
     [3]http://lists.ruby-it.org/mailman/listinfo/ml

--
"The really rich people figure out how to dodge taxes anyway." - George
W. Bush
, explaining why high taxes on the rich are a failed strategy,
Annandale, Va.,
Aug. 9, 2004

References

   1. mailto:vaccari@pobox.com
   2. mailto:Ml@lists.ruby-it.org
   3. http://lists.ruby-it.org/mailman/listinfo/ml
1c29f9b1bf5f1b88ed8b0c9a9be39788?d=identicon&s=25 Daniele Alessandri (Guest)
on 2007-03-09 20:56
(Received via mailing list)
On 3/9/07, Francesco Cioffi <ruby@fcioffi.net> wrote:
>
> L'ultimo post mi ha fatto venir voglia di provare...
>
> Allego il codice Ruby di una possibile soluzione al problema
> originario commentato con le spiegazioni.


Ho ripreso il tuo codice riscrivendolo un po' più in stile Ruby (ho
evitato
i commenti ma se è necessario spiego volentieri).
Qualcuno ha una soluzione ancora più elegante?
28c29f97569429d35882fdabf09f83ee?d=identicon&s=25 Massimiliano Mirra (Guest)
on 2007-03-09 22:53
(Received via mailing list)
On 3/9/07, Daniele Alessandri <suppakilla@gmail.com> wrote:
> Qualcuno ha una soluzione ancora più elegante?
Che bello, un po' di Ruby golf. :-)

Accontentate la mia pigrizia e inviate nel corpo del messaggio invece
che come allegato?  GMail non mostra i sorgenti inline. :-(


--
Massimiliano Mirra
code: http://dev.hyperstruct.net
blog: http://blog.hyperstruct.net
Aea9ee14e387a68f5cd63048a0ba9266?d=identicon&s=25 david (Guest)
on 2007-03-10 09:20
(Received via mailing list)
Bella, la tua versione. Proprio carina! (e molto migliore della
   mia...)
   Daniele Alessandri wrote:

     On 3/9/07, Francesco Cioffi [1]<ruby@fcioffi.net> wrote:

     L'ultimo post mi ha fatto venir voglia di provare...
     Allego il codice Ruby di una possibile soluzione al problema
     originario commentato con le spiegazioni.

     Ho ripreso il tuo codice riscrivendolo un po' più in stile Ruby (ho
     evitato
     i commenti ma se è necessario spiego volentieri).
     Qualcuno ha una soluzione ancora più elegante?
    _______________________________________________________________________

_______________________________________________
Ml mailing list
[2]Ml@lists.ruby-it.org
[3]http://lists.ruby-it.org/mailman/listinfo/ml


--
"Smaken är som baken - delad."

References

   1. mailto:ruby@fcioffi.net
   2. mailto:Ml@lists.ruby-it.org
   3. http://lists.ruby-it.org/mailman/listinfo/ml
36f352bc8c234dbde21cb30e89767824?d=identicon&s=25 Matley (Guest)
on 2007-03-10 23:42
(Received via mailing list)
Io calcolerei la prima somma con inject (imho ogni linea é cosi' é un
filino piu' chiara). Risultato in slots.

TOTAL = 1
n = 10
rands = Array.new(n) { rand }
sum = rands.inject { |subtotal, el| el + subtotal }
slots = rands.map { |el| el / sum * TOTAL }
1c29f9b1bf5f1b88ed8b0c9a9be39788?d=identicon&s=25 Daniele Alessandri (Guest)
on 2007-03-11 09:57
(Received via mailing list)
On 3/10/07, Matley <matley@muppetslab.org> wrote:
>
>
> Io calcolerei la prima somma con inject (imho ogni linea é cosi' é un
> filino piu' chiara). Risultato in slots.
>
> TOTAL = 1
> n = 10
> rands = Array.new(n) { rand }
> sum = rands.inject { |subtotal, el| el + subtotal }
> slots = rands.map { |el| el / sum * TOTAL }


Hai ragione a dire che è più chiaro, in effetti lo è.
L'unica considerazione che ho fatto per evitare l'inject, a cui avevo
pensato ma che poi ho volutamente tralasciato, non è stata tanto la
solita
tentazione dello one-liner (anche perché rimane fuori quel sum = 0,
maledetto :D) quanto più che altro il risparmio di un'iterazione
sugli elementi dell'array (quello che hai fatto con l'inject) per
calcolare
la somma, effettuando invece questo calcolo direttamente in fase di
valorizzazione dello stesso. Sì lo so, per un array di 10 o comunque
pochi
elementi possono essere considerate pippe mentali, ma è la forza
dell'abitudine :)
36f352bc8c234dbde21cb30e89767824?d=identicon&s=25 Luigi Panzeri (Guest)
on 2007-03-11 11:23
(Received via mailing list)
"Daniele Alessandri" <suppakilla@gmail.com> writes:

>
Il numero delle operazioni é sempre lo stesso (4n), cambia solo
l'ordine. n esecuzioni di rand, n somme ed 2n prodotti/divisioni.

Lo one-liner completo lo puoi fare:

recipienti = (rands = Array.new(n) { rand }).map { |el| el /
(rands.inject { |subtotal, el| el + subtotal })  * TOTAL }
4cdea2acea5b12d29134308996abbba2?d=identicon&s=25 Andrea Censi (Guest)
on 2007-03-11 11:38
(Received via mailing list)
On 3/11/07, Luigi Panzeri <matley@muppetslab.org> wrote:

> Lo one-liner completo lo puoi fare:
>
> recipienti = (rands = Array.new(n) { rand }).map { |el| el / (rands.inject { |subtotal, 
el| el + subtotal })  * TOTAL }

In questo caso, l'algoritmo gira in O(n^2) ?

Immagino che Ruby non si accorga che il  "rands.inject { ... " ha un
valore costante all'interno del loop -- dopotutto, uno potrebbe aver
aver cambiato inject.

--
Andrea Censi
      "Life is too important to be taken seriously" (Oscar Wilde)
Web: http://www.dis.uniroma1.it/~censi
1c29f9b1bf5f1b88ed8b0c9a9be39788?d=identicon&s=25 Daniele Alessandri (Guest)
on 2007-03-11 13:12
(Received via mailing list)
On 3/11/07, Luigi Panzeri <matley@muppetslab.org > wrote:


>
> Il numero delle operazioni é sempre lo stesso (4n), cambia solo
> l'ordine. n esecuzioni di rand, n somme ed 2n prodotti/divisioni.


Certamente, il numero delle operazioni matematiche è lo stesso e nella
realtà non cambia particolarmente nemmeno l'ordine della loro esecuzione
(la somma viene comunque effettuata dopo il calcolo di rand in entrambi
i
casi), ciò che cambia non è la complessità matematica ma l'efficienza
dell'implementazione: con due iterazioni su array (prima inject e poi
map)
anziché una (soltanto map) l'interprete è costretto a lavorare di più
(il
doppio delle letture dallo stesso, maggiori allocazioni, maggior lavoro
del
GC).

Poi ripeto, sono il primo ad ammettere che su un array di 10 elementi
non
cambia assolutamente nulla e non ne vale nemmeno la pena (si ha una
differenza in termini di tempi di esecuzione sull'ordine del secondo
giusto
con un array di 1.000.000 di elementi), però secondo me è bello e sempre
utile essere consapevoli di certe differenze.


> Lo one-liner completo lo puoi fare:
>
> recipienti = (rands = Array.new(n) { rand }).map { |el| el / (rands.inject{ |subtotal, 
el| el + subtotal })  * TOTAL }


Uhm così facendo però il blocco passato al metodo inject viene invocato
per
tutti gli elementi di rands ad ogni elemento di rands estratto tramite
il metodo map, anche se nella realtà il risultato di inject rimane
costante
(ma l'interprete non può saperlo). Cambia pesantemente la complessità
dell'algoritmo.
This topic is locked and can not be replied to.