Tiene una matriz de tamaño n, que contiene valores booleanos arbitrarios.Dada una matriz de booleanos, ¿cuál es la forma más eficiente de seleccionar el índice de un valor TRUE aleatorio?
¿Cuál es la forma más rápida de devolver el índice de un valor TRUE aleatorio.
El algoritmo debe devolver aleatoriamente cualquiera de los índices que contienen un VERDADERO.
Algo como esto:
int count = 0;
int index = -1;
for (int i = 0; i != n; ++i)
{
if (values[i])
{
++count;
if (unit_random <= 1.0f/count)
{
index = i;
}
}
}
Así, por 4 valores, por ejemplo, se obtienen los siguientes probabilidades para sus índices:
1: (1/1) * (1/2) * (2/3) * (3/4) = 1/4
2: (1/2) * (2/3) * (3/4) = 1/4
3: (1/3) * (3/4) = 1/4
4: 1/4 = 1/4
EDIT: Como Steve Jessop señaló el punto de comparación flotante eventualmente conducirá a una selección muy poco uniforme. Suponiendo unit_random se define como rand()/RAND_MAX la comparación se puede cambiar a:
typedef unsigned long long u64;
u64 product = u64(count) * rand();
if (product <= u64(RAND_MAX))
Esto no dará perfecta distribución debido a la naturaleza discreta de rand pero será mejor.
No está del todo claro qué significa "distribución aleatoria". ¿Significa "con alguna distribución desconocida"? Si es así, imaginemos que todas las distribuciones posibles son igualmente probables, por lo que la "distribución esperada" (como en "valor esperado") es uniforme (el "promedio" de todas las distribuciones posibles). Entonces cualquier índice es VERDADERO con una probabilidad de 1/2. De modo que su tarea se convierte en la tarea de iterar a través de la matriz lo más rápido posible. Comience por el principio, como normalmente iteraría una matriz, hasta que encuentre un valor VERDADERO.
Quise decir que no hay ningún patrón en los valores. No siguen ningún tipo de función de distribución. – PaulV
Supongo que eso significa [distribución uniforme] (http://en.wikipedia.org/wiki/Uniform_distribution_ (discrete)), ¿verdad? ;) –
@PaulV: "distribuido al azar" es probablemente una mala frase para usar si quieres decir "no siguen ningún tipo de función de distribución". Podría haber dicho "valores booleanos arbitrarios", o simplemente "valores booleanos". Entonces tendría que definir lo que quiere decir con "más rápido", porque si no tiene una distribución para los valores, entonces no existe el "tiempo de ejecución esperado" para ningún algoritmo cuya velocidad dependa de los valores. –
Para devolverlo, primero debe contar los valores verdaderos (no hay forma de omitir eso) y acumular sus índices en otra matriz. Y después de contar, necesita generar un entero aleatorio de 0 a N-1 (donde N es el número de valores True) y seleccionar el valor de la matriz creada.
en pseudo-Python:
indices=[]
for i,val in enumerate(arr):
if val:
indices.append(i)
randi = randint(0,len(indices)-1)
return indices[randi]
La solución más rápida - suponiendo que no selecciona varias veces en la misma matriz - es escoger un índice de azar, devolverlo si es verdad, y repita si no. En el mejor de los casos, donde todas las entradas son verdaderas, esto es O (1); en el peor de los casos, donde solo una entrada es verdadera, esto es O (n) (cada intento tiene una posibilidad 1/n de alcanzar el único valor verdadero, lo que significa un número esperado de intentos de n). Esto no es peor que cualquiera de las otras soluciones publicadas.
Si espera que la matriz sea casi siempre falsa, es posible que desee elegir otra solución, ya que la varianza en el tiempo de ejecución de este método aleatorio será alta.
"Esto no es peor que cualquiera de las otras soluciones publicadas": la complejidad no lo es, pero usa el caché de forma menos eficiente que la respuesta de Andreas. Y FWIW, el código de Andreas capta el caso de falla, y este enfoque no. Tal vez lo "mejor" (intercambiar entre el esperado y el peor de los casos) es realizar un pequeño número de muestras aleatorias, y si ninguna de ellas encuentra un valor verdadero, concluir que la matriz es escasa y recurrir a la solución de Andreas o similar . –
solución simple: Generar una permutación de los posibles índices (1: n) y en el orden de permutación que el índice de retorno si el valor correspondiente es cierto
def randomTrue(x):
perm = randomPermute(0:len(x))
for i in perm:
if x[i]:
return i
Lo siento, se olvidó una palabra. Quise decir: devuelve el índice de un valor TRUE aleatorio ... No solo el primero que encontramos. Pero la función debe devolver aleatoriamente cualquiera de los índices que contiene un VERDADERO. – PaulV
@PaulV Eso es exactamente lo que hace esta función. –
@Nick Sí, pero he editado mi respuesta;) –