Moyen rapide de générer des bits pseudo-aléatoires avec une probabilité donnée de 0 ou 1 pour chaque bit

Question

Normalement, un générateur de nombre aléatoire renvoie un flux de bits pour laquelle la probabilité d'observer un 0 ou un 1 dans chaque position est égale (c'est à dire 50%). Appelons cela un impartiale PRNG.

J'ai besoin de générer une chaîne de caractère pseudo-aléatoire de bits avec la propriété suivante: la probabilité de voir un 1 dans chaque position p (la probabilité de voir un 0 est 1-p). Le paramètre p est un nombre réel entre 0 et 1; à mon problème, il arrive qu'il dispose d'une résolution de 0,5%, c'est à dire qu'il peut prendre les valeurs 0%, 0.5%, 1%, 1.5%, ..., 99.5%, 100%.

Notez que p est une probabilité et non une fraction exacte. Le nombre effectif de bits mis à 1 dans un flux de n bits doivent suivre la loi binomiale B(n, p).

Il y a une méthode naïve qui peut utiliser un estimateur sans biais GÉNÉRATEUR pour générer la valeur de chaque bit (pseudo-code):

generate_biased_stream(n, p):
  result = []
  for i in 1 to n:
    if random_uniform(0, 1) < p:
      result.append(1)
    else:
      result.append(0)
  return result

Une telle mise en œuvre est beaucoup plus lent que celui de la génération d'une impartiale des flux, puisqu'il utilise le générateur de nombre aléatoire de fonction une fois par chaque bit; tandis que l'impartialité du générateur de flux appelle une fois par taille de mot (par exemple, il peut générer de 32 ou 64 bits aléatoires, avec un seul appel).

Je veux une mise en œuvre plus rapide, même s'il sacrifices aléatoire légèrement. Une idée qui vient à l'esprit est de précalculer une table de recherche: pour chacun des 200 valeurs possibles de p, calculer C 8-bits des valeurs à l'aide du ralentissement de l'algorithme et de les enregistrer dans une table. Ensuite, l'algorithme rapide serait tout simplement choisir l'un de ces au hasard afin de générer 8 biaisée bits.

Un dos de l'enveloppe calcul pour voir combien de mémoire est nécessaire: C doit être d'au moins 256 (au nombre de 8 bits des valeurs), probablement plus pour éviter les effets d'échantillonnage; disons 1024. Peut-être le nombre varie en fonction de p, mais nous allons garder les choses simples et dire que la moyenne est de 1024. Depuis il y a 200 valeurs de p => total de l'utilisation de la mémoire est de 200 KO. Ce n'est pas mauvais, et peut tenir dans le cache L2 de 256 KO). J'ai encore besoin de l'évaluer pour voir si il y a d'échantillonnage effets introduire des biais, dans ce cas C devra être augmenté.

Une carence de cette solution est qu'elle peut générer, à seulement 8 bits à la fois, de même qu'avec beaucoup de travail, alors que l'impartialité du GÉNÉRATEUR peut générer 64 à la fois avec juste un peu d'arithmétique instructions.

Je voudrais savoir si il existe une méthode plus rapide, basé sur les opérations sur les bits au lieu de tables de recherche. Par exemple, la modification de la génération de nombre aléatoire directement le code à introduire un biais pour chaque bit. Cela permettrait d'obtenir la même performance que l'impartialité du PRNG.

---

Edit 5 Mars

Merci à vous tous pour vos suggestions, j'ai eu beaucoup d'idées intéressantes et de suggestions. Voici le top:

• Changer le problème, les exigences de sorte que p a une résolution de 1/256 au lieu de 1/200. Ceci permet d'utiliser des bits de façon plus efficace, et vous offre également plus de possibilités pour l'optimisation. Je pense que je peux faire ce changement.
• Utiliser le codage arithmétique à consommer efficacement bits à partir de l'impartialité du générateur. Avec la modification ci-dessus de résolution, cela devient beaucoup plus facile.
• Quelques personnes ont suggéré que PRNGs sont très rapides, donc en utilisant le codage arithmétique pourrait en fait rendre le code plus lent en raison de l'introduction de frais généraux. Au lieu de cela je doit toujours consommer le pire des cas, le nombre de bits et d'optimiser le code. Voir les indices de référence ci-dessous.
• @rici a suggéré d'utiliser SIMD. C'est une belle idée, qui ne fonctionne que si nous avons toujours consommer un nombre fixe de bits.

Référence (sans décodage arithmétique)

Remarque: comme beaucoup d'entre vous l'ont suggéré, j'ai changé la résolution de 1/200 à 1/256.

J'ai écrit plusieurs implémentations de la méthode naïve qui prend simplement 8 random impartiale bits et génère 1 peu biaisée:

• Sans SIMD
• Avec SIMD à l'aide de la Agner de la Brume vectorclass de la bibliothèque, comme suggéré par @rici
• Avec SIMD à l'aide de intrinsèques

J'utilise deux impartiale pseudo-générateurs de nombres aléatoires:

• xorshift128plus
• Ranvec1 (Mersenne Twister-like) à partir de Agner de la Brume de la bibliothèque.

J'ai aussi mesurer la vitesse de la neutralité PRNG à des fins de comparaison. Voici les résultats:

RNG: Ranvec1(Mersenne Twister for Graphics Processors + Multiply with Carry)

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 16.081 16.125 16.093 [Gb/s]
Number of ones: 536,875,204 536,875,204 536,875,204
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 0.778 0.783 0.812 [Gb/s]
Number of ones: 104,867,269 104,867,269 104,867,269
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 2.176 2.184 2.145 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 2.129 2.151 2.183 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

SIMD augmente les performances par un facteur 3 par rapport à la méthode scalaire. Il est 8 fois plus lent que la neutralité du générateur, comme prévu.

La manière la plus rapide biaisée générateur atteint 2,1 Go/s.

RNG: xorshift128plus

Method: Unbiased with 1/1 efficiency (incorrect, baseline)
Gbps/s: 18.300 21.486 21.483 [Gb/s]
Number of ones: 536,867,655 536,867,655 536,867,655
Theoretical   : 104,857,600

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 22.660 22.661 24.662 [Gb/s]
Number of ones: 536,867,655 536,867,655 536,867,655
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 1.065 1.102 1.078 [Gb/s]
Number of ones: 104,868,930 104,868,930 104,868,930
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 4.972 4.971 4.970 [Gb/s]
Number of ones: 104,869,407 104,869,407 104,869,407
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 4.955 4.971 4.971 [Gb/s]
Number of ones: 104,869,407 104,869,407 104,869,407
Theoretical   : 104,857,600

Pour xorshift, SIMD augmente les performances par un facteur 5 par rapport à la méthode scalaire. Il est 4 fois plus lent que la neutralité du générateur. Notez que c'est un scalaire de la mise en œuvre de xorshift.

La manière la plus rapide biaisée générateur atteint 4.9 Go/s.

RNG: xorshift128plus_avx2

Method: Unbiased with 1/1 efficiency (incorrect, baseline)
Gbps/s: 18.754 21.494 21.878 [Gb/s]
Number of ones: 536,867,655 536,867,655 536,867,655
Theoretical   : 104,857,600

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 54.126 54.071 54.145 [Gb/s]
Number of ones: 536,874,540 536,880,718 536,891,316
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 1.093 1.103 1.063 [Gb/s]
Number of ones: 104,868,930 104,868,930 104,868,930
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 19.567 19.578 19.555 [Gb/s]
Number of ones: 104,836,115 104,846,215 104,835,129
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 19.551 19.589 19.557 [Gb/s]
Number of ones: 104,831,396 104,837,429 104,851,100
Theoretical   : 104,857,600

Cette implémentation utilise AVX2 pour exécuter 4 impartiale xorshift générateurs en parallèle.

La manière la plus rapide biaisée générateur atteint 19.5 Go/s.

Des repères pour l'arithmétique de décodage

De simples tests montrent que l'arithmétique de décodage de code est le goulot d'étranglement, pas le PRNG. Donc je ne suis que l'analyse comparative la plus chère PRNG.

RNG: Ranvec1(Mersenne Twister for Graphics Processors + Multiply with Carry)

Method: Arithmetic decoding (floating point)
Gbps/s: 0.068 0.068 0.069 [Gb/s]
Number of ones: 10,235,580 10,235,580 10,235,580
Theoretical   : 10,240,000

Method: Arithmetic decoding (fixed point)
Gbps/s: 0.263 0.263 0.263 [Gb/s]
Number of ones: 10,239,367 10,239,367 10,239,367
Theoretical   : 10,240,000

Method: Unbiased with 1/1 efficiency (incorrect, baseline)
Gbps/s: 12.687 12.686 12.684 [Gb/s]
Number of ones: 536,875,204 536,875,204 536,875,204
Theoretical   : 104,857,600

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 14.536 14.536 14.536 [Gb/s]
Number of ones: 536,875,204 536,875,204 536,875,204
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 0.754 0.754 0.754 [Gb/s]
Number of ones: 104,867,269 104,867,269 104,867,269
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 2.094 2.095 2.094 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 2.094 2.094 2.095 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

La simple méthode du point fixe réalise 0.25 Go/s, tandis que les naïfs scalaire méthode est 3x plus rapide, et les naïfs SIMD méthode est 8x plus rapide. Il y a peut-être des moyens pour optimiser et/ou de paralléliser le calcul méthode de décodage de l'avant, mais en raison de sa complexité, j'ai décidé d'arrêter ici et de choisir le naïf SIMD mise en œuvre.

Merci à vous tous pour l'aide.

Answer 1

Une chose que vous pouvez faire est de l'échantillon de la base impartiale générateur à plusieurs reprises, l'obtention de plusieurs 32-bits ou 64-bits des mots, puis l'exécution d'un binaire arithmétique booléenne. Par exemple, pour les 4 mots - b1,b2,b3,b4, vous pouvez obtenir les distributions suivantes:

 expression | p(bit est à 1)
-----------------------+-------------
 b1 & b2 & b3 et b4 | 6.25%
 b1 & b2 & b3 | 12.50%
 b1 & b2 & b3 | b4) | 18.75%
 b1 & b2 | 25.00%
 b1 | b2 & b3 | b4)) | 31.25%
 b1 & b2 | b3) | 37.50%
 b1 & b2 | b3 | b4)) | 43.75%
 b1 | 50.00%

Les constructions analogues peuvent être faites pour des résolutions plus fines. Cela devient un peu fastidieux et nécessite encore plus générateur d'appels, mais au moins pas un pour bits. Ceci est similaire à a3f réponse, mais est probablement plus facile à mettre en œuvre et, je le soupçonne, plus rapide que l'analyse des mots pour 0xF nybbles.

Notez que pour votre choix de 0,5% de la résolution, vous avez besoin de 8 impartiale mots pour un biaisée mot, ce qui vous donne une résolution de (0.5^8) = 0.390625%.

Answer 2

Si vous êtes prêt à approximatives p basé sur 256 valeurs possibles, et vous avez un GÉNÉRATEUR qui peut générer des valeurs uniformes dans lequel les bits individuels sont indépendants les uns des autres, alors vous pouvez utiliser vectorisé comparaison de produire plusieurs biaisée de bits à partir d'un seul nombre aléatoire.

C'est seulement la peine de le faire si (1) vous vous inquiétez au sujet de nombres aléatoires de la qualité et (2) vous êtes susceptibles d'avoir besoin d'un grand nombre de bits avec le même parti pris. La deuxième exigence semble être implicites par la question d'origine, qui critique un projet de solution, comme suit: "Une carence de cette solution est qu'elle peut générer, à seulement 8 bits à la fois, de même qu'avec beaucoup de travail, alors que l'impartialité du GÉNÉRATEUR peut générer 64 à la fois avec juste un peu d'arithmétique instructions." Ici, l'implication semble être qu'il est utile de générer un grand bloc de biaisées bits en un seul appel.

De nombres aléatoires de la qualité est un sujet difficile. Il est difficile, sinon impossible, de mesurer, et donc des personnes différentes propose différentes statistiques qui mettent en valeur et/ou dévaloriser les différents aspects de "l'aléatoire". Il est généralement possible de faire des compromis vitesse de nombres aléatoires génération pour la basse "qualité"; si cela vaut la peine de faire dépend de votre application précise.

La plus simple possible des tests de nombre aléatoire de qualité impliquent la distribution des valeurs individuelles et la longueur du cycle de la génératrice. Standard des implémentations de la bibliothèque C rand et Posix random fonctions généralement passer les tests de distribution, mais la durée du cycle ne sont pas adaptés à un long-applications en cours d'exécution.

Ces générateurs sont généralement extrêmement rapide, cependant: la glibc mise en œuvre de l' random ne nécessite qu'un certain nombre de cycles, alors que le classique générateur linéaire à congruence (LCG) nécessite une multiplication et une addition. (Ou, dans le cas de la mise en œuvre de la glibc, trois de la ci-dessus pour générer de 31 bits.) Si c'est suffisant pour vos exigences de qualité, alors il ya peu de point en essayant d'optimiser, en particulier si le biais de la probabilité de changements fréquents.

Gardez à l'esprit que la durée du cycle devrait être beaucoup plus longue que le nombre d'échantillons prévu; idéalement, il devrait être plus grand que le carré de ce nombre, donc linéaire-générateur à congruence (LCG) avec un cycle de longueur 2³¹ n'est pas approprié, si vous vous attendez à générer des giga-octets de données aléatoires. Même la Gnu trinôme non linéaire additif-générateur de feedback, dont la longueur du cycle est revendiquée pour être d'environ 2³⁵, ne doit pas être utilisé dans des applications qui nécessitent des millions d'échantillons.

Un autre problème de qualité, ce qui est beaucoup plus difficile à tester, se rapporte à l'indépendance sur des échantillons consécutifs. Courte durée du cycle est complètement échouer sur cette mesure, parce qu'une fois que la répétition commence, à la génération de nombres aléatoires sont précisément en corrélation avec les valeurs historiques. La Gnu trinôme algorithme, bien que son cycle est plus long, a une corrélation claire comme un résultat du fait que la i^ème nombre aléatoire généré, r_i, est toujours l'un des deux valeurs r_i-3+r_je-31 ou r_i-3+r_je-31+1. Cela peut avoir de surprenant ou au moins déroutante conséquences, notamment avec les expériences de Bernoulli.

Voici une mise en œuvre à l'aide de Agner Brouillard est utile de vecteur de la bibliothèque de la classe, qui ne tient pas enlevé beaucoup de détails ennuyeux dans l'ESS intrinsèques, et aussi obligeamment fourni avec un rapide vectorisé générateur de nombre aléatoire (qui se trouve dans special.zip à l'intérieur de l' vectorclass.zip archive), ce qui nous permet de générer 256 bits à partir de huit appels à 256 bits du GÉNÉRATEUR. Vous pouvez lire le Dr Brouillard de l'explication de pourquoi il trouve même le Mersenne twister avoir des problèmes de qualité, et sa proposition de solution; je ne suis pas qualifié pour commenter, vraiment, mais elle permet au moins de donner les résultats escomptés dans la loi de Bernoulli expériences que j'ai essayé avec elle.

#include "vectorclass/vectorclass.h"
#include "vectorclass/ranvec1.h"

class BiasedBits {
  public:
    // Default constructor, seeded with fixed values
    BiasedBits() : BiasedBits(1)  {}
    // Seed with a single seed; other possibilities exist.
    BiasedBits(int seed) : rng(3) { rng.init(seed); }

    // Generate 256 random bits, each with probability `p/256` of being 1.
    Vec8ui random256(unsigned p) {
      if (p >= 256) return Vec8ui{ 0xFFFFFFFF };
      Vec32c output{ 0 };
      Vec32c threshold{ 127 - p };
      for (int i = 0; i < 8; ++i) {
        output += output;
        output -= Vec32c(Vec32c(rng.uniform256()) > threshold);
      }
      return Vec8ui(output);
    }

  private:
    Ranvec1 rng;
};

Dans mon test, qui a produit et qui a compté 268435456 bits dans 260 ms, ou un bit par ordre de la nanoseconde. La machine de test est un i5, donc il n'a pas AVX2; YMMV.

Dans le cas d'utilisation, 201 valeurs possibles pour p, le calcul de la 8-bits de valeurs de seuil sera fâcheusement imprécis. Si cette imprécision est indésirable, vous pouvez adapter la ci-dessus pour l'utilisation 16 bits seuils, le coût de production de deux fois plus de nombres aléatoires.

Sinon, vous pouvez à la main un rouleau de vectorisation, basé sur 10 bits seuils, ce qui vous donne une très bonne approximation de 0,5% par incréments, en utilisant le standard de manipulation de bits hack de faire le vectorisé seuil de comparaison, en cochant pour emprunter sur chaque bit 10 de la soustraction de vecteurs de valeurs et la répétition de seuil. Combiné avec, disons, std::mt19937_64, qui vous donnent une moyenne de six bits 64-bit nombre aléatoire.

Answer 3

À partir d'une information de la théorie du point de vue, un parti pris flux de bits (avec p != 0.5) a moins d'informations qu'un estimateur sans biais de flux, donc, en théorie, elle doit prendre (en moyenne) moins de 1 bit de l'impartial de l'entrée afin de produire un seul bit de la désinformation des flux de sortie. Par exemple, l' entropie d'une variable aléatoire de Bernoulli avec p = 0.1 est -0.1 * log2(0.1) - 0.9 * log2(0.9) bits, ce qui est autour de 0.469 bits. Cela suggère que, pour le cas p = 0.1 , nous devrions être en mesure de produire un peu plus de deux bits du flux de sortie par impartiale d'entrée bits.

Ci-dessous, je donne deux méthodes pour la production de la désinformation bits. Les deux atteindre une efficacité optimale, dans le sens d'exiger, comme quelques-uns d'entrée impartiale bits que possible.

Méthode 1: arithmétique (de)codage

Une méthode pratique consiste à décoder votre impartiale flux d'entrée à l'aide de l'arithmétique (de)de codage, comme déjà décrit dans la réponse d'alexis. Pour cette simple hypothèse, il n'est pas difficile de code quelque chose. Voici quelques unoptimised pseudo-code (toux, Python) qui fait cela:

import random

def random_bits():
    """
    Infinite generator generating a stream of random bits,
    with 0 and 1 having equal probability.
    """
    global bit_count  # keep track of how many bits were produced
    while True:
        bit_count += 1
        yield random.choice([0, 1])

def bernoulli(p):
    """
    Infinite generator generating 1-bits with probability p
    and 0-bits with probability 1 - p.
    """
    bits = random_bits()

    low, high = 0.0, 1.0
    while True:
        if high <= p:
            # Generate 1, rescale to map [0, p) to [0, 1)
            yield 1
            low, high = low / p, high / p
        elif low >= p:
            # Generate 0, rescale to map [p, 1) to [0, 1)
            yield 0
            low, high = (low - p) / (1 - p), (high - p) / (1 - p)
        else:
            # Use the next random bit to halve the current interval.
            mid = 0.5 * (low + high)
            if next(bits):
                low = mid
            else:
                high = mid

Voici un exemple d'utilisation:

import itertools
bit_count = 0

# Generate a million deviates.
results = list(itertools.islice(bernoulli(0.1), 10**6))

print("First 50:", ''.join(map(str, results[:50])))
print("Biased bits generated:", len(results))
print("Unbiased bits used:", bit_count)
print("mean:", sum(results) / len(results))

Le ci-dessus donne l'exemple de sortie suivant:

First 50: 00000000000001000000000110010000001000000100010000
Biased bits generated: 1000000
Unbiased bits used: 469036
mean: 0.100012

Comme promis, nous avons généré 1 million de bits de notre sortie biaisée flux en utilisant moins de cinq cent mille à partir de la source impartiale de flux.

Pour l'optimisation, lors de la traduction en C / C++ il peut faire sens pour code les avec entier à point fixe de l'arithmétique plutôt que de virgule flottante.

Méthode 2: integer algorithme basé sur

Plutôt que d'essayer de convertir le décodage arithmétique de la méthode à utiliser des entiers directement, voici une approche plus simple. Ce n'est pas tout à fait de l'arithmétique de décodage plus, mais elle n'est pas totalement étranger, et il y parvient à peu près le même sortie biaisée bits d'entrée / de-impartiale bits ratio de la virgule flottante version ci-dessus. Il est organisé de façon à ce que toutes les quantités entrant dans un entier 32 bits non signé, il doit donc être facile à traduire en C / C++. Le code est spécialisé pour le cas où l' p est un multiple exact de 1/200, mais cette approche pourrait fonctionner pour n'importe quel p qui peut être exprimé comme un nombre rationnel avec raisonnablement petit dénominateur.

def bernoulli_int(p):
    """
    Infinite generator generating 1-bits with probability p
    and 0-bits with probability 1 - p.

    p should be an integer multiple of 1/200.
    """
    bits = random_bits()
    # Assuming that p has a resolution of 0.05, find p / 0.05.
    p_int = int(round(200*p))

    value, high = 0, 1
    while True:
        if high < 2**31:
            high = 2 * high
            value = 2 * value + next(bits)
        else:
            # Throw out everything beyond the last multiple of 200, to
            # avoid introducing a bias.
            discard = high - high % 200
            split = high // 200 * p_int
            if value >= discard:  # rarer than 1 time in 10 million
                value -= discard
                high -= discard
            elif value >= split:
                yield 0
                value -= split
                high = discard - split
            else:
                yield 1
                high = split

L'observation essentielle est que chaque fois que nous atteignons le début de l' while boucle, value est répartie uniformément entre tous les entiers en [0, high), et est indépendant de tous les précédemment sortie bits. Si vous vous souciez de la vitesse de la plus parfaite exactitude, vous pouvez vous débarrasser de l' discard et de la value >= discard branche: c'est juste là pour s'assurer que nous avons de sortie 0 et 1 avec exactement la bonne probabilités. Laisser cette complication, et il vous suffit de faire presque le droit des probabilités à la place. Aussi, si vous prenez la résolution de p égal à 1/256 plutôt que d' 1/200, puis potentiellement consommatrice de temps, la division et le modulo opérations peuvent être remplacées par des opérations sur les bits.

Avec le même code de test comme avant, mais en utilisant bernoulli_int à la place de bernoulli, j'obtiens les résultats suivants pour p=0.1:

First 50: 00000010000000000100000000000000000000000110000100
Biased bits generated: 1000000
Unbiased bits used: 467997
mean: 0.099675

Answer 4

Supposons que la probabilité qu'un 1 apparaisse est de 6,25% (1/16). Il existe 16 modèles de bits possibles pour un nombre de 4 bits: 0000,0001, ..., 1110,1111 .

Maintenant, générez simplement un nombre aléatoire comme vous le faisiez et remplacez chaque 1111 à une limite de quartet par un 1 et réglez le reste sur un 0 .

Ajustez en conséquence pour d'autres probabilités.

Answer 5

Euh, pseudo-générateurs de nombres aléatoires sont généralement assez rapide. Je ne suis pas sûr de ce que la langue c'est (Python, peut-être), mais "le résultat.append" (qui contient très certainement l'allocation de la mémoire) est probablement plus lent que "random_uniform" (qui fait juste un peu de mathématiques).

Si vous souhaitez optimiser les performances de ce code:

1. Vérifiez que c'est un problème. Les optimisations sont un peu de travail et de rendre le code plus difficile à maintenir. Ne pas le faire, sauf si nécessaire.
2. De profil. Faire quelques tests pour déterminer quelles parties du code sont en fait le plus lent. Ce sont les pièces dont vous avez besoin pour accélérer.
3. Apportez vos modifications, et de vérifier qu'elles sont en fait plus rapide. Les compilateurs sont assez intelligents; souvent clair code compiler dans un code de meilleure qualité que quelque chose de complexe qu'il n'apparaît plus rapide.

Si vous travaillez dans un langage compilé (même JIT compiler), vous prenez un gain de performance pour chaque transfert de contrôle (if, while, appel de fonction, etc). Éliminer ce que vous pouvez. L'allocation de mémoire est aussi (en général) assez cher.

Si vous travaillez dans un langage interprété, tous les paris sont éteints. Le code le plus simple est très probablement le meilleur. La surcharge de l'interprète nain tout ce que vous faites, afin d'alléger son travail autant que possible.

Je ne peux que deviner où vos problèmes de performances sont:

1. L'allocation de la mémoire. Pré-allouer le tableau à sa pleine taille et remplissez les entrées plus tard. Cela garantit que la mémoire n'est pas besoin d'être réaffectées pendant que vous êtes en train d'ajouter les entrées.
2. Les Branches. Vous pourriez être en mesure d'éviter le "si" en jetant le résultat ou quelque chose de similaire. Cela dépendra beaucoup sur le compilateur. Vérifiez le montage (ou profil) pour vérifier qu'il fait ce que vous voulez.
3. Les types numériques. Trouver le type de votre générateur de nombre aléatoire utilise nativement, et de faire de l'arithmétique dans ce type. Par exemple, si le générateur retourne naturellement non signé de 32 bits entiers, de l'échelle "p" pour cette plage d'abord, puis de l'utiliser pour la comparaison.

Par ailleurs, si vous voulez vraiment utiliser le moins de bits d'aléatoire possible, utiliser "le codage arithmétique" de décoder les flux aléatoire. Il ne sera pas rapide.