Problème avec Random et Threads dans .NET

Question

J'ai des problèmes avec la classe Random dans .NET, j'implémente une collection threadée qui fonctionne bien, sauf pour un détail plus petit. La collection est un Skip list et ceux d'entre vous qui le connaissent savent que pour chaque nœud inséré, je dois générer une nouvelle hauteur qui est <= CurrentMaxHeight+1, voici le code que j'utilise pour le faire (je sais que c'est très inefficace, mais ça marche et c'est ma priorité maintenant)

int randomLevel() 
{ 
    int height = 1; 

    while(rnd.NextDouble() >= 0.5 && height < MaxHeight) 
    ++height; 

    return height; 
} 

mon problème est que parfois je continue à obtenir seulement 1 retour de cela pour plusieurs milliers d'éléments dans une rangée qui tue les performances de la liste de saut. La chance pour 10.000 éléments de générer seulement 1 de cette méthode dans une rangée, semble très mince (arrive assez régulièrement).

Je suppose donc (devinettes) qu'il ya un problème avec l'objet Random d'une certaine façon, mais je ne sais pas vraiment où commencer à creuser autour. Alors je me tourne vers stackoverflow pour voir si quelqu'un a une idée?

Modifier

La rnd variable est déclarée dans la classe SkipList<T>, et il est accessible à partir de plusieurs threads (chaque thread appelle .Add sur la collecte et ajouter des appels .randomLevel)

Answer 1

Essayez lock l'objet Random.

int RandomLevel() 
{ 
    int height = 1; 

    lock(rnd) 
    { 
     while(rnd.NextDouble >= 0.5 && height < MaxHeight) height++; 
    } 

    return height; 
} 

Il peut y avoir un problème avec les collisions lorsque plusieurs threads accéder à l'objet Random en même temps, et la graine peut être obtenir endommagé. Je ne peux donner aucun aperçu de ce qui pourrait se passer, mais selon le MSDN, les membres d'instance du type Random ne sont pas garantis d'être thread-safe, donc un lock semble nécessaire dans tous les cas.

Answer 2

Il semble que votre boucle tourne moins de la moitié du temps - c'est ce que vous cherchez (quand un nombre aléatoire entre 0 et 1 est> 0.5? Cela pourrait expliquer pourquoi vous obtenez "1 "plus souvent que vous ne le pensiez - au moins la moitié du temps, il ne lance même pas la boucle qui incrémente la hauteur - il définit simplement la hauteur à 1, ne la change pas, puis retourne" 1 ". Je ne suis pas trop familier avec les nombres aléatoires, mais est-il possible que vous ayez un problème d'ensemencement? Si vous êtes familier avec les listes de sauts, cela pourrait être intentionnel, mais je pensais que je demanderais:

ne randomise pas l'objet Random lorsque vous l'instanciez, il peut renvoyer un flux prévisible de nombres, au lieu de ceux qui sont vraiment aléatoires. r vous voyez ici, mais quelque chose à envisager d'aller de l'avant.

Answer 3

Je ne verrouillerais pas toute la boucle while. Verrouillez simplement les appels rnd.NextDouble().

int RandomLevel() 
{ 
    int height = 1; 
    double newRand; 

    lock(rnd) { newRand = rnd.NextDouble(); } 

    while(newRand >= 0.5 && height < MaxHeight) 
    { 
    height++; 
    lock(rnd) { newRand = rnd.NextDouble(); } 
    } 

    return height; 
} 

Bien que si la performance est une considération, je serais certainement comparer les deux solutions, car il pourrait y avoir une différence dans un seul thread par rapport à la performance multithread.