[OT] refactoring di problemi - Was: un insieme casuale la cu


#1

On 2/27/07, Matteo V. removed_email_address@domain.invalid wrote:

Cool Chiaro, bella soluzione.

cheers :slight_smile:

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?


#2

— chiaro scuro removed_email_address@domain.invalid 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


#3

On 2/28/07, gabriele renzi removed_email_address@domain.invalid wrote:

studi sulla riduzione di un problema ad un altro?" la
risposta sarebbe “si, tutta l’informatica teorica”.

Giusto. Tutta la matematica, in realtà :slight_smile:


#4

On 2/28/07, Matteo V. removed_email_address@domain.invalid 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à :slight_smile:

si, ma in quel caso perchè un problema era più facile da risolvere
dell’altro? mi sembravano matematicamente identici, ma rivestiti di
metafore
differenti.


#5

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…
:slight_smile:
“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 V. [1]<removed_email_address@domain.invalid> 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]removed_email_address@domain.invalid
 [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:removed_email_address@domain.invalid
  2. mailto:removed_email_address@domain.invalid
  3. http://lists.ruby-it.org/mailman/listinfo/ml

#6

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 V. removed_email_address@domain.invalid wrote:

caso ci sono infinite maniere di scegliere un array di numeri la cui
removed_email_address@domain.invalid
http://lists.ruby-it.org/mailman/listinfo/ml

–
– Kia

therubymine.com | be a miner


#7

On 2/28/07, chiaro scuro removed_email_address@domain.invalid 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


#8

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


#9

Questo è ottimo. Mi ha permesso di finire il programma e c’ho una
manciata di utenti felici. Grazie a te chiaro-scuro!
:slight_smile:
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 V. [1]<removed_email_address@domain.invalid> 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]removed_email_address@domain.invalid
 [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:removed_email_address@domain.invalid
  2. mailto:removed_email_address@domain.invalid
  3. http://lists.ruby-it.org/mailman/listinfo/ml

#10

On 3/9/07, Francesco C. removed_email_address@domain.invalid 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?


#11

On 3/9/07, Daniele A. removed_email_address@domain.invalid wrote:

Qualcuno ha una soluzione ancora più elegante?
Che bello, un po’ di Ruby golf. :slight_smile:

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

–
Massimiliano M.
code: http://dev.hyperstruct.net
blog: http://blog.hyperstruct.net


#12

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 }


#13

On 3/10/07, Matley removed_email_address@domain.invalid 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 :slight_smile:


#14

“Daniele A.” removed_email_address@domain.invalid 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 }


#15

On 3/11/07, Luigi P. removed_email_address@domain.invalid 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


#16

Bella, la tua versione. Proprio carina! (e molto migliore della
mia…)
Daniele A. wrote:

 On 3/9/07, Francesco C. [1]<removed_email_address@domain.invalid> 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]removed_email_address@domain.invalid
[3]http://lists.ruby-it.org/mailman/listinfo/ml

–
“Smaken är som baken - delad.”

References

  1. mailto:removed_email_address@domain.invalid
  2. mailto:removed_email_address@domain.invalid
  3. http://lists.ruby-it.org/mailman/listinfo/ml

#17

On 3/11/07, Luigi P. <removed_email_address@domain.invalid > 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.