algorithm - pseint - ordenamiento quicksort

¿Qué pasa, en todo caso, está mal con este algoritmo de mezcla y cómo puedo saberlo?

Question

Solo como fondo, soy consciente de la mezcla perfecta de Fisher-Yates . Es un gran revoltijo con su complejidad O (n) y su uniformidad garantizada y sería un tonto no usarlo ... en un entorno que permite actualizaciones in situ de matrices (por lo que en la mayoría, si no en todos, entornos de programación imperativa ).

Lamentablemente, el mundo de la programación funcional no le da acceso al estado mutable.

Sin embargo, debido a Fisher-Yates, no hay mucha literatura que pueda encontrar sobre cómo diseñar un algoritmo de mezcla. Los pocos lugares que lo abordan lo hacen brevemente antes de decir, en efecto, "así que aquí está Fisher-Yates, que es todo lo que necesitas saber". Al final, tuve que encontrar mi propia solución.

La solución que surgió funciona de esta manera para mezclar cualquier lista de datos:

• Si la lista está vacía, devuelva el conjunto vacío.
• Si la lista tiene un solo elemento, devuelva ese único elemento.
• Si la lista no está vacía, particione la lista con un generador de números aleatorios y aplique el algoritmo recursivamente en cada partición, reuniendo los resultados.

En el código de Erlang se ve algo como esto:

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(Si esto te parece una especie de desquiciación rápida, bueno, eso es lo que es, básicamente).

Así que aquí está mi problema: la misma situación que hace que la búsqueda de algoritmos de mezcla que no son difíciles para Fisher-Yates haga que encontrar herramientas para analizar un algoritmo de mezcla sea igualmente difícil. Hay mucha literatura que puedo encontrar al analizar los PRNG para uniformidad, periodicidad, etc., pero no mucha información sobre cómo analizar un shuffle. (De hecho, parte de la información que encontré sobre el análisis de mezclas fue simplemente incorrecta, fácilmente engañada a través de técnicas simples).

Entonces mi pregunta es: ¿cómo analizo mi algoritmo de mezcla (suponiendo que la llamada random:uniform() está a la altura de la tarea de generar números aleatorios apropiados con buenas características)? ¿Qué herramientas matemáticas hay a mi disposición para juzgar si, digamos, 100,000 ejecuciones del mezclador sobre una lista de enteros que van desde 1.100 me han dado resultados plausiblemente buenos? He hecho algunas pruebas por mi cuenta (comparando incrementos a decrementos en las mezclas, por ejemplo), pero me gustaría saber algunas más.

Y si hay alguna idea de ese algoritmo de mezcla que también sería apreciado.

Answer 1

Observación General

Mi enfoque personal acerca de la exactitud de los algoritmos que usan la probabilidad: si sabes cómo probar que es correcto, entonces probablemente sea correcto; si no lo hace, ciertamente es incorrecto.

Dicho de otra manera, en general es inútil intentar analizar cada algoritmo que se te ocurra: tienes que seguir buscando un algoritmo hasta que encuentres uno que puedas probar correctamente.

Analizando un algoritmo aleatorio calculando la distribución

Conozco una forma de "automáticamente" analizar un aleatorio (o más generalmente un algoritmo de uso aleatorio) que es más fuerte que el simple "lanzar muchas pruebas y verificar la uniformidad". Puede calcular mecánicamente la distribución asociada a cada entrada de su algoritmo.

La idea general es que un algoritmo de uso aleatorio explora una parte de un mundo de posibilidades. Cada vez que su algoritmo solicita un elemento aleatorio en un conjunto ({ true , false } cuando lanza una moneda), hay dos posibles resultados para su algoritmo, y se elige uno de ellos. Puede cambiar su algoritmo para que, en lugar de devolver uno de los resultados posibles, explore todas las soluciones en paralelo y devuelva todos los resultados posibles con las distribuciones asociadas.

En general, eso requeriría reescribir su algoritmo en profundidad. Si su idioma admite continuaciones delimitadas, no es necesario; puede implementar "exploración de todos los resultados posibles" dentro de la función solicitando un elemento aleatorio (la idea es que el generador aleatorio, en lugar de devolver un resultado, capture la continuación asociada a su programa y lo ejecute con todos los resultados diferentes). Para ver un ejemplo de este enfoque, vea HANSEI de HANSEI .

Una solución intermedia, y probablemente menos arcana, es representar este "mundo de posibles resultados" como una mónada, y usar un lenguaje como Haskell con instalaciones para la programación monádica. Aquí hay una implementación de ejemplo de una variante¹ de su algoritmo, en Haskell, usando la mónada de probability paquete de probability :

import Numeric.Probability.Distribution

shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
        (left, right) <- partition li
        sleft <- shuffleM left
        sright <- shuffleM right
        return (sleft ++ [pivot] ++ sright)
  where partition [] = return ([], [])
        partition (x:xs) = do
                  (left, right) <- partition xs
                  uniform [(x:left, right), (left, x:right)]

Puede ejecutarlo para una entrada determinada y obtener la distribución de salida:

*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
  [([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
   ([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]

Puede ver que este algoritmo es uniforme con entradas de tamaño 2, pero no uniforme en las entradas de tamaño 3.

La diferencia con el enfoque basado en pruebas es que podemos obtener certeza absoluta en un número finito de pasos: puede ser bastante grande, ya que equivale a una exploración exhaustiva del mundo de los posibles (pero generalmente más pequeño que 2 ^ N, como hay factorizaciones de resultados similares), pero si devuelve una distribución no uniforme, sabemos con certeza que el algoritmo está equivocado. Por supuesto, si devuelve una distribución uniforme para [1..N] y 1 <= N <= 100 , solo sabe que su algoritmo es uniforme hasta listas de tamaño 100; aún puede estar equivocado.

¹: este algoritmo es una variante de la implementación de Erlang, debido al manejo específico del pivote. Si no uso pivote, como en su caso, el tamaño de entrada no disminuye en cada paso: el algoritmo también considera el caso donde todas las entradas están en la lista de la izquierda (o en la lista de la derecha), y se pierde en un ciclo infinito . Esta es una debilidad de la implementación de la mónada de probabilidad (si un algoritmo tiene una probabilidad 0 de no terminación, el cómputo de distribución aún puede divergir), que aún no sé cómo solucionarlo.

Mezcla basada en clasificaciones

Aquí hay un algoritmo simple que estoy seguro de que podría probar que es correcto:

1. Elija una clave aleatoria para cada elemento en su colección.
2. Si las claves no son todas distintas, reinicie desde el paso 1.
3. Ordenar la colección por estas claves aleatorias.

Puede omitir el paso 2 si sabe que la probabilidad de una colisión (dos números aleatorios recogidos son iguales) es suficientemente baja, pero sin ella la mezcla no es perfectamente uniforme.

Si elige sus llaves en [1..N] donde N es la longitud de su colección, tendrá muchas colisiones ( problema de cumpleaños ). Si selecciona su clave como un entero de 32 bits, la probabilidad de conflicto es baja en la práctica, pero aún está sujeta al problema del cumpleaños.

Si utiliza cadenas de bits infinitas (evaluadas de forma diferida) como claves, en lugar de claves de longitud finita, la probabilidad de una colisión se vuelve 0 y ya no es necesario verificar la distinción.

Aquí hay una implementación aleatoria en OCaml, usando números reales perezosos como bitstrings infinitos:

type ''a stream = Cons of ''a * ''a stream lazy_t

let rec real_number () =
  Cons (Random.bool (), lazy (real_number ()))

let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a''), Cons (_, lazy b'') ->
    compare_real a'' b''

let shuffle list =
  List.map snd
    (List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
       (List.map (fun x -> real_number (), x) list))

Hay otros enfoques para "mezclar puro". Una buena es la solución de apfelmus basada en mergesort .

Consideraciones algorítmicas: la complejidad del algoritmo anterior depende de la probabilidad de que todas las claves sean distintas. Si los eliges como enteros de 32 bits, tienes una probabilidad de entre ~ 4,000 millones de que una tecla particular colisione con otra clave. La clasificación por estas teclas es O (n log n), suponiendo que elegir un número aleatorio es O (1).

Si tiene infinitas cadenas de bits, nunca tendrá que reiniciar la selección, pero la complejidad está relacionada con "cuántos elementos de las secuencias se evalúan en promedio". Conjeturo que es O (log n) en promedio (por lo tanto, sigue siendo O (n log n) en total), pero no tiene ninguna prueba.

... y creo que tu algoritmo funciona

Después de más reflexión, creo (como douplep), que su implementación es correcta. Aquí hay una explicación informal.

Cada elemento de su lista se prueba con varias pruebas random:uniform() < 0.5 . Para un elemento, puede asociar la lista de resultados de esas pruebas, como una lista de booleanos o { 0 , 1 }. Al comienzo del algoritmo, no conoce la lista asociada a ninguno de esos números. Después de la primera llamada de partition , conoce el primer elemento de cada lista, etc. Cuando su algoritmo retorna, la lista de pruebas es completamente conocida y los elementos se ordenan según esas listas (ordenadas en orden lexicográfico, o consideradas como representaciones binarias de numeros reales).

Entonces, su algoritmo es equivalente a clasificar por claves infinitas de cadena de bits. La acción de particionar la lista, que recuerda a la partición de quicksort sobre un elemento de pivote, es en realidad una forma de separar, para una posición dada en la cadena de bits, los elementos con valoración 0 de los elementos con valoración 1 .

El género es uniforme porque las cadenas de bits son todas diferentes. De hecho, dos elementos con números reales iguales hasta el n -ésimo bit están en el mismo lado de una partición que ocurre durante una llamada shuffle recursiva de profundidad n . El algoritmo solo finaliza cuando todas las listas resultantes de las particiones son vacías o simples: todos los elementos han sido separados por al menos una prueba, y por lo tanto tienen un decimal binario distinto.

Terminación probabilística

Un punto sutil acerca de su algoritmo (o mi método equivalente basado en la clasificación) es que la condición de terminación es probabilística . Fisher-Yates siempre termina después de un número conocido de pasos (la cantidad de elementos en la matriz). Con su algoritmo, la terminación depende de la salida del generador de números aleatorios.

Hay salidas posibles que harían que tu algoritmo divergera , no terminara. Por ejemplo, si el generador de números aleatorios siempre da como resultado 0 , cada llamada de partition devolverá la lista de entrada sin cambios, en la que recursivamente llamará a la mezcla aleatoria: se reproducirá indefinidamente.

Sin embargo, esto no es un problema si confía en que su generador de números aleatorios es justo: no hace trampa y siempre devuelve resultados independientes distribuidos de manera uniforme. En ese caso, la probabilidad de que la prueba random:uniform() < 0.5 siempre devuelva true (o false ) es exactamente 0:

• la probabilidad de que las primeras N llamadas devuelvan true es 2 ^ {- N}
• la probabilidad de que todas las llamadas devuelvan true es la probabilidad de la intersección infinita, para todos los N, del evento en que las primeras N llamadas devuelvan 0 ; es el límite inferior¹ de 2 ^ {- N}, que es 0

¹: para los detalles matemáticos, ver http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets

De manera más general, el algoritmo no termina si y solo si algunos de los elementos se asocian a la misma secuencia booleana. Esto significa que al menos dos elementos tienen la misma secuencia booleana. Pero la probabilidad de que dos flujos booleanos aleatorios sean iguales es nuevamente 0: la probabilidad de que los dígitos en la posición K sean iguales es 1/2, por lo que la probabilidad de que los primeros dígitos N sean iguales es 2 ^ {- N}, y la misma análisis aplica

Por lo tanto, usted sabe que su algoritmo termina con la probabilidad 1 . Esta es una garantía ligeramente más débil que el algoritmo de Fisher-Yates, que siempre termina . En particular, eres vulnerable al ataque de un malvado adversario que controlaría tu generador de números aleatorios.

Con más teoría de probabilidad, también puede calcular la distribución de los tiempos de ejecución de su algoritmo para una longitud de entrada determinada. Esto está más allá de mis habilidades técnicas, pero supongo que es bueno: supongo que solo necesita mirar O (log N) los primeros dígitos en promedio para verificar que todas las N secuencias diferidas sean diferentes, y que la probabilidad de tiempos de ejecución mucho más altos disminuir exponencialmente

Answer 2

En base a Cómo probar la aleatoriedad (caso en punto - Mezcla) , propongo:

Conjuntos aleatorios (de tamaño mediano) compuestos de números iguales de ceros y unos. Repita y concatene hasta aburrirse. Úselos como entrada para las pruebas duras. Si tiene una buena mezcla, entonces debe generar secuencias aleatorias de ceros y unos (con la advertencia de que el exceso acumulado de ceros (o unos) es cero en los límites de las matrices de tamaño mediano, lo que esperaría que las pruebas detectaran , pero el "medio" más grande es menos probable que lo hagan).

Tenga en cuenta que una prueba puede rechazar su barajamiento por tres razones:

• el algoritmo de mezcla es malo,
• el generador de números aleatorios utilizado por el mezclador o durante la inicialización es malo, o
• la implementación de la prueba es mala

Tendrás que resolver cuál es el caso si alguna prueba rechaza.

Varias adaptaciones de las pruebas duras (para resolver ciertos números, utilicé la source de la página obstinada ). El principal mecanismo de adaptación es hacer que el algoritmo aleatorio actúe como una fuente de bits aleatorios distribuidos uniformemente.

• Espacios de cumpleaños: en una matriz de n ceros, inserte log n ones. Barajar. Repite hasta aburrido. Construya la distribución de distancias entre uno, compare con la distribución exponencial. Debe realizar este experimento con diferentes estrategias de inicialización: las del frente, las del final, las del medio, las dispersas al azar. (Este último tiene el mayor riesgo de una mala aleatorización de inicialización (con respecto a la aleatorización aleatoria) produciendo el rechazo de la mezcla). Esto realmente se puede hacer con bloques de valores idénticos, pero tiene el problema de que introduce una correlación en las distribuciones ( uno y dos no pueden estar en el mismo lugar en una sola mezcla).
• Permutaciones superpuestas: mezclar cinco valores varias veces. Verifique que los 120 resultados sean aproximadamente igualmente probables. (Prueba Chi-cuadrado, 119 grados de libertad: la prueba diehard (cdoperm5.c) usa 99 grados de libertad, pero esto es (principalmente) un artefacto de correlación secuencial causada por el uso de subsecuencias superpuestas de la secuencia de entrada).
• Rangos de matrices: de 2 * (6 * 8) ^ 2 = 4608 bits de mezclar números iguales de ceros y unos, seleccione 6 subcadenas de 8 bits no superpuestas. Trátelos como una matriz binaria de 6 por 8 y calcule su rango. Repita para 100.000 matrices. (Agrupe los rangos de 0 a 4. Los rangos son 6, 5 o 0-4). La fracción esperada de rangos es 0.773118, 0.217439, 0.009443. Chi-cuadrado se compara con fracciones observadas con dos grados de libertad. Las pruebas de 31 por 31 y 32 por 32 son similares. Los rangos de 0-28 y 0-29 se agrupan, respectivamente. Las fracciones esperadas son 0.2887880952, 0.5775761902, 0.1283502644, 0.0052854502. La prueba Chi-cuadrado tiene tres grados de libertad.

y así...

También puede aprovechar dieharder y / o ent para hacer pruebas adaptadas similares.

Answer 3

Estuve haciendo algo similar a esto hace un tiempo, y en particular, podría interesarle los vectores de Clojure, que son funcionales e inmutables, pero aún con O (1) características de acceso / actualización aleatorias. Estas dos ideas tienen varias implementaciones de "tomar N elementos al azar de esta lista de tamaño M"; al menos uno de ellos se convierte en una implementación funcional de Fisher-Yates si dejas que N = M.

https://gist.github.com/805546

https://gist.github.com/805747

Answer 4

Su algoritmo es una mezcla aleatoria basada en género, como se explica en el artículo de Wikipedia.

En términos generales, la complejidad computacional de las aleatorizaciones basadas en género es la misma que la del algoritmo de ordenamiento subyacente (p. Ej. O ( n log n ) promedio, O ( n ²) el peor caso para una mezcla aleatoria basada en ordenamiento), y aunque la distribución no es perfectamente uniforme, debe acercarse al uniforme lo suficientemente cerca para la mayoría de los propósitos prácticos.

Oleg Kiselyov proporciona el siguiente artículo / discusión:

• Mezcla aleatoria perfectamente perfecta y sus implementaciones funcionales puras

que cubre las limitaciones de las mezclas basadas en género con más detalle, y también ofrece dos adaptaciones de la estrategia de Fischer-Yates: una O ( n ²) ingenua y una basada en árbol binario O ( n log n ).

Lamentablemente, el mundo de la programación funcional no le da acceso al estado mutable.

Esto no es cierto: mientras que la programación puramente funcional evita los efectos secundarios , admite el acceso al estado mutable con efectos de primera clase, sin requerir efectos secundarios.

En este caso, puede usar las matrices mutables de Haskell para implementar el algoritmo de Fischer-Yates mutante como se describe en este tutorial:

• Haskell Shuffling (Brett Hall)

Apéndice

La base específica de su clasificación aleatoria es en realidad una clasificación de radix de clave infinita: como señala gasche, cada partición corresponde a una agrupación de dígitos.

La principal desventaja de esto es la misma que cualquier otra combinación aleatoria de clasificación de clave infinita: no hay garantía de terminación. Aunque la probabilidad de terminación aumenta a medida que avanza la comparación, nunca hay un límite superior: la complejidad del caso más desfavorable es O (∞).