Enumeración aleatoria de una tabla hash en OCaml

Question

Disculpa por la pregunta larga. Primero decidí explicar el contexto del problema, ya que quizás haya otras soluciones para mi problema. Si tienes prisa, simplemente lee LA PREGUNTA a continuación.

(editado - Por el momento he añadido algunos intentos para resolver el problema El cuarto tiene mi conclusión final, es posible saltar directamente a él..)

EL CONTEXTO

I tener una tabla hash llena con aproximadamente 20k pares (clave (i), valor (i)). Quiero generar listas aleatorias como éste

[(key(213),value(213));(key(127),value(127));(key(89),value(89));...] 

La restricción es que una vez que he elegido llave (213) para ser el primer elemento de la lista, no todas las teclas pueden seguirla (tengo alguna otra función 'decide' que puede decidir si alguna tecla puede ser la siguiente en la lista o no). Por lo tanto, me gustaría elegir un próximo elemento aleatorio y verificar si es apropiado; en el ejemplo anterior, se eligió la clave (127). En el caso de que ese elemento sea rechazado por mi función de 'decidir', me gustaría elegir otro aleatoriamente. Pero no quisiera elegir lo mismo que rechacé porque sé que será rechazado de nuevo y no solo sería ineficiente, también corro el riesgo, si solo unas pocas claves pueden ser las siguientes, de tomarme un largo tiempo hasta que encuentre una clave apropiada. Tenga en cuenta que puede ser repetición, tales como

[(key(213),value(213));(key(213),value(213));(key(78),value(78));...] 

Esto está bien, siempre y cuando la función de 'decidir' acepta clave (213) como el siguiente en la lista. Entonces, todo lo que necesito es una forma de enumerar aleatoriamente los pares (clave, valor) en la tabla hash. Cada vez que tengo que elegir una clave, creo una enumeración, que consumo verificando cada elemento nuevo con la función 'decidir' (así, no ocurren repeticiones) y cuando encuentro una, la agrego a la lista y sigo incrementando la lista . La cuestión es que no quiero que esta enumeración de la tabla hash sea la misma siempre. Quiero que sea al azar (Esto tiene que ver con la estructura del espacio de búsqueda que tengo en mi problema particular que no es relevante aquí.)

Por supuesto puedo implementar esto generando enteros aleatorios y usando listas simples - eso es lo que soy actualmente haciendo. Pero, como esto es algo con lo que me tropiezo con bastante frecuencia, me pregunto si hay alguna facilidad de enumeración aleatoria para tablas hash en alguna parte.

LA PREGUNTA

¿Hay alguna función de enumeración de las tablas hash aleatoria en alguna parte? Conozco la función BatHashtbl.enum (Biblioteca de baterías) pero creo que siempre me dará la misma enumeración para la misma tabla hash (¿es correcto?). Además, no parece existir nada de ese tipo en ese módulo BatHashtbl. Yo estaría interesado en algo así como

random_enum: ('a, 'b) t -> int -> ('a * 'b) Enum.t 

que, al ser dotado de una tabla hash y algún entero como una semilla para el generador aleatorio, dará un recuento aleatorio diferente de la tabla hash. ¿Algunas ideas?

¡Gracias por cualquier ayuda!

Mejor, Surikator.

primer intento

Después de la sugerencia de Niki en los comentarios, y mirando con más detalle a través de la Biblioteca de baterías, se me ha ocurrido con este

let rand_enum ht n = 
BatRandom.init n; 
let hte = BatHashtbl.enum ht 
in let s = BatRandom.shuffle hte (* This returns*) 
in Array.to_list s 

que tiene el tipo

val rand_enum : ('a,'b) BatHashtbl.t -> int -> ('a*'b) list 

Utiliza el algoritmo de Fisher-Yates para el barajado que se ejecuta en O (n). Devuelve una lista en lugar de una enumeración y eso es bastante molesto, porque significa que incluso si estoy contento con el tercer elemento de la lista obtenida con rand_enum, la función calculará una enumeración aleatoria de los 20k elementos en el tabla de picadillo.

mejor, Surikator

segundo intento

que define el módulo como RndHashtblEnum

(* Random Hashtable Enumeration Module *) 
type ('a,'b) t = { 
    ht:('a,'b) BatHashtbl.t; 
    mutable ls:('a*'b) list; 
    f: (('a,'b) BatHashtbl.t -> ('a*'b) list)} 

let shuffle ht = 
    let hte = BatHashtbl.enum ht 
    in let s = BatRandom.shuffle hte 
    in Array.to_list s 

let create ht n = (BatRandom.init n; {ht=ht;ls=shuffle ht;f=shuffle}) 

let rec next re = 
match re.ls with 
    | [] -> re.ls<-(re.f re.ht);next re 
    | h::t -> re.ls<-t; h 

Cuenta con el nuevo tipo de t para las enumeraciones al azar de las tablas hash. Este tipo almacena la tabla hash que deseamos enumerar, la lista que enumeraremos y una función para calcular una nueva lista enumerada (desde la tabla hash) una vez que se acabe la lista que tenemos. Una vez que la lista se ha agotado, cuando solicitamos un nuevo elemento aleatorio de la tabla hash, el tipo t automáticamente coloca una nueva lista aleatoria creada a partir de la tabla hash.

Por lo tanto, utilizando el módulo anterior, si queremos enumerar una tabla hash al azar, simplemente hacemos:

let re = RndHashtblEnum.create ht 1236 

para crear una enumeración aleatoria de ht tabla hash con semilla aleatoria 1236 (En este código I asumir la tabla hash se definió antes) y que a continuación, puede escribir

let (k,v) = RndHashtblEnum.next re 

para obtener el siguiente (k, v) par de la enumeración al azar.

Una pregunta que podemos hacernos es si esto es aleatoriedad real porque utilizo el resto de la lista para enumerar aleatoriamente la tabla hash la próxima vez que necesito una enumeración aleatoria. Bueno, no lo es. Si mi tabla hash tiene, por ejemplo, 1000 elementos y después de extraer 5 aleatorios estoy satisfecho con el resultado, sé que en los próximos 995 (del segundo conjunto de extracciones) ninguno de esos 5 elementos será extraído. Entonces, eso no es una aleatoriedad justa. Es aún peor. Puede ocurrir que en las siguientes 1000 extracciones (995 de esta lista, 5 de la lista de enumeración siguiente) algunos elementos no estén cubiertos. En promedio, el algoritmo es justo, pero no es justo todo el tiempo.

Mejor, Surikator.

tercer intento

Hola de nuevo,

Incluyendo sugerencia de utilizar BatArray.enum y un cambio fundamental en la parte estocástica del algoritmo de Niki, que han llegado con una nueva versión mejorada de la Módulo RndHashtblEnum.La sugerencia es:

(* Improved Random Hashtable Enumeration Module *) 
type ('a,'b) t = {ht:('a,'b) BatHashtbl.t; mutable enum:('a*'b) BatEnum.t; enum0: ('a*'b) BatEnum.t} 

let shuffle ht = 
let hte = BatHashtbl.enum ht 
in let s = BatRandom.shuffle hte 
in BatArray.enum s 

let create ht n = 
let e = shuffle ht 
in (BatRandom.init n; {ht=ht;enum=BatEnum.clone e;enum0=e}) 

let rec next re = 
match BatEnum.get re.enum with 
    | None -> re.enum<-re.enum0; next re 
    | Some e -> e 

Este nuevo módulo se deshace de los costos (tontos) de pasar una matriz a una lista y sólo utiliza el algoritmo de Fisher-Yates vez al comienzo - por lo que, en el largo plazo, podemos considerar la contribución del bit de Fisher-Yates como O (1).

La nueva versión ahora es justa en términos de aleatoriedad. Esto no es tan fácil de ver y me tomó un poco darme cuenta de eso. Supongamos que la tabla hash tiene 1000 entradas. En la nueva versión, siempre usamos la misma enumeración (enum0 - corregida cuando creamos la enumeración aleatoria con la función "crear"). Esto significa que, al tratar de encontrar el siguiente elemento en nuestra lista final, dado que alguna clave en la tabla hash tendrá que cumplir la función "decidir" (de lo contrario, no podríamos continuar con el algoritmo y simplemente nos detendríamos), lo hará en algún lugar entre la entrada 0ª y la 999ª. Supongamos que está en la entrada 300. Ahora, dado que hemos elegido esta clave, para decidir la siguiente clave en la lista final, nuestra enumeración continuará con los 700 elementos restantes y luego pasará a los siguientes 300 en la copia de la misma enumeración. Entonces, los 700 + 300 hacen exactamente los 1000 en la tabla hash. Esto significa que siempre consideraremos cada entrada en la tabla hash una vez y solo una vez. La otra cosa es que cada vez que intentamos encontrar una clave para ir en la lista, esa etiqueta se puede encontrar en la entrada 300, pero también en la entrada 734 o en otra, porque la función de decisión en realidad depende de qué teclas anteriores se hayan elegido hasta ese punto en la lista final. Entonces, cada vez que empezamos de nuevo buscando un elemento para la lista final en la tabla hash, comenzamos con un elemento aleatorio de la tabla hash.

Lo siento si esto no es muy claro. Es dificil de explicar. =)

Gracias por todos los comentarios.

Mejor, Surikator.

CUARTA Y el último intento - esto es la solución que propongo

Hola una vez más,

preocupaciones Intercambio de Gasché sobre campos y enumeraciones en general mutables y todos los extraños efectos secundarios que pueden venir de allí, decidí olvidarme de las soluciones listas para usar usando las bibliotecas de tablas hash disponibles y escribí mis cosas usando listas simples. También traía la pereza para tratar de evitar la generación de listas aleatorias de las cuales solo se usaría una parte (por lo que había cosas perezosas útiles para usar como sugirió, Niki).

creé el tipo

type 'a node_t = 
    | ENil 
    | ECons of 'a * 'a list * 'a t 
and 'a t = ('a node_t) Lazy.t 

para enumeraciones al azar de descanso de las listas. Cada enumeración está vacía (ENil) o no (ECons), en cuyo caso tiene tres partes: (1) el elemento actualmente en foco, (2) el resto de elementos disponibles para enumerar, (3) otra enumeración para continuar esta enumeración.

Entonces, una enumeración aleatoria de una lista se puede obtener usando la función

let rec create ls = 
lazy( match ls with 
    | [] -> ENil 
    | h::t -> let n = Random.int (List.length ls) 
       in let newx,rest=remove ls n 
      in ECons(newx,rest,create t)) 

create donde la función auxiliar remove se ha definido para extraer el elemento n-ésimo de una lista y regresar un par (x,ls) donde x es el elemento extraído y ls es la nueva lista sin el elemento extraído. Para completar, también agregué el código de la función remove aquí.

let rec remove ls n = 
let rec remove_ ls acc k n = 
    match ls with 
     | []  -> raise (Failure "remove") 
     | h::t -> if k=n 
      then h, List.rev_append acc t 
      else remove_ t (h::acc) (k+1) n 
in remove_ ls [] 0 n 

Ahora podemos definir funciones muy simples para generar el siguiente estado de la enumeración al azar y para conseguir el elemento real en cada estado de la enumeración. Esos son

exception End_of_enum 
let next e = 
match Lazy.force e with 
    | ENil -> raise End_of_enum 
    | ECons(x,ls,t) -> t 
let rec get e = 
match Lazy.force e with 
    | ENil -> raise End_of_enum 
    | ECons(x,ls,t) -> x 

bien, hasta ahora, simplemente he enumerado las listas al azar. Si queremos enumerar una tabla hash lugar, podemos utilizar

let rand_enum ht = 
let ls = Hashtbl.fold (fun k v acc -> (k, v) :: acc) ht [] 
in create ls 

para obtener una enumeración aleatoria de los pares en la tabla hash y podemos usar siguiente y llegar a obtener los pares (clave, valor). El fold, pero es solo una manera de obtener todos los pares (clave, valor) de la tabla hash en una lista (gracias Pascal por su respuesta en este question).

Esto termina la enumeración de la tabla hash todo. En aras de la exhaustividad, estoy agregando también la solución al problema general que estaba tratando de resolver, explicado en "El contexto" más arriba. El problema, si lo recuerdas, es generar aleatoriamente una lista de pares (clave, valor) de (1) una tabla hash, y (2) una función decide que puede indicar si una (clave, valor) se puede agregar a alguna lista particular de pares. Dado que el proceso de generación completo puede no terminar nunca, para garantizar la finalización pensé que tendría sentido tener un tercer argumento, que es una función que indica si debemos detener el proceso o no (y que debemos asegurarnos de que sea cierto en algún momento) para que termine todo el proceso).

La función generate podría ser algo como

let generate ht d stop = 
let rec gen1 d fst e = 
    if d (List.rev fst) (get e) 
       then (get e)::fst 
       else gen1 d fst (next e) 
in let rec generate_ ht d stop acc = 
      let e = rand_enum ht 
      in if stop acc 
         then acc 
         else try generate_ ht d stop (gen1 d acc e) 
          with End_of_enum -> generate_ ht d stop (List.tl acc) 
in generate_ ht d stop [] 

Muchas gracias a todos los que contribuyeron con comentarios útiles. Esto fue realmente útil.

Todo lo mejor, Surikator.

Answer 1

Dudo que exista tal función dada la interfaz expuesta por Hashtbl. El enfoque obvio como obtener todos los valores en una matriz y hacer búsquedas por Array.get a (Random.int (Array.length a)) me parece bien.

Answer 2

Tengo dos sugerencias. La primera es cambiar su función rand_enum por lo que devuelve un Enum.t:

let rand_enum ht n = 
BatRandom.init n; 
let hte = BatHashtbl.enum ht 
in Array.enum (BatRandom.shuffle hte) 

que no es terriblemente diferente (que todavía está calculando una enumeración aleatoria para todos 20k), pero está más cerca de lo que quería en un principio.

Como alternativa, siempre se puede tomar el código fuente de HashTbl y recompilar con una función rand_enum. Sin embargo, esto probablemente tampoco sea tan diferente, ya que HashTbl se implementa como una matriz y si quieres evitar los malos duplicados, probablemente termines utilizando una mezcla aleatoria.

Answer 3

¿Cuál es la densidad del siguiente elemento potencial? ¿Cuál es el costo de su función decide?

Toda su solución actual tiene un O (n) Coste. Fisher-Yates es O (n) (y no tiene mucho sentido tratar de adaptarlo para Enums, ya que requeriría forzar la enumeración de todos modos), y Array.to_list alos es O (n).

Si su función decide es lo suficientemente rápida y su densidad lo suficientemente baja, creo que puede ser más sencillo crear una lista/matriz de todos los elementos elegibles (llamando al decide en cada elemento de la tabla), luego elija uno al azar ellos.

Si la densidad es lo suficientemente alta y decide es costosa, creo que es su primera idea, elegir las claves al azar y mantener una lista de las claves ya encontradas. Podrá elegir el primer elemento elegible encontrado (número óptimo de llamadas decide). Esta manera de enumerar una secuencia se vuelve costosa "al final", cuando ya se han seleccionado todos los elementos, pero si su densidad es alta, no se encontrará con ese caso.

Si no lo sabe, puede ser interesante comenzar con la hipótesis de "alta densidad", y cambiar de opinión una vez que haya visto una parte determinada de la tabla, y aún no haya encontrado nada.

Finalmente: si no necesita agregar/eliminar elementos durante la generación de su secuencia, sería interesante convertir su hashtable en una matriz una vez y listo (manteniendo otra clave -> tabla de índice de matriz en algún lugar), como todos esos problemas son más simples cuando la indexación es contigua.

Answer 4

Sus implementaciones) (segunda y tercera) son demasiado complicadas. No me gusta mutable y no me gusta Enum. La combinación de ambos es la mejor manera de dispararse en el pie con efectos secundarios incontrolados.

También creo que su problema particular es demasiado específico para ser resuelto por una función genérica de "barajar algo y eso es todo". Intentar encontrar una función independiente del dominio que también solucione el problema específico de su dominio es quizás la razón por la cual su implementación sucesiva se vuelve más fea y compleja en cada intento.

La producción aleatoria de una tabla Hashtable es simple: BatHashtbl.enum |- BatRandom.shuffle |- BatArray.enum. El resto de su código debe referirse al uso de la función decide.