OCaml中哈希表的随机枚举

Question

很抱歉这个问题很长.我决定首先解释问题的背景,因为我的问题可能有其他解决方案.如果你赶时间,请阅读下面的问题.

(编辑 - 同时我添加了一些解决问题的尝试.第四个有我的最终结论,你可以直接跳到它.)

上下文

我有一个哈希表,大约有20k对(key(i),value(i)).我想生成像这样的随机列表

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

限制是,一旦我选择了键(213)作为列表的第一个元素,并不是所有键都可以跟随它(我有一些其他函数'决定',它可以决定某个键是否可以是下一个键.列表与否).所以,我想选择一个随机的下一个元素并检查它是否合适 - 在上面的例子中选择了key(127).如果该元素被我的'决定'功能拒绝,我想随机选择另一个.但是我不想选择同样被拒绝的因为我知道它会被再次拒绝而且不仅效率低下,如果只有几个键可以成为下一个键,我也会冒风险,需要很长时间直到找到合适的钥匙.注意,可以重复,例如

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

这是可以的,只要'decision'函数接受键(213)作为列表中的下一个.因此,我需要的是一种随机枚举哈希表中的(键,值)对的方法.每当我必须选择一个键时,我创建一个枚举,我通过使用'decision'函数检查每个新元素来消耗(因此,不会发生重复),当我找到一个时,我将它添加到列表中并继续递增列表.问题是我不希望每次哈希表的枚举都相同.我希望它是随机的.(这与我在特定问题中搜索空间的结构有关,这与我的相关性无关.)

我当然可以通过生成随机整数和仅使用列表来实现这一点 - 这就是我目前正在做的事情.但是,由于这是我经常遇到的问题,我想知道是否在某处有一些随机的枚举工具用于哈希表.

问题

哈希表是否有某些随机枚举函数？我知道函数BatHashtbl.enum(电池库),但我认为它总是会给我相同的哈希表相同的枚举(这是正确的吗？).此外,BatHashtbl模块中似乎没有任何类型的东西.我会对类似的东西感兴趣

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

当提供哈希表和一些整数作为随机生成器的种子时,它将给出哈希表的不同随机枚举.有任何想法吗？

谢谢你的帮助!

最好的,Surikator.

第一次尝试

在Niki在评论中提出建议并通过电池库查看更多细节后,我想出了这个

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

哪种类型

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

它使用Fisher-Yates算法进行在O(n)中运行的混洗.它返回一个列表而不是枚举,这很烦人,因为这意味着即使我对使用rand_enum获得的列表的第三个元素感到满意,该函数仍然会计算整个20k元素的随机枚举.哈希表.

最好的,Surikator

第二次尝试

我将模块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

它具有用于随机枚举哈希表的新类型t.这个类型存储我们希望枚举的哈希表,我们将枚举的列表以及一旦我们用完的列表就计算新的枚举列表(来自哈希表)的函数.一旦列表用完,当我们要求哈希表的新随机元素时,类型t会自动放入从哈希表创建的新随机列表.

因此,使用上面的模块,如果我们想要随机枚举一个哈希表,我们只需:

let re = RndHashtblEnum.create ht 1236

使用随机种子1236创建哈希表ht的随机枚举(在此代码中我假设哈希表是在之前定义的)然后我们可以写

let (k,v) = RndHashtblEnum.next re

从随机枚举中获取下一个(k,v)对.

我们可能会问的一个问题是这是否实际上是公平的随机性,因为我在下次需要随机枚举时使用列表的其余部分随机枚举哈希表.嗯,事实并非如此.如果我的哈希表有1000个元素,并且在提取了5个随机元素之后我对结果感到满意,我知道在接下来的995(第二组提取)中,将不会提取这5个元素.所以,这不是公平的随机性.情况更糟.情况很可能是在接下来的1000次提取中(此列表中的995次,下一次枚举列表中的5次)将不会涵盖某些元素.平均而言,该算法是公平的,但它始终不公平.

最好的,Surikator.

第三次尝试

你好,我们又见面了,

包括Niki对使用BatArray.enum的建议以及算法随机部分的根本改变,我提出了一个新的改进版本的RndHashtblEnum模块.建议是:

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

这个新模块消除了将数组传递到列表的(愚蠢)成本,并且在开始时仅使用Fisher-Yates算法 - 因此,从长远来看,我们可以考虑Fisher-Yates位的贡献是O(1).

新版本在随机性方面现在是公平的.这不容易看到,我花了一点时间才意识到这一点.假设哈希表有1000个条目.在新版本中,我们总是使用相同的枚举(enum0 - 在使用"create"函数创建随机枚举时修复).这意味着,当我们试图在最终列表中找到下一个元素时,由于哈希表中的某些键必须满足"决定"功能(否则我们将无法继续算法,我们只会停止),它会在第0和第999条之间的某个地方进行.假设它在条目300上.现在,鉴于我们已经选择了这个密钥,为了确定最终列表中的下一个密钥,我们的枚举将继续使用其余的700个元素,然后将继续使用相同的副本中的下一个300.列举.因此,700 + 300正好在哈希表中生成1000.这意味着我们将始终只考虑哈希表中的每个条目一次.另一件事是,每次我们尝试找到一个键进入列表,标签可以在条目300上找到,但也可以在条目734或其他东西上找到,因为决定函数实际上取决于选择了哪些以前的键这一点在最终名单中.因此,每次我们重新开始寻找哈希表中最终列表的元素时,我们都会从哈希表的随机元素开始.另一件事是,每次我们尝试找到一个键进入列表,标签可以在条目300上找到,但也可以在条目734或其他东西上找到,因为决定函数实际上取决于选择了哪些以前的键这一点在最终名单中.因此,每次我们重新开始寻找哈希表中最终列表的元素时,我们都会从哈希表的随机元素开始.另一件事是,每次我们尝试找到一个键进入列表,标签可以在条目300上找到,但也可以在条目734或其他东西上找到,因为决定函数实际上取决于选择了哪些以前的键这一点在最终名单中.因此,每次我们重新开始寻找哈希表中最终列表的元素时,我们都会从哈希表的随机元素开始.

对不起,如果这不是很清楚.很难解释.=)

感谢所有的评论.

最好的,Surikator.

第四次和最后的尝试 - 这是我提出的解决方案

嗨再来一次,

分享gasche对可变字段和枚举的担忧以及可能来自那里的所有奇怪的副作用,我决定忘记使用可用的哈希表库的现成解决方案,并使用普通列表编写我的东西.我还带来了懒惰,以避免生成随机列表,其中只有部分将被使用(所以有很多有用的懒惰的东西可以按照你的建议使用,Niki).

我创建了这个类型

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

对于列表的惰性随机枚举.每个枚举都是空的(ENil)或不是(ECons),在这种情况下它有三个部分:(1)当前焦点的元素,(2)枚举的其余可用元素,(3)继续的另一个枚举这个枚举.

然后,可以使用该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))

其中remove已定义辅助函数以提取列表的第n个元素并返回一个对(x,ls),其中x是提取的元素,并且ls是没有提取元素的新列表.为了完整起见,我remove也在这里添加了函数的代码.

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

我们现在可以定义非常简单的函数来生成随机枚举的下一个状态,并获取枚举的每个状态中的实际元素.那些是

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

好的,到现在为止,我只是随机列举了一个列表.如果我们想要枚举哈希表,我们可以使用

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

获取哈希表中对的随机枚举,我们可以使用next并获得(键,值)对.该fold但是刚开列表中的所有的(键,值)对哈希表(感谢帕斯卡在这个答案的方式问题).

这结束了整个哈希表枚举的事情.为了完整起见,我还添加了我试图解决的整体问题的解决方案,在上面的"上下文"中进行了解释.如果你还记得,问题是从(1)哈希表中随机生成(键,值)对的列表,以及(2)decide可以判断(键,值)是否可以附加到某个特定的函数的函数对列表.由于整个生成过程可能永远不会终止,为了确保终止,我认为有一个第三个参数是有意义的,这个函数告诉我们是否应该停止该过程(我们应该确保在某些时候返回true)整个过程终止).

功能generate可能是这样的

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

非常感谢所有提供有用评论的人.这真的很有帮助.

一切顺利,Surikator.

Answer 1

鉴于 Hashtbl 暴露的接口，我怀疑是否有这样的功能。显而易见的方法，例如将所有值放入数组中并进行查找，对Array.get a (Random.int (Array.length a))我来说看起来很好。