Извините за длинный вопрос.Я решил сначала объяснить контекст проблемы, так как, возможно, есть другие решения моей проблемы.Если вы спешите, просто прочитайте ВОПРОС ниже.
(РЕДАКТИРОВАНИЕ - Тем временем я добавил несколько попыток решить проблему. Четвертый завершает мой окончательный вывод, вы можете сразу перейти кит.)
КОНТЕКСТ
У меня есть хеш-таблица, заполненная примерно 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
, которое, когда оно снабжено хеш-таблицей и некоторым целым числом в качестве начального числа для генератора случайных чисел, даст другое случайное перечисление хеш-таблицы.Есть идеи?
Спасибо за любую помощь!
Best, Surikator.
ПЕРВАЯ ПОПЫТКА
После предложения Ники в комментарияхи, просматривая более подробно библиотеку аккумуляторов, я пришел к этому
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, функция все равно вычислит случайное перечисление для целых 20k элементов вхеш-таблица.
Best, 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 из следующего списка перечисления) некоторые элементы не будут охвачены.В среднем алгоритм честен, но не всегда честен.
Best, Surikator.
ТРЕТЬЯ ПОПЫТКА
Привет еще раз,
Включая предложение Ники об использовании 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 или что-то еще, потому что функция выбора фактически зависит от того, какие предыдущие ключи были выбраны доэта точка в окончательном списке.Таким образом, каждый раз, когда мы начинаем заново искать элемент для окончательного списка в хеш-таблице, мы начинаем со случайного элемента хеш-таблицы.
Извините, если это не очень понятно.Это трудно объяснить.=)
Спасибо за все комментарии.
Best, Surikator.
ЧЕТВЕРТАЯ И ЗАКЛЮЧИТЕЛЬНАЯ ПОПЫТКА - ЭТО МОЕ ПРЕДЛАГАЕМОЕ РЕШЕНИЕ
Привет еще раз,
Разделяя беспокойство Гаше по поводу изменчивых полей и перечислений в целом и всех странных побочных эффектов, которые могут возникнуть в результате, я решил забыть о готовых решениях с использованием доступных библиотек хеш-таблиц и написал свои материалы, используя простые списки.Я также добавил лень, чтобы избежать генерации случайных списков, из которых будет использоваться только часть (так что, как вы и предлагали, было полезно использовать ленивый материал).
Я создал тип
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, но это просто способ получить все пары (ключ, значение) хеш-таблицы в списке (спасибо Паскалю за ответ на этот вопрос ).
ThisЗавершает все перечисление хеш-таблицы.Ради полноты я добавляю также решение общей проблемы, которую я пытался решить, объясненной в «Контексте» выше.Проблема, если вы помните, состоит в том, чтобы случайным образом генерировать список пар (ключ, значение) из (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.