Creation de tableau d'indice aléatoire, version plus rapide

[invite97ba6c10]

bonjour à tous!

Je sollicite votre aide pour un petit problème que je n'arrive pas à résoudre.

Je suis en train de créer un programme en fortran 95, sur un domaine d'astrophysique. Pour faire simple, j'ai un tableau de N particules, référencés par l'indice du tableau, et je souhaite en sélectionner M, de manière totalement aléatoire, et non redondante. Qui plus est, il faut une méthode, efficace, rapide.

Pour l'instant voici ce que je fait :


_______________________Aléatoi re vraiment aléatoire____________

ubroutine init_random_seed()
	integer :: i, n, clock
	integer, dimension(:), allocatable :: seed
	
	call random_seed(size = n)
	allocate(seed(n))
	
	call system_clock(count=clock)
	
	seed = clock + 37 * (/ (i - 1, i = 1, n) /)
	call random_seed(PUT = seed)
	
	deallocate(seed)
end subroutine

_____________________puis dans ma routine de calcul_____________

      do j=1,threshold
					call random_number(random)
					random_index=int(aint(mass_halo(i)*random))+1
					random_index_arr(j)=random_index
					
	enddo

et par la suite, je retire les redondance

test = .true.
do while (test)
	do j=1,threshold
		do l=j+1,threshold
			if (random_index_arr(l) == random_index_arr(j)) then
				if (random_index_arr(j) < mass_halo(i)) then
					call random_number(random)
					random_index=int(aint(mass_halo(i)*random))+1
					random_index_arr(l)=random_index
				endif
			endif
		enddo
		
	enddo
	do j=1,threshold
		do l=j+1,threshold
			test=.false.
			if (random_index_arr(l) == random_index_arr(j)) then
				test=.true.
			endif
		enddo
	enddo
enddo

Le problème, c'est que c'est très, très, vraiment très lent.
Et je ne vois plus vraiment comment optimiser. Je suis donc ouvert à toute suggestion. J'ai aussi pensé trier mon tableau, mais le fait est qu'il peut avoir plus d'1M d'élement, est-ce jouable avec des tris en n.ln(n)?

Je vous tiens au courant, si j'ai d'autre idée, qui sait, ça servira peut être à quelqu'un.

Merci par avance!
-----

[invite97ba6c10]

Désolé pour le second message, pour un sujet sur les doublons, ça fait mal vu, je n'ai pas vu de bouton EDIT, afin de réediter mon message.

je m'adresse aux modérateurs du forum, je me suis rendu compte que mon post n'était pas dans la bonne section, donc si on pouvais le deplacer au lieu d'en recréer un, ce serait mieux.

Encore mille excuses.

[invite15928b85]

Bonjour.

La lenteur constatée est sans doute liée à la phase d'élimination des doublons. Il faut donc ne pas en générer.

Une idée :

générer un tableau A de N entiers initialisés à 1
préparer un tableau vide B de M entiers.

pour m = 1 à M
générer un entier aléatoire n compris entre 1 et N
si A(n) différent de 0
alors
B(m) = n
A(n) = 0
m = m+1

A la fin, B contient M entiers compris entre 1 et N, sans doublon. A (n) passe de 1 à 0 quand n est généré une première fois et ne peut plus être réutilisé en raison du test A(n) différent de 0.

Cordialement,

[invite97ba6c10]

Tout d'abord, merci de répondre aussi vite.

J'ai toute suite réagis sur votre idée partant de "Il faut donc ne pas en générer."

je ne suis pas sur que de manipuler un tableau uniquement pour savoir si on est bon soit judicieux, mais l'idée de base me semble bonne.
Ce que je fait finalement:

1) je choisis un seuil max Nmax, et un seuil de particule Npart inférieur au seuil max.
Il me faut maintenant trouver Npart aléatoirement parmi les N initiales, uniquement si le nombre de particules N est plus grand que Nmax. De plus, j'oblige Npart<<Nmax. Vu le nombre de particule que j'ai, la statistique sera bonne.

2)Pour la méthode, je fais maintenant

                               do j=1,threshold_calc
					test=.true.
					do while (test)
						call random_number(random)
						random_index=int(aint(mass_halo(i)*random))+1
						test=.false.
						do l=1,j
							if (random_index==random_index_arr(l)) then
								test=.true.
							endif
						enddo
					enddo
					random_index_arr(j)=random_index
				enddo

avec threshold_calc le nombre de particule que j'ai à trouvé =!=Npart.

Le fait est, dans ma méthode comme dans la votre, que le temps sera dautant plus grand que Nmax sera proche de Npart, compréhensible car il faudra trouver une séquence de moins en moins probable.

Si d'autres idées arrivent, je reste ouvert, mais je considère mon problème comme résolu.

Cordialement.

Edit: je peux éditer mes messages secondaires, mais pas le message principal, j'imagine que c'est du pour une plus grande facilité de suivi du sujet, mais c'est quand même peut pratique!

[A voir en vidéo sur Futura]

[invite2d7144a7]

Bonjour,

La condition "de manière totalement aléatoire" n'existe pas si tu génères les valeurs de manière purement logicielle, quelle que soit la qualité de ton générateur.

[invite97ba6c10]

Disons que si je relance mon programme, le ker sera différent, et donc j'aurais une série différente.

Effectivement, si l'aléatoire venait à prendre le pas sur l'informatique, surement assisterons-nous à quelque chose de nouveaux (peut être la vie).

PS : après test de stabilité du programme sur des grands runs, il s'avère que le choix de Nmax et Npart doit être finementtrouvé par l'utilisateur pour avoir suffisamment de statistique et une assez grande vitesse. Mais qui n'en est pas là en astrophysique!