Случайное перечисление хеш-таблицы в OCaml

Извините за длинный вопрос. Я решил сначала объяснить контекст проблемы, так как, возможно, есть другие решения моей проблемы. Если вы спешите, просто прочтите ВОПРОС ниже .

(EDITED - тем временем я добавил несколько попыток решить проблему. Четвертый вариант содержит мой окончательный вывод, вы можете сразу перейти к нему.)

КОНТЕКСТ

У меня есть хеш-таблица заполнено примерно 20 тыс. пар (ключ (i), значение (i)). Я хочу сгенерировать случайные списки, подобные этому

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

. Ограничение состоит в том, что после того, как я выбрал ключ (213) в качестве первого элемента списка, не все ключи могут следовать за ним (у меня есть другая функция, которая решает, какая может решить, может ли какой-то ключ быть следующим в списке или нет). Итак, я хотел бы выбрать случайный следующий элемент и проверить, подходит ли он - в приведенном выше примере был выбран ключ (127). В случае, если этот элемент отклоняется моей функцией «решить», я хотел бы случайным образом выбрать другой. Но я бы не хотел выбирать тот же, только что отклоненный, потому что я знаю, что он будет отклонен снова, и это не только будет неэффективно, но я также рискую, если только несколько ключей могут быть следующими, что займет много времени. пока не найду подходящий ключ. Обратите внимание, что может быть повторением, например,

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

Это нормально, пока функция 'решить' принимает клавишу (213) как следующую в списке. Итак, все, что мне нужно, это способ случайным образом перечислить пары (ключ, значение) в хэш-таблице. Всякий раз, когда мне нужно выбрать ключ, я создаю перечисление, которое я использую, проверяя каждый новый элемент с помощью функции 'решить' (так что никаких повторов не происходит), и когда я нахожу один, я добавляю его в список и продолжаю увеличивать список . Дело в том, что я не хочу, чтобы это перечисление хеш-таблицы каждый раз было одинаковым. Я хочу, чтобы это было случайным образом. (Это связано со структурой пространства поиска, которое у меня есть в моей конкретной проблеме, которая здесь не имеет отношения.)

Я, конечно, могу реализовать это, генерируя случайные целые числа и используя только списки - это то, что я сейчас делаю. Но, так как это то, с чем я сталкиваюсь довольно часто, мне интересно, есть ли где-нибудь средство случайного перечисления для хеш-таблиц.

ВОПРОС

Есть ли где-нибудь функция случайного перечисления для хеш-таблиц? Мне известна функция BatHashtbl.enum (библиотека батарей), но я думаю, что она всегда будет давать мне одно и то же перечисление для одной и той же хеш-таблицы (это правильно?). Кроме того, похоже, что в этом модуле BatHashtbl ничего подобного не существует. Я был бы заинтересован в чем-то вроде

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

, который, при наличии хеш-таблицы и некоторого целого числа в качестве начального числа для случайного генератора, даст другое случайное перечисление хеш-таблицы. Есть идеи?

Спасибо за любую помощь!

С уважением,

ВОПРОС

Есть ли где-нибудь функция случайного перечисления для хеш-таблиц? Мне известна функция BatHashtbl.enum (библиотека батарей), но я думаю, что она всегда будет давать мне одно и то же перечисление для одной и той же хеш-таблицы (это правильно?). Кроме того, похоже, что в этом модуле BatHashtbl ничего подобного не существует. Я был бы заинтересован в чем-то вроде

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

, который, при наличии хеш-таблицы и некоторого целого числа в качестве начального числа для случайного генератора, даст другое случайное перечисление хеш-таблицы. Есть идеи?

Спасибо за любую помощь!

С уважением,

ВОПРОС

Есть ли где-нибудь функция случайного перечисления для хеш-таблиц? Мне известна функция BatHashtbl.enum (библиотека батарей), но я думаю, что она всегда будет давать мне одно и то же перечисление для одной и той же хеш-таблицы (это правильно?). Кроме того, похоже, что в этом модуле BatHashtbl ничего подобного не существует. Я был бы заинтересован в чем-то вроде

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

, который, при наличии хеш-таблицы и некоторого целого числа в качестве начального числа для случайного генератора, даст другое случайное перечисление хеш-таблицы. Есть идеи?

Спасибо за любую помощь!

С уважением, похоже, что в этом модуле BatHashtbl ничего подобного не существует. Я был бы заинтересован в чем-то вроде

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

, который, при наличии хеш-таблицы и некоторого целого числа в качестве начального числа для случайного генератора, даст другое случайное перечисление хеш-таблицы. Есть идеи?

Спасибо за любую помощь!

С уважением, похоже, что в этом модуле BatHashtbl ничего подобного не существует. Я был бы заинтересован в чем-то вроде

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

, который, при наличии хеш-таблицы и некоторого целого числа в качестве начального числа для случайного генератора, даст другое случайное перечисление хеш-таблицы. Есть идеи?

Спасибо за любую помощь!

С уважением, Сурикатор.

ПЕРВАЯ ПОПЫТКА

После предложения Ники в комментариях и более подробного просмотра библиотеки батарей я придумал этот

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

. Он использует метод Фишера-Йейтса. алгоритм перетасовки, который выполняется за O (n). Он возвращает список вместо перечисления, и это довольно раздражает, потому что это означает, что даже если я доволен третьим элементом списка, полученным с помощью rand_enum, функция все равно будет вычислять случайное перечисление для всех 20 тыс. Элементов в хэш-таблица.

Лучшее, 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

для создания случайного перечисления хеш-таблицы ht со случайным начальным числом 1236 (в этом коде я предполагаю, что хеш-таблица была определена раньше), а затем мы можем написать

let (k,v) = RndHashtblEnum.next re

, чтобы получить следующий (k, v) пара из случайного перечисления.

Один вопрос, который мы можем задать: действительно ли это справедливая случайность, потому что я использую оставшуюся часть списка для случайного перечисления хэш-таблицы в следующий раз, когда мне понадобится случайное перечисление. Что ж, это не так. Если моя хеш-таблица содержит, скажем, 1000 элементов, и после извлечения 5 случайных элементов я доволен результатом, я знаю, что в следующих 995 (из второго набора извлечений) ни один из этих 5 элементов не будет извлечен. Итак, это не честная случайность. Еще хуже. Вполне может случиться так, что в следующих 1000 извлечений (995 из этого списка, 5 из следующего списка перечисления) некоторые элементы не будут охвачены. В среднем алгоритм справедлив, но не всегда.

Лучшее, Что ж, это не так. Если моя хеш-таблица содержит, скажем, 1000 элементов, и после извлечения 5 случайных элементов я доволен результатом, я знаю, что в следующих 995 (из второго набора извлечений) ни один из этих 5 элементов не будет извлечен. Итак, это не честная случайность. Еще хуже. Вполне может случиться так, что в следующих 1000 извлечений (995 из этого списка, 5 из следующего списка перечисления) некоторые элементы не будут охвачены. В среднем алгоритм справедлив, но не всегда.

Лучшее, Что ж, это не так. Если моя хеш-таблица содержит, скажем, 1000 элементов, и после извлечения 5 случайных элементов я доволен результатом, я знаю, что в следующих 995 (из второго набора извлечений) ни один из этих 5 элементов не будет извлечен. Итак, это не честная случайность. Еще хуже. Вполне может случиться так, что в следующих 1000 извлечений (995 из этого списка, 5 из следующего списка перечисления) некоторые элементы не будут охвачены. В среднем алгоритм справедлив, но не всегда.

Лучшее, Вполне может случиться так, что в следующих 1000 извлечений (995 из этого списка, 5 из следующего списка перечисления) некоторые элементы не будут охвачены. В среднем алгоритм справедлив, но не всегда.

Лучшее, Вполне может случиться так, что в следующих 1000 извлечений (995 из этого списка, 5 из следующего списка перечисления) некоторые элементы не будут охвачены. В среднем алгоритм справедлив, но не всегда.

Лучшее, Сурикатор.

ТРЕТЬЯ ПОПЫТКА

И снова привет,

Включая предложение Ники об использовании 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

Этот новый модуль избавляется от (глупых) затрат на передачу массива в список и использует алгоритм Фишера-Йейтса только один раз в начале, поэтому в долгосрочной перспективе мы можем рассмотреть бит Фишера-Йейтса должен быть O (1).

Новая версия теперь справедлива с точки зрения случайности. Это не так просто увидеть, и мне потребовалось время, чтобы это понять. Предположим, в хеш-таблице 1000 записей. В новой версии мы всегда используем одно и то же перечисление (enum0 - исправлено, когда мы создаем случайное перечисление с помощью функции "create"). Это означает, что, при попытке найти следующий элемент в нашем окончательном списке, поскольку некоторый ключ в хэш-таблице должен будет удовлетворять функции «принятия решения» (иначе мы не смогли бы продолжить работу с алгоритмом и просто остановились бы), он сделает это где-то между 0-й и 999-й записью. Предположим, это запись 300. Теперь, учитывая, что мы выбрали этот ключ, для определения следующего ключа в окончательном списке, наше перечисление продолжится с оставшимися 700 элементами, а затем перейдет к следующим 300 в копии того же самого. перечисление. Итак, 700 + 300 составляют ровно 1000 в хеш-таблице. Это означает, что мы всегда будем рассматривать каждую запись в хеш-таблице один и только один раз. Другое дело, что каждый раз, когда мы пытаемся найти ключ для перехода в список, эта метка может быть найдена в записи 300, а также в записи 734 или в чем-то еще, потому что функция решения фактически зависит от того, какие предыдущие ключи были выбраны до этого момента в окончательном списке. Итак, каждый раз, когда мы начинаем заново искать элемент для окончательного списка в хеш-таблице, мы начинаем со случайного элемента хеш-таблицы.

Извините, если это не очень понятно. Это трудно объяснить. =)

Спасибо за все комментарии.

С уважением, Сурикатор.

ЧЕТВЕРТАЯ И ЗАКЛЮЧИТЕЛЬНАЯ ПОПЫТКА - ЭТО МОЕ ПРЕДЛАГАЕМОЕ РЕШЕНИЕ

И снова привет,

Разделяя беспокойство Гаше по поводу изменяемых полей и перечислений в целом и всех странных побочных эффектов, которые могут возникнуть отсюда, я решил забыть о готовых решениях с использованием доступных библиотек хеш-таблиц и писал свои материалы, используя простые списки. Я также привел лень, чтобы избежать генерации случайных списков, из которых будет использоваться только часть (так что были полезные ленивые вещи, которые можно было использовать, как вы предложили, Ники).

Я создал тип

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 и получить, чтобы получить пары (ключ, значение). свертка , но это всего лишь способ получить все пары (ключ, значение) хеш-таблицы в списке (спасибо Паскалю за ваш ответ в этом вопросе ).

На этом заканчивается вся процедура перечисления хеш-таблицы. Для полноты картины я также добавляю решение общей проблемы, которую я пытался решить, как описано выше в разделе «Контекст». Проблема, если вы помните, состоит в том, чтобы случайным образом сгенерировать список пар (ключ, значение) из (1) хеш-таблицы и (2) функции решения , которая может определить, является ли (ключ, значение) ) можно добавить к определенному списку пар. Поскольку весь процесс генерации никогда не завершится, Для обеспечения завершения я подумал, что имеет смысл иметь третий аргумент, который представляет собой функцию, которая сообщает, должны ли мы останавливать процесс или нет (и которую мы должны убедиться, что в какой-то момент вернет 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 []

Большое спасибо всем, кто внес полезные комментарии. Это было действительно полезно.

Всего наилучшего, Сурикатор.