+ Rispondi al Thread
Pagina 1 di 2 12 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 13

Discussione: Estrazioni Casuali

  1. #1
    Skary non è in linea Scolaretto
    Post
    331

    Estrazioni Casuali

    Salve a tutti

    E' un pò che ci rifletto su , ma non riesco a trovare una risposta che mi piaccia.

    Dunque :

    Se vuoi dovreste scrivere un programma che estrae un numero bello grande di numeri casuali unici (es 10^8) nel minor tempo possibile , come fareste ?

    Fino ad ora ho letto di algoritmi che estraggono l'indice di un array che va da 0 a N e che contiene tutti i numeri da 0 a N e mano a mano che estrae viene accorciato , ma è una cosa ingestibile per un numero elevato di estrazioni...

    Allo stesso modo continuare ad estrarre fino a che non esce un numero che non era mai uscito prima è qualocsa di fuori di testa in casi come questo.

    Altri algoritmi non mi vengono in mente , voi sapete se questo problema ha soluzione ?

  2. #2
    L'avatar di Brontolo
    Brontolo non è in linea Very Important Person
    Post
    2,282
    Sbaglio o ti stai ripetendo?
    VB6 Rnd()

    Una rapida ricerca nel forum ti presenterà decine di risultati sull'argomento, tra cui anche roba tua.
    Il regolamento del forum: la prima cosa da leggere.

  3. #3
    Skary non è in linea Scolaretto
    Post
    331
    Quote Originariamente inviato da Brontolo Visualizza il messaggio
    Sbaglio o ti stai ripetendo?
    VB6 Rnd()

    Una rapida ricerca nel forum ti presenterà decine di risultati sull'argomento, tra cui anche roba tua.
    In effetti la domanda mi era ventua riguardando e tentando di sviluppare un mio vecchio programma , ma non avevo mai affrontato questa parte del probelma e dalla ricerca che avevo fatto avevo trovato solo questa risposta :
    http://forum.masterdrive.it/ms-offic...etizi-ni-6048/

    anche su altri siti trovo solo risposte simili.

    Comuque no non mi riferivo a quel problema nello specifico (intendo quello che mi hai linkato tu e non quello che ho linkato io , poiche alla fine ho trovato che quella libreria , Melix qualcosa , che era crittograficamente sicura e quindi all'altezza delle mie eisgenze) la questione in questo caso coinvolge i numeri causuali , ma sono solo parte dell'algoritmo e non parte del problema , il problema è l'algoritmo.

    Il punto è che per esempio se io volessi randomizzare l'esecuzione di una playlist di 100 canzoni facendo in modo che le canzoni vengano eseguite 1 sola volta come posso fare facendo si che l'algoritmo sia il più veloce in assoluto ? (questa è un interpretazione del problema che ponevo).

    Il problema nella forma più generale era semplicemente , se devo estrarre (solo una volta) tutti i numeri appartenenti ad un intervallo numerico grande a sufficenza da non poter essere contenuto in memoria come faccio ?

    Perchè fin ora ho visto che se ad esempio si devono estrarre una volta soltanto numeri compresi tra 1 e 100 uno può tenerli in memoria in un array e ad ogni nuova estrazione controllare se sono presenti nell'array , se si l'estrazione si ripete (ovvio però che quando mancherà soltanto un numero è probabile che si facciano 99 estrazioni a vuoto , e questo in primis è un inefficenza ed in secondo luogo se l'intervallo numerico è superiore alla memoria disponibile la soluzione non è praticabile).

    Oppure potrei crearmi un array con tutti i numeri dell'intervallo ed estrarre i loro indici casualmente e ciò sarebbe buona cosa se l'intervallo è piccolo , altrimenti si satura la memoria.

    Come dicevo prima mi son messo a riflettere sul fatto che una soluzione a questo possa esistere o meno , e fin ora ho trovato una soluzione , ma che non mi ispira :

    1) dividere il grande intervallo in tanti piccoli sottointervalli gestibili in memoria estrarre casualmente un indice di un array che identifica un intervallo piccolo , caricare un altro array con dentro l'intervallo piccolo ed esaurire quell'intervallo con le estrazioni casuali poi passare al successivo , dovrebbe funzionare , ma la casualità mi pare limitata in quanto alla fin delle finite dopo la prima estrazione di sa che le N successive apparterranno a quelli intervallo.

    Quindi domandavo a voi se avevato un idea di come si possa risolvere un problema di questo genere ; perchè più ci penso e più inizio a convincermi che non esiste una soluzione bella pulita.

    Grazie in anticipo e scusate se la domanda è assurda , ma era un dubbio che mi ha preso in questi giorni ed anche se probabilmente non è fondamentale mi incuriosiva.
    Ultima modifica di Skary; 26-05-2010 12:50 

  4. #4
    L'avatar di Brontolo
    Brontolo non è in linea Very Important Person
    Post
    2,282
    Capisco che devi proprio essere allergico alle ricerche. Il link che ti ho segnalato era soltanto uno dei numerosi esistenti, per parlare anche solo di questo forum, che trattano l'argomento.
    Per esempio qui:
    Generatore di numeri casuali REALI
    avevi avuto la fortuna di usufruire di una consulenza (gratuita!) di M.A.W.

    Per parte mia, oggi come all'epoca, continuo a non trovare giustificata questa presunta necessità di conservare in memoria contemporanemente tutti i numeri estraibili.

    Mi è anche oscuro (ma pazienza!) il motivo per cui ti occorra l'... algoritmo più veloce del west semplicemente per randomizzare una playlist musicale.
    Il regolamento del forum: la prima cosa da leggere.

  5. #5
    Skary non è in linea Scolaretto
    Post
    331
    Quote Originariamente inviato da Brontolo Visualizza il messaggio
    Capisco che devi proprio essere allergico alle ricerche. Il link che ti ho segnalato era soltanto uno dei numerosi esistenti, per parlare anche solo di questo forum, che trattano l'argomento.
    Per esempio qui:
    Generatore di numeri casuali REALI
    avevi avuto la fortuna di usufruire di una consulenza (gratuita!) di M.A.W.

    Per parte mia, oggi come all'epoca, continuo a non trovare giustificata questa presunta necessità di conservare in memoria contemporanemente tutti i numeri estraibili.

    Mi è anche oscuro (ma pazienza!) il motivo per cui ti occorra l'... algoritmo più veloce del west semplicemente per randomizzare una playlist musicale.
    è evidente che mi stò perdendo in un bicchiere d'acqua e chiedo scusa se disturbo per nulla ( ) , ma non riesco proprio a vedere il nesso tra quelle discussioni e il problema che ponevo.

    Cioè da quello che ho letto in quelle disucssioni si parla di algoritmi per generare numeri pseudocasuali crittograficamente sicuri , o algoritmi proposti da MAW per risolverre il problema dello zaino di fabel.
    Nelle altre discussioni che avevo trovato avevo visto solo soluzioni con array o collection (in memoria) che come dicevo prima diventa inadeguato per un gran numero di estrazioni.

    E l'esempio della playlist era solo un esempio per rendere più concreto il problema.

    Mi spiace aver fatto la figura del menefreghista che scrive senza nemmeno fare le dovute ricerche , il fatto però è che questa curiosità mi si è posta poichè recentemente fabel è riuscito a finire il programma e mi ha passato una copia per darci un occhiata ; e da li mi sono domandato cosa sarebbe successo applicando algoritmi più sofisticati (inveche che il modello di Dawkins base) ed è proprio quest ultimo (il modello di Dawkins) il famoso programma che dicevo stavo riguardando confrontandolo con quel poco che riscivo a capire di algoritmi simili ma più complessi come il smulated annealing o l'RTS.

    E forse follemente , pensavo che se si eliminassero le generazioni già avvenute (senza cancellarle perchè in una blacklist e nemmeno facendo tutte le generazioni possibili in un array da cui estrarre casualmente) , allora forse l'algoritmo sarebbe migliorato in velocità.

    In realtà avevo in mente anche un altro paio di modifiche ma non avevo intenzione di fare questa digressione , in quanto come già detto in quella famosa discussione , essendo che io la matematica non la mastico molto bene , non volevo correre il rischio di farvi ridere a crepapelle.

    Detto questo in che modo non riesci a trovare giustificata questa presunta necessità di conservare in memoria contemporanemente tutti i numeri estraibili ? come faresti tu ad estrarre ad esempio tutti i numeri compresi tra 1 e 10000000000 una e una sola volta (in ordine sparso si intende)?

    Grazie per la pazienza e qual'ora dovessi reputare inutile proseguire la discussione dimmelo pure che non c'è problema per me a chiudere e a non farvi perdere tempo (mi rendo conto che questi sono abbozzi elementari che io da amatore ho buttato li per cercare una soluzione che magari è pure banale o inutile).

  6. #6
    Post
    2,255
    Blogs
    6
    Hai valutato l'idea di appoggiarti al Disco magari tramite un DB ?

    Detto questo, non è sempre possibile ottenere delle prestazioni "accettabili" con i calcolatori di uso "comune".

    Bisogna trovare il giusto compromesso tra le risorse Hardware ed i tempi di esecuzione.
    NB: Per copiare il codice inserito con il SyntaxHighlighter (codice colorato con numeri di riga a fianco), prima si deve eseguire un DoppioClick sul codice e successivamente copiarne il contenuto, altrimenti si avranno problemi di Formattazione
    ___
    VB.Net: {Extension Methods} {Lambda Expressions} {BinaryFormatter} {GetExternalIp} {CustomBinding}
    HowTo: {Windows 7 - Installare il Sistema su C e la cartella Users su D}{Windows 7 - Spostare la cartella Users su altra Partizione}
    Blog: {Fix's Blog}

  7. #7
    L'avatar di Brontolo
    Brontolo non è in linea Very Important Person
    Post
    2,282
    Quote Originariamente inviato da Skary Visualizza il messaggio
    Detto questo in che modo non riesci a trovare giustificata questa presunta necessità di conservare in memoria contemporanemente tutti i numeri estraibili ?
    Non conosco algoritmi sofisticati, quindi supponiamo di adottare l' algoritmo banale rappresentato dal sacchetto dei numeri della tombola: i numeri esistono tutti "a priori" e via via che vengono estratti vengono eliminati dalla lista iniziale.

    L'implementazione informatica prevederebbe una sequenza indicizzata di 90 elementi (array, vettore, collection ...) ognuno dei quali valorizzato con un numero compreso nell'intervallo da 1 a 90 e ognuno con un valore diverso: il contenuto di ciascun elemento sarebbe uguale all'indice dell'elemento stesso, rendendo quindi inutile l'informazione rappresentata dal valore.
    D'altra parte l'unico scopo dell'esistenza "a priori" di questi elementi sarebbe solo quello di cancellarli (o annullarli in qualche modo) ad ogni estrazione, solo per verificare il loro stato di "già estratto". E' chiaro che al crescere del numero di elementi cresce l'occupazione di memoria, anche se, con gli ordini di grandezza delle RAM odierne, credo che occorrano numeri enormi per avere dei problemi.
    Si potrebbe al contrario pensare di registrare i numeri via via che vengono estratti e, se la RAM è un problema, utilizzare una memoria di massa che, in fin dei conti, è stata inventata anche per questo.

    Il regolamento del forum: la prima cosa da leggere.

  8. #8
    Skary non è in linea Scolaretto
    Post
    331
    Quote Originariamente inviato da Brontolo Visualizza il messaggio
    Non conosco algoritmi sofisticati, quindi supponiamo di adottare l' algoritmo banale rappresentato dal sacchetto dei numeri della tombola: i numeri esistono tutti "a priori" e via via che vengono estratti vengono eliminati dalla lista iniziale.

    L'implementazione informatica prevederebbe una sequenza indicizzata di 90 elementi (array, vettore, collection ...) ognuno dei quali valorizzato con un numero compreso nell'intervallo da 1 a 90 e ognuno con un valore diverso: il contenuto di ciascun elemento sarebbe uguale all'indice dell'elemento stesso, rendendo quindi inutile l'informazione rappresentata dal valore.
    Questo è vero per la prima estrazione , ma non lo è per le successive , infatti se si sceglie questo metodo il contenuto deve essere uguale alla prima estrazione es :

    codice:
    indice : 0  1  2  3  4  5
    valore : 0  1  2  3  4  5
    Casualmente estraggo l'elemento di indice 3 (posso estrarre da 0 a 5).
    Il primo numero della mia sequenza casuale è 3.
    Eliminino l'elemento di indice 3 e tutti i successivi vengono quindi scalati.
    Decremento di uno lo spazio entro cui posso estrarre.

    la situazione ora è
    codice:
    indice : 0  1  2  3  4
    valore : 0  1  2  4  5
    Casualmente estraggo ancora l'elemento di indice 3
    il secondo numero della mia sequenza è 4 e non 3 , quindi nell'array bisogna effettivamente scrivere qualcosa.

    Quote Originariamente inviato da Brontolo Visualizza il messaggio
    D'altra parte l'unico scopo dell'esistenza "a priori" di questi elementi sarebbe solo quello di cancellarli (o annullarli in qualche modo) ad ogni estrazione, solo per verificare il loro stato di "già estratto".
    Se ci si limitasse semplicemente a verificare se è già stato estratto invece che di far scorrere l'array di valori , si finirebbe per fare un sacco di estrazioni a vuoto ( di elementi già estratti ) quando da estrarne ne restano pochi rispetto ai numeri a disposizione.

    Quote Originariamente inviato da Fix918 Visualizza il messaggio
    Hai valutato l'idea di appoggiarti al Disco magari tramite un DB ?

    Detto questo, non è sempre possibile ottenere delle prestazioni "accettabili" con i calcolatori di uso "comune".

    Bisogna trovare il giusto compromesso tra le risorse Hardware ed i tempi di esecuzione.
    Quote Originariamente inviato da Brontolo Visualizza il messaggio
    E' chiaro che al crescere del numero di elementi cresce l'occupazione di memoria, anche se, con gli ordini di grandezza delle RAM odierne, credo che occorrano numeri enormi per avere dei problemi.
    Si potrebbe al contrario pensare di registrare i numeri via via che vengono estratti e, se la RAM è un problema, utilizzare una memoria di massa che, in fin dei conti, è stata inventata anche per questo.

    A quanto pare si questo è l'unica possibilità , peccato , mi sa che dovrò lasciar perdere (perchè facendo così le ci perdo invece di risparmiare tempo) e cercare un altro modo per ottimizzare.

  9. #9
    L'avatar di bottomap
    bottomap non è in linea Moderatore Globale
    Post
    4,097
    Ciao,

    Per quanto riguarda il discorso delle "estrazioni a vuoto", puoi facilmente evitare la cosa prevedendo un contenitore che si adatti al numero di elementi contenuti.

    Certo la cosa può avere un overhead relativo, ma utilizzando strutture dati appropriate non rischi la necessità di randomizzare un quantitaivo enorme di numeri per ottenere l'unico rimasto.
    Il problema si sposta all'individuazione una struttura dati che sia efficiente per il tipo di operazione che hai biosgno di effettuare (sarebbe preferibile non dover ricompattare tutto - come potrebbe succedere con un array - a seguito di un'estrazione, ma anche l'accesso diretto agli elementi, per l'operazione di estrazione, sarebbe da auspicare).

    Quello di cui hai bisogno è un Set (ossia un insieme non ordinato di elementi univoci). Le implementazioni possono essere le più disparate, come puoi leggere qui: Set (informatica) - Wikipedia.
    A seconda dei linguaggi utilizzati, puoi trovare la cosa anche a "costo zero" (in Java ad esempio esiste la comoda interfaccia di nome, appunto, Set, con varie implementazioni - HashSet, LinkedHashSet, TreeSet).

    Chiaramente se il numero degli elementi è veramente enorme l'approccio con contenitore tende ad essere controproducente, ma a naso non vedo nient altro che possa tener traccia dei numeri già estratti (il consiglio di appoggiarsi al disco è forse il più sensato in questo caso).

    Un approccio più drastico potrebbe essere, in presenza di un numero molto alto di elementi, di frammentare il dominio in una serie di parti (evetnualmente frammentabili ulteriormente), l'estrazione sarebbe rappresentata dalla generazione di più numeri random (indici a vari sottinsiemi). In sostanza una tupla <x1...xn> di indici sempre più specifici. Non guadagneresti molto in termini di storico (la memorizzazione della tupla estratta comunque richiede spazio), ma forse puoi guadagnare qualcosa dal fatto che il dominio è stato partizionato a priori.

    Ciaociao
    Ultima modifica di bottomap; 27-05-2010 15:27 


    Venite a farmi un saluto su http://www.bottomap.com/

    - Come porre domande in modo intelligente
    - Hai mai dato un'occhiata al
    Regolamento del Forum? Se la risposta è no, sarebbe proprio l'ora di farlo...
    - Il Crossposting è vietato dalla Netiquette.

    "Solo Puffin ti darà forza e grinta a volontà" - Charlie O'Brian
    "I gatti sono animali verso cui ho il massimo rispetto. I gatti e i non conformisti mi sembrano davvero i soli esseri in questo mondo che abbiano una coscienza pratica e attiva" - Jerome K. Jerome
    "Dun Dun DUNNN!" - Capitan Caos
    (per chiunque se lo fosse mai chiesto, il nick Bottomap è volutamente sgrammaticato)

  10. #10
    Skary non è in linea Scolaretto
    Post
    331
    Grazie bottomap

    Ho fatto un pò di ricerche sui set e mi è saltato fuori un link che riguarda i bloom filter che pare essere prorprio ciò che mi serve , ora mi documento un pò.

    Grazie ancora

+ Rispondi al Thread
Pagina 1 di 2 12 ultimoultimo

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi