Mostra notizie nelle discussioni
  • Avatar
    Scritto da
    Non Autenticato
    il 2010-03-24 15:49:00.0 alle 2010-03-24 15:49:00.0
    Estrazione casuale da array
    Supponiamo di avere un array

    a(i) = p

    dove p è la probabilità dell'elemento i-esimo.

    È possibile scrivere un algoritmo che esegua l'estrazione a caso di un elemento, in modo che la probabilità di essere estratti corrisponda a p?

    Cioè se

    a(0) = 1/2
    a(1) = 1/4
    a(2) = 1/4
    a(3) = 0

    eseguendo estrazioni multiple si osserverà che a(3) non viene mai estratto, e a(0) viene estratto il doppio delle volte di ciascuno degli altri due.

    Gatto estrattore
    • Avatar
      Scritto da
      Non Autenticato
      il 2010-03-24 16:00:00.0 alle 2010-03-24 16:00:00.0
      Re: Estrazione casuale da array

      - Scritto da:
      > Supponiamo di avere un array
      >
      > a(i) = p
      >
      > dove p è la probabilità dell'elemento i-esimo.
      >
      > È possibile scrivere un algoritmo che esegua
      > l'estrazione a caso di un elemento, in modo che
      > la probabilità di essere estratti corrisponda a
      > p?
      >
      > Cioè se
      >
      > a(0) = 1/2
      > a(1) = 1/4
      > a(2) = 1/4
      > a(3) = 0
      >
      > eseguendo estrazioni multiple si osserverà che
      > a(3) non viene mai estratto, e a(0) viene
      > estratto il doppio delle volte di ciascuno degli
      > altri
      > due.
      >
      > Gatto estrattore
      io farei così
      tiri fuori dal cappello magico un numero casuale se e' minore 0,5 estraggo a0 se e' compreso tra 0,5 e 0,75 prendo a1 se e' compreso tra 0,75 e 1 prendo a2
      facilissimo!
      ed efficace anche se magari non proprio figo come la descrizione
      • Avatar
        Scritto da
        Non Autenticato
        il 2010-03-24 16:07:00.0 alle 2010-03-24 16:07:00.0
        Re: Estrazione casuale da array
        > tiri fuori dal cappello magico un numero casuale
        > se e' minore 0,5 estraggo a0 se e' compreso tra
        > 0,5 e 0,75 prendo a1 se e' compreso tra 0,75 e 1
        > prendo a2

        Interessante, ma sento che comporta un qualche problema che per ora non ho presente, tipo richiedere un ordinamento particolare degli a(i) o roba simile.
        • Avatar
          Scritto da
          Non Autenticato
          il 2010-03-24 16:09:00.0 alle 2010-03-24 16:09:00.0
          Re: Estrazione casuale da array

          - Scritto da:
          > > tiri fuori dal cappello magico un numero casuale
          > > se e' minore 0,5 estraggo a0 se e' compreso tra
          > > 0,5 e 0,75 prendo a1 se e' compreso tra 0,75 e 1
          > > prendo a2
          >
          > Interessante, ma sento che comporta un qualche
          > problema che per ora non ho presente, tipo
          > richiedere un ordinamento particolare degli a(i)
          > o roba
          > simile.
          no non ci sono problemi basta che dividi l'intero in intervalli corretti coerentemente con le probabilità!
          • Avatar
            Scritto da
            Non Autenticato
            il 2010-03-24 16:15:00.0 alle 2010-03-24 16:15:00.0
            Re: Estrazione casuale da array
            > > > tiri fuori dal cappello magico un numero
            > casuale
            > > > se e' minore 0,5 estraggo a0 se e' compreso
            > tra
            > > > 0,5 e 0,75 prendo a1 se e' compreso tra 0,75
            > e
            > 1
            > > > prendo a2
            > >
            > > Interessante, ma sento che comporta un qualche
            > > problema che per ora non ho presente, tipo
            > > richiedere un ordinamento particolare degli a(i)
            > > o roba
            > > simile.
            > no non ci sono problemi basta che dividi l'intero
            > in intervalli corretti coerentemente con le
            > probabilità!

            Dunque, ad ogni elemento viene fatto corrispondere un intervallo numerico la cui misura è uguale a p, quindi si estrae un numero a caso nell'intervallo.

            Come idea è semplice, ma adesso devo pensare a un modo per far corrispondere ad ogni elemento dell'array un intervallo.

            Potrei dapprima ordinarli per p decrescenti. A quello con p più grande assegno l'intervallo [0, p[. Il seguente avrà una probabilità p' e gli assegno ]p, p+p'] e così via.
            • Avatar
              Scritto da
              Non Autenticato
              il 2010-03-24 16:19:00.0 alle 2010-03-24 16:19:00.0
              Re: Estrazione casuale da array
              > Potrei dapprima ordinarli per p decrescenti. A
              > quello con p più grande assegno l'intervallo [0,
              > p[. Il seguente avrà una probabilità p' e gli
              > assegno ]p, p+p'] e così via.

              Solo che con questo modo dovrei fare in modo di estrarre numeri casuali reali con un numero qualsiasi di cifre decimali, altrimenti l'insieme dei numeri casuali da estrarre è finito e in tal caso mi sa che ottengo soltanto una estrazione che approssima le probabilità volute.
              • Avatar
                Scritto da
                Non Autenticato
                il 2010-03-24 16:23:00.0 alle 2010-03-24 16:23:00.0
                Re: Estrazione casuale da array
                > > Potrei dapprima ordinarli per p decrescenti. A
                > > quello con p più grande assegno l'intervallo [0,
                > > p[. Il seguente avrà una probabilità p' e gli
                > > assegno ]p, p+p'] e così via.
                >
                > Solo che con questo modo dovrei fare in modo di
                > estrarre numeri casuali reali con un numero
                > qualsiasi di cifre decimali, altrimenti l'insieme
                > dei numeri casuali da estrarre è finito e in tal
                > caso mi sa che ottengo soltanto una estrazione
                > che approssima le probabilità volute.

                Se i numeri casuali da estrarre sono 1.000, 10.000, 100.000 volte più numerosi che gli a(i) la probabilità dell'estrazione approssima la probabilità p con sempre maggior precisione. A questo punto mi piacerebbe un calcolo dell'errore.
                • Avatar
                  Scritto da
                  Non Autenticato
                  il 2010-03-24 16:26:00.0 alle 2010-03-24 16:26:00.0
                  Re: Estrazione casuale da array

                  - Scritto da:
                  > > > Potrei dapprima ordinarli per p decrescenti. A
                  > > > quello con p più grande assegno l'intervallo
                  > [0,
                  > > > p[. Il seguente avrà una probabilità p' e gli
                  > > > assegno ]p, p+p'] e così via.
                  > >
                  > > Solo che con questo modo dovrei fare in modo di
                  > > estrarre numeri casuali reali con un numero
                  > > qualsiasi di cifre decimali, altrimenti
                  > l'insieme
                  > > dei numeri casuali da estrarre è finito e in tal
                  > > caso mi sa che ottengo soltanto una estrazione
                  > > che approssima le probabilità volute.
                  >
                  > Se i numeri casuali da estrarre sono 1.000,
                  > 10.000, 100.000 volte più numerosi che gli a(i)
                  > la probabilità dell'estrazione approssima la
                  > probabilità p con sempre maggior precisione. A
                  > questo punto mi piacerebbe un calcolo
                  > dell'errore.

                  sono sicuro che ci sono algoritmi ben definiti per trasformare un generatore di numeri casuali con distribuzione di probabilità uniforme in una distribuzione di probabilità di quelle tipiche (normale etc) anzi mi pare proprio di aver letto una cosa del genere su wikipedia (dalla quale traggo tutte le mie conoscenze passate presenti e future)
                • Avatar
                  Scritto da
                  Non Autenticato
                  il 2010-03-24 16:34:00.0 alle 2010-03-24 16:34:00.0
                  Re: Estrazione casuale da array
                  > > > Potrei dapprima ordinarli per p decrescenti. A
                  > > > quello con p più grande assegno l'intervallo
                  > [0,
                  > > > p[. Il seguente avrà una probabilità p' e gli
                  > > > assegno ]p, p+p'] e così via.
                  > >
                  > > Solo che con questo modo dovrei fare in modo di
                  > > estrarre numeri casuali reali con un numero
                  > > qualsiasi di cifre decimali, altrimenti
                  > l'insieme
                  > > dei numeri casuali da estrarre è finito e in tal
                  > > caso mi sa che ottengo soltanto una estrazione
                  > > che approssima le probabilità volute.
                  >
                  > Se i numeri casuali da estrarre sono 1.000,
                  > 10.000, 100.000 volte più numerosi che gli a(i)
                  > la probabilità dell'estrazione approssima la
                  > probabilità p con sempre maggior precisione. A
                  > questo punto mi piacerebbe un calcolo
                  > dell'errore.

                  Per il calcolo è essenziale conoscere quanti numeri a n cifre decimali contiene un generico intervallo [a, b[ (chiuso su a, aperto su b).
                  • Avatar
                    Scritto da
                    Non Autenticato
                    il 2010-03-24 17:11:00.0 alle 2010-03-24 17:11:00.0
                    Re: Estrazione casuale da array
                    > > > > Potrei dapprima ordinarli per p
                    > decrescenti.
                    > A
                    > > > > quello con p più grande assegno l'intervallo
                    > > [0,
                    > > > > p[. Il seguente avrà una probabilità p' e
                    > gli
                    > > > > assegno ]p, p+p'] e così via.
                    > > >
                    > > > Solo che con questo modo dovrei fare in modo
                    > di
                    > > > estrarre numeri casuali reali con un numero
                    > > > qualsiasi di cifre decimali, altrimenti
                    > > l'insieme
                    > > > dei numeri casuali da estrarre è finito e in
                    > tal
                    > > > caso mi sa che ottengo soltanto una estrazione
                    > > > che approssima le probabilità volute.
                    > >
                    > > Se i numeri casuali da estrarre sono 1.000,
                    > > 10.000, 100.000 volte più numerosi che gli a(i)
                    > > la probabilità dell'estrazione approssima la
                    > > probabilità p con sempre maggior precisione. A
                    > > questo punto mi piacerebbe un calcolo
                    > > dell'errore.
                    >
                    > Per il calcolo è essenziale conoscere quanti
                    > numeri a n cifre decimali contiene un generico
                    > intervallo [a, b[ (chiuso su a, aperto su
                    > b).

                    Però in pratica le probabilità p(i) sono date con un certo numero N di cifre decimali. Intuitivamente mi viene da pensare che se i numeri da estrarre hanno pure essi N cifre decimali, o un multiplo di N, il risultato possa anche essere esatto.

                    Ci vorrebbe sassofono. In lacrime
    • Avatar
      Scritto da
      Non Autenticato
      il 2010-03-24 16:03:00.0 alle 2010-03-24 16:03:00.0
      Re: Estrazione casuale da array

      - Scritto da:
      > Supponiamo di avere un array
      >
      > a(i) = p
      >
      > dove p è la probabilità dell'elemento i-esimo.
      >
      > È possibile scrivere un algoritmo che esegua
      > l'estrazione a caso di un elemento, in modo che
      > la probabilità di essere estratti corrisponda a
      > p?
      >
      > Cioè se
      >
      > a(0) = 1/2
      > a(1) = 1/4
      > a(2) = 1/4
      > a(3) = 0
      >
      > eseguendo estrazioni multiple si osserverà che
      > a(3) non viene mai estratto, e a(0) viene
      > estratto il doppio delle volte di ciascuno degli
      > altri
      > due.
      >
      > Gatto estrattore

      ho letto questo esercizio su Introduction to Algorithms
    • Avatar
      Scritto da
      Non Autenticato
      il 2010-03-24 16:47:00.0 alle 2010-03-24 16:47:00.0
      Re: Estrazione casuale da array

      - Scritto da:
      > Supponiamo di avere un array
      >
      > a(i) = p
      >
      > dove p è la probabilità dell'elemento i-esimo.
      >
      > È possibile scrivere un algoritmo che esegua
      > l'estrazione a caso di un elemento, in modo che
      > la probabilità di essere estratti corrisponda a
      > p?
      >
      > Cioè se
      >
      > a(0) = 1/2
      > a(1) = 1/4
      > a(2) = 1/4
      > a(3) = 0
      >
      > eseguendo estrazioni multiple si osserverà che
      > a(3) non viene mai estratto, e a(0) viene
      > estratto il doppio delle volte di ciascuno degli
      > altri
      > due.
      >
      > Gatto estrattore

      definiamo una generica funzione
      rnd()
      che restituisce un float x tale che 0<=x<1

      e dato un array a() definito da a(0) ad a(MAX),
      la funzione estratto(a()) prendendo in ingresso l'array a() restituirà un numero intero i compreso tra 0 e MAX, con la distribuzione di probabilità p=a(i).

      giusto?

      in pratica la funzione estratto deve:
      innanzitutto controllare che la sommatoria di tutti gli a(i) faccia 1, e se non dovesse farlo, dovrebbe decidere che cazzo fare.
      posto che le probabilità siano corrette, dovrebbe prendere un float n = rnd(), compararlo con a(i) con i=0 e vedere se il risultato è minore di 0. Se sì, estratto = i, se no, si incrementa i e si riprova.
      Il limite di questa implementazione è che comunque a parità di p, a(x) sarà sempre più probabile rispetto ad a(y). Quindi ci vorrebbe prima una funzione disordinatrice che creasse un'array di una struttura float p e int i, ordinata in maniera arbitraria.

      prova, ci ho pensato molto di fretta e ci potrebbero essere cappelle.
    • Avatar
      ☺
      Scritto da
      suoranciata
      il 2010-03-24 20:17:00.0 alle 2010-03-24 20:17:00.0
      Trollate totali: 2013
      Re: Estrazione casuale da array
      Te la scrivo in pseudo-javascript, non credo che la sintassi sia corretta, ma spero si capisca il senso.

      //numeri da estrarre
var n = [1,2,3,4]
//Quantità di probabilità di ogni numero
var a = [0.50, 0.25, 0.25, 0];
//ogni b[i] è la somma di a[i] + b[i-1] o quasi
var b = [a[0], a[0]+a[1], a[0]+a[1]+a[2], a[0]+a[1]+a[2]+a[3] ];
//b = [0.50,0.75,1,1]

// == 1, è la somma di tutti i valori di a
var S = b[b.length-1];

var rndv = rnd()*S;    
for (int i=0;i<b.length;i++)
    if (b[i]>=rndv)
        return n[i];

      • Avatar
        Scritto da
        Non Autenticato
        il 2010-03-25 07:26:00.0 alle 2010-03-25 07:26:00.0
        Re: Estrazione casuale da array

        - Scritto da: suoranciata
        > Te la scrivo in pseudo-javascript, non credo che
        > la sintassi sia corretta, ma spero si capisca il
        > senso.
        >
        > 
        > //numeri da estrarre
> var n = [1,2,3,4]
> //Quantità di probabilità di ogni numero
> var a = [0.50, 0.25, 0.25, 0];
> //ogni b[i] è la somma di a[i] + b[i-1] o quasi
> var b = [a[0], a[0]+a[1], a[0]+a[1]+a[2],
> a[0]+a[1]+a[2]+a[3]
> ];
> //b = [0.50,0.75,1,1]
> 
> // == 1, è la somma di tutti i valori di a
> var S = b[b.length-1];
> 
> var rndv = rnd()*S;    
> for (int i=0;i<b.length;i++)
>     if (b[i]>=rndv)
>         return n[i];
>


        fammi capire, siamo sempre nell'algoritmo degli intervalli, ma tu anziché andare per sottrazioni di a(i) come pensai io, vai per cumulate. right right right?
    • Avatar
      ☺
      Scritto da
      Rin Kobayashi
      il 2010-03-24 20:27:00.0 alle 2010-03-24 20:27:00.0
      Trollate totali: 5425
      Re: Estrazione casuale da array
      > a(0) = 1/2
      > a(1) = 1/4
      > a(2) = 1/4
      > a(3) = 0

      Creo un nuovo array che mi contiene gli indici tante volte quanto più è alta la probabilità di estrarlo.

      [0, 0, 1, 2]

      Questo nuovo array ha per il terzo indice (3) zero probabilità di essere estratto. Per l'indice 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice 2 ha 1/4.

      L'estrazione poi procede con il random normale ma sull'array degli indici così creato.
      • Avatar
        Scritto da
        Non Autenticato
        il 2010-03-24 21:30:00.0 alle 2010-03-24 21:30:00.0
        Re: Estrazione casuale da array
        > > a(0) = 1/2
        > > a(1) = 1/4
        > > a(2) = 1/4
        > > a(3) = 0
        >
        > Creo un nuovo array che mi contiene gli indici
        > tante volte quanto più è alta la probabilità di
        > estrarlo.
        >
        > [0, 0, 1, 2]
        >
        > Questo nuovo array ha per il terzo indice (3)
        > zero probabilità di essere estratto. Per l'indice
        > 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice 2
        > ha 1/4.
        >
        > L'estrazione poi procede con il random normale ma
        > sull'array degli indici così creato.

        Non ho capito. Al momento sono stato catturato dall'idea degli intervalli e devo metabolizzare quella.
      • Avatar
        Scritto da
        Non Autenticato
        il 2010-03-25 07:29:00.0 alle 2010-03-25 07:29:00.0
        Re: Estrazione casuale da array

        - Scritto da: Rin Kobayashi
        > > a(0) = 1/2
        > > a(1) = 1/4
        > > a(2) = 1/4
        > > a(3) = 0
        >
        > Creo un nuovo array che mi contiene gli indici
        > tante volte quanto più è alta la probabilità di
        > estrarlo.
        >
        > [0, 0, 1, 2]
        >
        > Questo nuovo array ha per il terzo indice (3)
        > zero probabilità di essere estratto. Per l'indice
        > 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice 2
        > ha
        > 1/4.
        >
        > L'estrazione poi procede con il random normale ma
        > sull'array degli indici così
        > creato.

        come fai per p non razionali?

        tipo a(2)= PI
        o banalmente anche con numeri razionali a infinite cifre decimali, tipo
        a(2)= 1/3
        • Avatar
          Scritto da
          Non Autenticato
          il 2010-03-25 10:25:00.0 alle 2010-03-25 10:25:00.0
          Re: Estrazione casuale da array
          > come fai per p non razionali?

          Il problema non si pone, perché i numeri usati da un calcolatore hanno un numero finito di cifre decimali. GS
          • Avatar
            Scritto da
            Non Autenticato
            il 2010-03-25 12:14:00.0 alle 2010-03-25 12:14:00.0
            Re: Estrazione casuale da array

            - Scritto da:
            > > come fai per p non razionali?
            >
            > Il problema non si pone, perché i numeri usati da
            > un calcolatore hanno un numero finito di cifre
            > decimali.
            > GS


            questo lo dici te, esistono dei formati di dati per memorizzare numeri razionali a cifre decimali infinite, ad esempio memorizzandolo sotto forma di frazioni.
            • Avatar
              Scritto da
              Non Autenticato
              il 2010-03-25 15:09:00.0 alle 2010-03-25 15:09:00.0
              Re: Estrazione casuale da array
              > > > come fai per p non razionali?
              > >
              > > Il problema non si pone, perché i numeri usati
              > da
              > > un calcolatore hanno un numero finito di cifre
              > > decimali.
              > > GS
              >
              >
              > questo lo dici te, esistono dei formati di dati
              > per memorizzare numeri razionali a cifre decimali
              > infinite, ad esempio memorizzandolo sotto forma
              > di
              > frazioni.

              Frazioni, quindi numeri razionali. La domanda parlava di numeri irrazionali.

              Anche usando bc che esegue calcoli con precisione illimitata, un numero irrazionale sarà approssimato per forza con un numero finito di cifre decimali.

              Per probabilità del tipo 1/q il metodo dell'esplosione dell'array è semplice, e può essere generalizzato per p/q. Nel contesto in cui mi interessa, le probabilità derivano da calcoli e sono sempre numeri razionali.

              Però, come già osservato, nel caso di un array di partenza molto grande, esploderlo richiede risorse macchina non indifferenti.
              • Avatar
                Scritto da
                Non Autenticato
                il 2010-03-25 18:31:00.0 alle 2010-03-25 18:31:00.0
                Re: Estrazione casuale da array

                - Scritto da:
                > > > > come fai per p non razionali?
                > > >
                > > > Il problema non si pone, perché i numeri usati
                > > da
                > > > un calcolatore hanno un numero finito di cifre
                > > > decimali.
                > > > GS
                > >
                > >
                > > questo lo dici te, esistono dei formati di dati
                > > per memorizzare numeri razionali a cifre
                > decimali
                > > infinite, ad esempio memorizzandolo sotto forma
                > > di
                > > frazioni.
                >
                > Frazioni, quindi numeri razionali. La domanda
                > parlava di numeri
                > irrazionali.
                >
                > Anche usando bc che esegue calcoli con precisione
                > illimitata, un numero irrazionale sarà
                > approssimato per forza con un numero finito di
                > cifre
                > decimali.
                >
                > Per probabilità del tipo 1/q il metodo
                > dell'esplosione dell'array è semplice, e può
                > essere generalizzato per p/q. Nel contesto in cui
                > mi interessa, le probabilità derivano da calcoli
                > e sono sempre numeri
                > razionali.
                >
                > Però, come già osservato, nel caso di un array di
                > partenza molto grande, esploderlo richiede
                > risorse macchina non
                > indifferenti.

                è un algoritmo da veri dementi
        • Avatar
          ☺
          Scritto da
          Rin Kobayashi
          il 2010-03-25 12:35:00.0 alle 2010-03-25 12:35:00.0
          Trollate totali: 5425
          Re: Estrazione casuale da array

          - Scritto da:
          >
          > - Scritto da: Rin Kobayashi
          > > > a(0) = 1/2
          > > > a(1) = 1/4
          > > > a(2) = 1/4
          > > > a(3) = 0
          > >
          > > Creo un nuovo array che mi contiene gli indici
          > > tante volte quanto più è alta la probabilità di
          > > estrarlo.
          > >
          > > [0, 0, 1, 2]
          > >
          > > Questo nuovo array ha per il terzo indice (3)
          > > zero probabilità di essere estratto. Per
          > l'indice
          > > 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice 2
          > > ha
          > > 1/4.
          > >
          > > L'estrazione poi procede con il random normale
          > ma
          > > sull'array degli indici così
          > > creato.
          >
          > come fai per p non razionali?
          >
          > tipo a(2)= PI
          > o banalmente anche con numeri razionali a
          > infinite cifre decimali,
          > tipo
          > a(2)= 1/3

          Ovviamente l'algoritmo è adatto solo ai casi più semplici. Non funziona nel continuo e nonappena le probabilità si fanno "incasinate" comincia a diventare "costoso" in termini di spazio in memoria usato per memorizzare l'array degli indici. Da qualche parte ho letto circa un metodo che usava gli alberi binari pesati per memorizzare i valori da estrarre ma non ricordo nulla a riguardo.
      • Avatar
        Scritto da
        Non Autenticato
        il 2010-03-25 08:39:00.0 alle 2010-03-25 08:39:00.0
        Re: Estrazione casuale da array

        - Scritto da: Rin Kobayashi
        > > a(0) = 1/2
        > > a(1) = 1/4
        > > a(2) = 1/4
        > > a(3) = 0
        >
        > Creo un nuovo array che mi contiene gli indici
        > tante volte quanto più è alta la probabilità di
        > estrarlo.
        >
        > [0, 0, 1, 2]
        >
        > Questo nuovo array ha per il terzo indice (3)
        > zero probabilità di essere estratto. Per l'indice
        > 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice 2
        > ha
        > 1/4.
        >
        > L'estrazione poi procede con il random normale ma
        > sull'array degli indici così
        > creato.

        approved, ottimo algoritmo
        • Avatar
          Scritto da
          Non Autenticato
          il 2010-03-25 12:15:00.0 alle 2010-03-25 12:15:00.0
          Re: Estrazione casuale da array

          - Scritto da:
          >
          > - Scritto da: Rin Kobayashi
          > > > a(0) = 1/2
          > > > a(1) = 1/4
          > > > a(2) = 1/4
          > > > a(3) = 0
          > >
          > > Creo un nuovo array che mi contiene gli indici
          > > tante volte quanto più è alta la probabilità di
          > > estrarlo.
          > >
          > > [0, 0, 1, 2]
          > >
          > > Questo nuovo array ha per il terzo indice (3)
          > > zero probabilità di essere estratto. Per
          > l'indice
          > > 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice 2
          > > ha
          > > 1/4.
          > >
          > > L'estrazione poi procede con il random normale
          > ma
          > > sull'array degli indici così
          > > creato.
          >
          > approved, ottimo algoritmo


          palle fa schifo ha un'efficienza ridicola
          • Avatar
            ☺
            Scritto da
            Rin Kobayashi
            il 2010-03-25 12:16:00.0 alle 2010-03-25 12:16:00.0
            Trollate totali: 5425
            Re: Estrazione casuale da array

            - Scritto da:
            >
            > - Scritto da:
            > >
            > > - Scritto da: Rin Kobayashi
            > > > > a(0) = 1/2
            > > > > a(1) = 1/4
            > > > > a(2) = 1/4
            > > > > a(3) = 0
            > > >
            > > > Creo un nuovo array che mi contiene gli indici
            > > > tante volte quanto più è alta la probabilità
            > di
            > > > estrarlo.
            > > >
            > > > [0, 0, 1, 2]
            > > >
            > > > Questo nuovo array ha per il terzo indice (3)
            > > > zero probabilità di essere estratto. Per
            > > l'indice
            > > > 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice
            > 2
            > > > ha
            > > > 1/4.
            > > >
            > > > L'estrazione poi procede con il random normale
            > > ma
            > > > sull'array degli indici così
            > > > creato.
            > >
            > > approved, ottimo algoritmo
            >
            >
            > palle fa schifo ha un'efficienza ridicola

            Non piace neanche a me, però è semplice da implementare e finché l'array da cui estrarre gli oggetti ha piccole dimensioni fa il suo lavoro.
          • Avatar
            Scritto da
            Non Autenticato
            il 2010-03-25 12:27:00.0 alle 2010-03-25 12:27:00.0
            Re: Estrazione casuale da array

            - Scritto da:
            >
            > - Scritto da:
            > >
            > > - Scritto da: Rin Kobayashi
            > > > > a(0) = 1/2
            > > > > a(1) = 1/4
            > > > > a(2) = 1/4
            > > > > a(3) = 0
            > > >
            > > > Creo un nuovo array che mi contiene gli indici
            > > > tante volte quanto più è alta la probabilità
            > di
            > > > estrarlo.
            > > >
            > > > [0, 0, 1, 2]
            > > >
            > > > Questo nuovo array ha per il terzo indice (3)
            > > > zero probabilità di essere estratto. Per
            > > l'indice
            > > > 0 ha 1/2, per l'indice 1 ha 1/4, per l'indice
            > 2
            > > > ha
            > > > 1/4.
            > > >
            > > > L'estrazione poi procede con il random normale
            > > ma
            > > > sull'array degli indici così
            > > > creato.
            > >
            > > approved, ottimo algoritmo
            >
            >
            > palle fa schifo ha un'efficienza ridicola

            è semplice, chiaramente corretto e anche veloce una volta inizializzato. L'efficienza nello storage qui è un aspetto del tutto secondario.
<softv>

Pagina generata in 87 millisecondi

Utenti attivi: 8 nell'ultimo minuto, 19 negli ultimi cinque minuti, 35 negli ultimi 15 minuti