[c++] Generare milioni di numeri casuali univoci [Risolto subito Vict85+APa]

[Giova411]

#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
int
main ()
{
  vector < int > v (1000000);
  int r;
  bool ripeti = false;
  srand (time (NULL));		

  for (int i = 0; i < 1000000; i++)	
    {
      r = rand () % 2000000 + 1;	
      for (int c = 0; c < i; c++)	
	{
	  if (v[c] == r)
	    {			
	      ripeti = true;	
	      c = i;		
	    }
	}

       if (ripeti == true)	
	  i = i - 1;	 
       else		
	  v[i] = r;		
     ripeti = false;		
    }
  ofstream out ("prova.txt");
  for (int i = 0; i <1000000; i++)
    out << v[i] << " ";
  out << endl;
  return 0;
}

Volevo migliorare questo codice senza copiare, in rete, algoritmi noti (Knuth/Ruskey..) ma difficili.
Il codice riportato è "comprensibile" agli ignorantoni come me; ci mette mezz'ora (anche di più ) per generare un file con un milione di numeri che NON si ripetino.

[apatriarca]

Nella descrizione del problema originale si chiedeva che venissero generati \(N\) punti che avessero quelle proprietà. L'algoritmo dell'articolo suppone invece di voler riempire lo spazio preso in considerazione con un numero massimale di punti. La sua generazione di punti è quindi casuale, ma non è ben distribuita nel piano se ci si ferma prima di aver generato tutti i punti. Possiamo però usare comunque questo algoritmo, ammesso di essere poi disposti a fare un riordinamento casuale dei campioni generati. In effetti si può usare a questo punto una idea ancora più semplice.

Supponiamo di voler generare un insieme (finito) di valori casuali \( \{x_i\} \subset (a, b) \) tali che \( |x_i - x_j| > \epsilon \) per ogni coppia di valori e questo insieme è "massimale". Non deve cioè essere possibile inserire ulteriori valori mantenendo la condizione. Consideriamo quindi il sottointervallo \( (a, \min(a+\epsilon, b)). \) Siccome abbiamo supposto che il nostro insieme deve essere massimale, dovrà esserci un valore in questo sottointervallo. Uno solo perché ovviamente in caso contrario la condizione di distanza non potrebbe essere soddisfatta. Possiamo quindi generare un numero casuale in questo sottointervallo, chiamiamolo \(x_0\), e quindi seguire lo stesso procedimento per il restante sottointervallo \( (x_0 + \epsilon, b). \)

[Giova411]

Apa un po' capisco le tue indicazioni ma non mi oriento proprio su come si scrivono a livello di codice.
Non so se hai letto i post miei precedenti, ci ho provato ma non ho dimestichezza proprio
Mi serve una matrice, giusto?

[Giova411]

APa e Vic ho quella sensazione di aver lasciato in sospeso qualcosa qui...
Ovviamente volete aprirmi la capoccia, questo l'ho capito

Riassumo (PROVO). APa sta consigliando un metodo più semplice di quello che aveva proposto inizialmente.
Trovo un numero casuale (magari con la funzione semplice linkata da Vic?) in un intervallo dato \((a,b)\)
Dentro questo intervallo mi muovo grazie ad un \(\epsilon\) dato (che mi "garantisce" una distanza tra i numeri scelti?)
Si inzia col cercare \(x_0\) in un sottointervallo \( (a, \min(a+\epsilon, b)) \)
Poi itero continuo con \((x_0, min (x_0 + \epsilon, b) )\) ?

[apatriarca]

Siccome sto supponendo ora di generare abbastanza numeri da coprire l'intero intervallo, devo necessariamente avere un campione a distanza minore di \(\epsilon\) dal bordo dell'intervallo e dato un valore dovrò avere due valori, uno precedente e uno successivo con una distanza compresa tra \(\epsilon\) e \(2\epsilon\). Quindi per comodità li genero in ordine partendo dal bordo e poi considerando il successivo punto (generandolo con la distanza di cui ho parlato prima da quello precedente).

[apatriarca]

Te la sei cercata..

import random

def func(a, b, e):
    samples = []
    while a < b:
        lim = min(b, a + e)
        x = random.uniform(a, lim)
        samples.append(x)
        a = x + e
    return samples

samples = func(1, 5, 0.2)
diffs = [samples[i+1] - samples[i] for i in range(0, len(samples)-1) ]

print samples
print diffs

Un esempio di output:

[1.1060591613279958, 1.4937016153370881, 1.8309607732437594, 2.205855138012931, 2.414610618975913, 2.6790592599140246, 3.075306053958607, 3.3713030907266845, 3.6140107023199235, 3.8738858946676302, 4.163829868370242, 4.467338110985665, 4.796673624789376, 4.997159955207803]
[0.38764245400909236, 0.33725915790667127, 0.3748943647691716, 0.2087554809629819, 0.2644486409381117, 0.3962467940445822, 0.29599703676807776, 0.24270761159323895, 0.25987519234770673, 0.28994397370261193, 0.30350824261542275, 0.32933551380371107, 0.20048633041842745]

[Giova411]

AHAHAHAHAHHAHAHAHAHAHAHAHA!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Nooooooooooooooooooooooooooooooooooooooooooooo

Eh sì.... Per chi si fosse perso qualcosa, ho iniziato a bombardare APa di MP e mi ha punito con il codice di cui sopra. Si ringrazia ugualmente perché, didatticamente, è molto stimolante. GRAZIE

[apatriarca]

Comunque, a parte la riga in cui ho definito diffs, il resto è abbastanza semplice e facilmente traducibile in C++..

[Giova411]

E' Python, vero?

Cavolo com'é sintetico! E' di una stitichezza tale che mi fa ricordare le pilloline alle erbe che prende spesso mia nonna!

Sì, appena posso certo che lo faccio!!!!! Scherzi?! (Non finisce qui !!!!)
= P

PS:
Poi, quando ti farò IO da cicerone, mi devi dire quanti CA(beeeeeP!)O di linguaggi di programmazione conosci........