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

Question

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

(РЕДАКТИРОВАНИЕ - В то же время я добавил несколько попыток решить проблему Четвертый имеет свой окончательный вывод, вы можете перейти прямо к нему.).

КОНТЕКСТА

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

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

let (k,v) = RndHashtblEnum.next re 

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

Один вопрос, который мы можем задать, заключается в том, действительно ли это справедливая случайность, потому что я использую оставшийся список для случайного перечисления хеш-таблицы в следующий раз, когда мне нужно случайное перечисление. Ну, это не так. Если в моей хэш-таблице указано 1000 элементов и после извлечения 5 случайных я удовлетворен результатом, я знаю, что в следующем 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 

Этот новый модуль избавляется от (глупых) затрат передачи массива в список и только использует алгоритм Фишера-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 функция определена для извлечения п-й элемент списка и возвращает пару (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 

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

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

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

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

Answer 1

Сомневаюсь, что существует такая функция, учитывая интерфейс, открытый Hashtbl. Очевидный подход, такой как получение всех значений в массиве и просмотр запросов на Array.get a (Random.int (Array.length a)), выглядит хорошо для меня.

Answer 2

У меня есть два предложения. Во-первых, изменить 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 реализуется как массив, и если вы хотите избежать плохих дубликатов, вы, вероятно, в конечном итоге будете использовать тасование.

Answer 3

Какова плотность потенциала следующего элемента? Какова стоимость вашей функции decide?

Все ваше текущее решение имеет стоимость O (n). Fisher-Yates - O (n) (и не имеет смысла пытаться адаптировать его для Enums, так как это потребует принудительного перечисления), а Array.to_list alos - O (n).

Если ваша функция decide достаточно быстрая, и ваша плотность достаточно низкая, я думаю, что проще всего построить список/массив всех подходящих элементов (вызывая decide для каждого элемента таблицы), затем произвольно выберите один из их.

Если плотность достаточно высокая и decide дорого, думаю, ваша первая идея, выбор ключей наугад и сохранение списка уже встречающихся ключей. Вы сможете выбрать первый подходящий элемент (оптимальное количество звонков decide). Этот способ перечислить последовательность становится дорогостоящим «в конце», когда все элементы уже выбраны, но если ваша плотность высока, вы не столкнетесь с этим случаем.

Если вы не знаете, может быть интересно начать с гипотезы «высокой плотности» и передумать, увидев данную часть стола и ничего не найдя.

И наконец: если вам не нужно добавлять/удалять элементы во время генерации вашей последовательности, было бы интересно преобразовать вашу хеш-таблицу в массив один раз и forall (где-то хранится таблица индексов другого ключа ->), так как все такие проблемы проще, когда индексирование смежно.

Answer 4

Ваши реализации) (второй и третий) слишком сложны. Мне не нравится mutable, и мне не нравится Enum. Сочетание их обоих - лучший способ стрелять в ногу с неконтролируемыми побочными эффектами.

Я также считаю, что ваша конкретная проблема слишком специфична, чтобы ее можно было решить с помощью универсальной функции «перетасовать что-то и что это». Попытка найти такую ​​независимую от домена функцию, которая также решает вашу проблему, связанную с конкретным доменом, может быть, почему ваша последовательная реализация становится более уродливой и сложной при каждой попытке.

Произвольный случайный поток из Hashtable прост: BatHashtbl.enum |- BatRandom.shuffle |- BatArray.enum. Остальная часть вашего кода должна касаться использования функции decide.