OCaml中哈希表的随机枚举

Question

抱歉问了这么长的问题。我决定首先解释问题的背景，因为我的问题可能还有其他解决方案。如果您赶时间，请阅读下面的问题。

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

上下文

我有一个哈希表，里面装满了大约 20k 对(key(i),value(i))。我想生成这样的随机列表

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

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

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

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

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

问题

某处是否有一些哈希表的随机枚举函数？我知道函数 BatHashtbl.enum(电池库)，但我认为它总会为我提供相同哈希表的相同枚举(这是正确的吗？)。此外，该 BatHashtbl 模块中似乎不存在任何此类内容。我会对类似的东西感兴趣

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

当提供散列表和一些整数作为随机生成器的种子时，将给出散列表的不同随机枚举。有任何想法吗？

谢谢你的帮助!

最好，
苏里卡托。

第一次尝试

在 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 元素计算随机枚举哈希表。

最好，
苏里卡托

第二次尝试

我将模块 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 个)某些元素将不会被覆盖。平均而言，该算法是公平的，但并非一直都公平。

最好，
苏里卡托。

第三次尝试

你好，我们又见面了，

包括 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 或其他东西上找到，因为决定函数实际上取决于之前选择了哪些键最终名单中的那一点。因此，每次我们重新开始寻找哈希表中最终列表的元素时，我们都会从哈希表的随机元素开始。

对不起，如果这不是很清楚。很难解释。 =)

感谢所有的评论。

最好，
苏里卡托。

第四次也是最后一次尝试——这是我建议的解决方案

再次嗨，

分享 gasche 对可变字段和枚举的担忧以及可能来自那里的所有奇怪的副作用，我决定忘记使用可用哈希表库的现成解决方案，并使用普通列表编写我的东西。我还带来了懒惰来处理避免生成仅使用部分的随机列表(因此，按照您的建议，可以使用有用的懒惰的东西，尼基)。

我创建了类型

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 和 get 来获取(键，值)对。 fold 只是获取列表中哈希表的所有 (key,value) 对的一种方式(感谢 Pascal 在 question 中的回答)。

这结束了整个哈希表枚举的事情。为了完整起见，我还添加了我试图解决的整体问题的解决方案，在上面的“上下文”中进行了解释。如果你还记得，问题是从 (1) 一个哈希表和 (2) 一个 decide 函数中随机生成一个 (key, value) 对列表，该函数可以判断一个 (key, value) 是否可以附加到某些特定的对列表。由于整个生成过程可能永远不会终止，为了确保终止，我认为有一个第三个参数是有意义的，它是一个函数，它告诉我们是否应该停止这个过程(并且我们应该确保它在某个时候会返回 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 []

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

一切顺利，
苏里卡托。

Answer 1

我有两个建议。第一个是更改您的 rand_enum 函数，使其返回 Enum.t:

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

这并没有太大的不同(它仍然为所有 20k 计算一个随机枚举)，但更接近你最初想要的。

或者，您始终可以获取 HashTbl 的源代码并使用 rand_enum 函数重新编译它。然而，这也可能不会有什么不同，因为 HashTbl 是作为数组实现的，如果你想避免错误的重复，你可能最终会使用 shuffle。