Énumération aléatoire d'une table de hachage dans OCaml

Question

Désolé pour la question longue. J'ai décidé d'expliquer d'abord le contexte du problème car il y a peut-être d'autres solutions à mon problème. Si vous êtes pressé, lisez simplement LA QUESTION ci-dessous.

(Edited - Dans le même temps j'ai ajouté quelques tentatives pour résoudre le problème, le quatrième a ma conclusion finale, vous pouvez passer directement à elle..)

LE CONTEXTE

I avoir une table de hachage remplie d'environ 20k paires (clé (i), valeur (i)). Je veux générer des listes aléatoires comme celui-ci

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

La restriction est qu'une fois que je l'ai choisi clé (213) pour être le premier élément de la liste, toutes les touches peuvent suivre (j'ai une autre fonction 'décider' qui peut décider si une clé peut être la suivante dans la liste ou non). Donc, je voudrais choisir un élément suivant aléatoire et vérifier si c'est approprié - dans l'exemple ci-dessus la clé (127) a été choisie. Dans le cas où cet élément est rejeté par ma fonction «décider», j'aimerais en choisir un autre au hasard. Mais je ne voudrais pas choisir la même chose que je viens de rejeter parce que je sais qu'elle sera rejetée à nouveau et non seulement cela serait inefficace, mais aussi le risque, si seulement quelques touches peuvent être les prochaines, de prendre beaucoup de temps jusqu'à ce que je trouve une clé appropriée. Notez qu'il peut être la répétition, comme

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

Ceci est OK, tant que la fonction « décider » accepte la clé (213) comme la suivante dans la liste. Donc, tout ce dont j'ai besoin est un moyen d'énumérer aléatoirement les paires (clé, valeur) dans la table de hachage. Chaque fois que je dois choisir une clé, je crée une énumération, que je consomme en vérifiant chaque nouvel élément avec la fonction 'decide' (donc, pas de répétitions) et quand j'en trouve une, je l'ajoute à la liste et continue d'incrémenter la liste . Le fait est que je ne veux pas que cette énumération de la table de hachage soit la même à chaque fois. Je veux que ce soit aléatoire. (Cela a à voir avec la structure de l'espace de recherche que j'ai dans mon problème particulier qui n'est pas pertinent ici.)

Je peux bien sûr implémenter ceci en générant des entiers aléatoires et en utilisant juste des listes - c'est ce que je suis en train de faire. Mais, comme c'est quelque chose que je rencontre assez souvent, je me demande s'il existe un mécanisme de recensement aléatoire pour les tables de hachage quelque part.

LA QUESTION

Y at-il une fonction d'énumération aléatoire pour les tables de hachage quelque part? Je suis au courant de la fonction BatHashtbl.enum (bibliothèque Batteries) mais je pense qu'elle me donnera toujours la même énumération pour la même table de hachage (est-ce correct?). En outre, il ne semble pas exister quelque chose de ce genre dans ce module BatHashtbl. Je serais intéressé par quelque chose comme

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

qui, lorsqu'elle est munie d'une table de hachage et un entier comme une graine pour le générateur aléatoire, donnera une énumération aléatoire différente de la table de hachage. Des idées?

Merci pour toute aide!

Best, Surikator.

PREMIÈRE TENTATIVE

Après la suggestion de Niki dans les commentaires, et en regardant plus en détail à la bibliothèque Batteries, je suis venu avec cette

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 

qui a le type

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

Il utilise l'algorithme de Fisher-Yates pour le réarrangement qui s'exécute dans O (n). Il renvoie une liste au lieu d'une énumération et cela est assez ennuyeux, car cela signifie que même si je suis content du troisième élément de la liste obtenu avec rand_enum, la fonction va quand même calculer une énumération aléatoire pour l'ensemble des éléments de 20k dans le table de hachage.

Best, Surikator

TENTATIVE DEUXIÈME

I défini comme le module 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 

Il a le nouveau type t pour les énumérations aléatoires de tables de hachage. Ce type stocke la table de hachage que nous souhaitons énumérer, la liste que nous allons énumérer et une fonction pour calculer une nouvelle liste énumérée (à partir de la table de hachage) une fois la liste épuisée. Une fois la liste épuisée, lorsque nous demandons un nouvel élément aléatoire de la table de hachage, le type t place automatiquement une nouvelle liste aléatoire créée à partir de la table de hachage.

Ainsi, en utilisant le module ci-dessus, si nous voulons énumérer une table de hachage au hasard, nous faisons simplement:

let re = RndHashtblEnum.create ht 1236 

pour créer une énumération aléatoire de table de hachage ht avec la graine aléatoire 1236 (Dans ce code I assumer la table de hachage a été définie avant) et nous pouvons alors écrire

let (k,v) = RndHashtblEnum.next re 

pour obtenir la prochaine (k, v) paire de l'énumération aléatoire. Une question que nous pouvons nous poser est de savoir si cela est vraiment aléatoire parce que j'utilise le reste de la liste pour énumérer aléatoirement la table de hachage la prochaine fois que j'ai besoin d'une énumération aléatoire. Eh bien, ce n'est pas. Si ma table de hachage a dit 1000 éléments et après avoir extrait 5 éléments aléatoires je suis satisfait du résultat, je sais que dans le prochain 995 (du second ensemble d'extractions) aucun de ces 5 éléments ne sera extrait. Donc, ce n'est pas juste au hasard. C'est encore pire. Il se peut très bien que dans les 1000 extractions suivantes (995 de cette liste, 5 de la prochaine liste d'énumération) certains éléments ne seront pas couverts. En moyenne, l'algorithme est juste, mais ce n'est pas juste tout le temps.

Best, Surikator.

TENTATIVE TROISIÈME

Salut à nouveau,

Y compris la suggestion de Niki d'utiliser BatArray.enum et un changement fondamental dans la partie stochastique de l'algorithme, je suis venu avec une nouvelle version améliorée du Module RndHashtblEnum.La suggestion est:

(* 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 

Ce nouveau module se débarrasse des coûts (stupides) de passer un tableau à une liste et utilise uniquement l'algorithme Fisher-Yates une fois au début - donc, à long terme, on peut considérer que la contribution du bit Fisher-Yates est O (1).

La nouvelle version est maintenant juste en termes de caractère aléatoire. Ce n'est pas si facile à voir et il m'a fallu un peu de temps pour m'en rendre compte. Supposons que la table de hachage a 1000 entrées. Dans la nouvelle version, nous utilisons toujours la même énumération (enum0 - fixé lorsque nous créons l'énumération aléatoire avec la fonction "create"). Cela signifie que, lorsque nous essayons de trouver l'élément suivant dans notre liste finale, une clé de la table de hachage devra satisfaire la fonction "décider" (sinon nous ne pourrions pas continuer avec l'algorithme et nous arrêterions simplement), il le fera quelque part entre la 0e et la 999e entrée. Supposons que ce soit sur l'entrée 300. Maintenant, étant donné que nous avons choisi cette clé, pour décider de la clé suivante dans la liste finale, notre énumération continuera avec les 700 éléments restants et passera ensuite aux 300 suivants dans la copie de la même énumération. Ainsi, les 700 + 300 font exactement les 1000 dans la table de hachage. Cela signifie que nous considérerons toujours chaque entrée de la table de hachage une seule fois. L'autre chose est que chaque fois que nous essayons de trouver une clé pour aller dans la liste, cette étiquette pourrait être trouvée à l'entrée 300, mais aussi à l'entrée 734 ou autre chose, parce que la fonction décider dépend des clés précédentes choisies jusqu'à ce point dans la liste finale. Ainsi, chaque fois que nous commençons à chercher un élément pour la liste finale dans la table de hachage, nous commençons avec un élément aléatoire de la table de hachage.

Désolé, ce n'est pas très clair. C'est difficile à expliquer. =)

Merci pour tous les commentaires.

Best, Surikator.

QUATRIÈME ET FINALES TENTATIVE - CECI EST MA SOLUTION PROPOSÉE

Salut encore une fois,

soucis de partage GASCHE sur les champs mutables et énumérations en général et tous les étranges effets secondaires qui peuvent provenir de Là, j'ai décidé d'oublier les solutions prêtes à l'emploi en utilisant les bibliothèques de tables de hachage disponibles et j'ai écrit mes trucs en utilisant des listes simples. J'ai aussi apporté la paresse pour éviter de générer des listes aléatoires dont seule une partie serait utilisée (il y avait donc des trucs paresseux utiles à utiliser comme vous l'avez suggéré, Niki).

J'ai créé le type

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

pour les énumérations aléatoires paresseux de listes. Chaque énumération est soit vide (ENil) ou non (ECons) auquel cas elle comporte trois parties: (1) l'élément actuellement en focus, (2) le reste des éléments disponibles à énumérer, (3) une autre énumération pour continuer cette énumération.

Ensuite, une énumération aléatoire d'une liste peut être obtenue en utilisant la fonction create

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)) 

où la fonction remove auxiliaire a été définie pour extraire le n-ième élément de la liste et le retour d'une paire (x,ls) où x est l'élément extrait et ls est la nouvelle liste sans l'élément extrait. Juste pour l'exhaustivité j'ajoute le code de la fonction remove ici aussi.

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 

Nous pouvons maintenant définir des fonctions très simples pour générer l'état suivant de l'énumération aléatoire et pour obtenir l'élément réel dans chaque état de l'énumération. Ce sont

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 

OK, jusqu'à maintenant, j'ai simplement énuméré des listes au hasard. Si nous voulons énumérer une table de hachage à la place, nous pouvons utiliser

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

pour obtenir une énumération aléatoire des paires dans la table de hachage et nous pouvons utiliser ensuite et obtenir pour obtenir les paires (clé, valeur). Le fold mais est juste un moyen d'obtenir toutes les paires (clé, valeur) de la table de hachage dans une liste (merci Pascal pour votre réponse dans ce question).

Ceci termine l'ensemble de l'énumération de tables de hachage. Par souci d'exhaustivité, j'ajoute aussi la solution au problème global que j'essayais de résoudre, expliqué dans "The Context" ci-dessus. Le problème, si vous vous souvenez, est de générer aléatoirement une liste de paires (clé, valeur) de (1) une table de hachage, et (2) une fonction decide qui peut indiquer si une valeur (clé, valeur) peut être ajoutée à liste particulière de paires. Puisque le processus de génération entière peut ne jamais se terminer, pour assurer la terminaison, j'ai pensé qu'il serait logique d'avoir un troisième argument qui est une fonction qui indique si nous devons arrêter le processus ou non (et que nous devrions nous assurer que pour que l'ensemble du processus se termine).

La fonction generate pourrait être quelque chose comme

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 [] 

Merci beaucoup à tous ceux qui ont contribué avec des commentaires utiles. C'était vraiment utile.

Tout le meilleur, Surikator.

Answer 1

Je doute qu'il existe une telle fonction étant donné l'interface exposée par Hashtbl. Approche évidente comme obtenir toutes les valeurs dans un tableau et faire des recherches par Array.get a (Random.int (Array.length a)) me semble bien.

Answer 2

J'ai deux suggestions. La première est de changer votre fonction rand_enum il retourne un Enum.t:

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

qui est pas très différent (il est encore un calcul ENUM aléatoire pour tous 20k), mais est plus proche de ce que vous vouliez à l'origine. Alternativement, vous pouvez toujours prendre le code source de HashTbl et le recompiler avec une fonction rand_enum. Cependant, cela ne sera probablement pas si différent, car un HashTbl est implémenté comme un tableau et si vous voulez éviter les doublons incorrects, vous allez probablement finir par utiliser un shuffle. Quelle est la densité du prochain élément potentiel?

Answer 3

Quel est le coût de votre fonction decide?

Toutes vos solutions actuelles ont un coût O (n). Fisher-Yates est O (n) (et cela n'a pas beaucoup de sens d'essayer de l'adapter pour Enums, car il faudrait forcer l'énumération de toute façon), et Array.to_list alos est O (n).Si votre fonction decide est assez rapide et votre densité assez faible, je pense qu'il peut être plus simple de simplement construire une liste/tableau de tous les éléments éligibles (en appelant decide sur chaque élément de la table), puis choisir au hasard l'un des leur.

Si la densité est assez élevée et decide coûteuse, je pense que votre première idée, en choisissant les clés au hasard et en gardant une liste des clés déjà rencontrées. Vous serez en mesure de choisir le premier élément éligible rencontré (nombre optimal d'appels decide). Cette façon d'énumérer une séquence devient coûteuse "à la fin", quand tous les éléments ont déjà été choisis, mais si votre densité est élevée, vous ne rencontrerez pas ce cas. Si vous ne savez pas, il peut être intéressant de commencer avec l'hypothèse de "haute densité", et de changer d'avis une fois que vous avez vu une partie donnée de la table, et que vous n'avez toujours rien trouvé. Enfin: si vous n'avez pas besoin d'ajouter/supprimer des éléments lors de la génération de votre séquence, il serait intéressant de convertir votre hashtable en tableau une fois pour toutes (en gardant une autre clé -> table d'index de tableau quelque part), car tous ces problèmes sont plus simples lorsque l'indexation est contiguë.

Answer 4

Vos implémentations) (deuxième et troisième) sont trop compliquées. Je n'aime pas mutable et je n'aime pas Enum. Combiner les deux est la meilleure façon de vous tirer dans le pied avec des effets secondaires incontrôlés.

Je pense aussi que votre problème particulier est trop spécifique pour être résolu par une fonction générique de "mélanger quelque chose et c'est tout". Essayer de trouver une telle fonction indépendante du domaine qui résout aussi votre problème spécifique au domaine est peut-être pourquoi votre implémentation successive devient plus laide et plus complexe à chaque tentative.

La production d'un flux aléatoire à partir d'une table de hachage est simple: BatHashtbl.enum |- BatRandom.shuffle |- BatArray.enum. Le reste de votre code devrait concerner l'utilisation de la fonction decide.