Как загрузить случайный документ из CouchDB (эффективно и честно)?

Я хотел бы загрузить случайный документ из набора документов, хранящихся в базе данных CouchDB. Метод сбора и загрузки документа должен соответствовать следующим требованиям:

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

Каков наилучший способ реализовать это в CouchDB?

Ответ 1

Подумав еще об этом, я придумал решение. Для полноты я сначала продемонстрирую два простых подхода и объясню, почему они ошибочны. Третье решение - это то, с чем я иду.

Подход 1: Пропустить

Это тривиальное решение: у вас есть простой вид (пусть его называют random) с функцией отображения, которая испускает все документы, которые вы хотите выбрать, и встроенную функцию уменьшения _count. Чтобы выбрать случайный документ, выполните следующие действия:

Найдите общее количество документов N в представлении, вызвав:
http://localhost:5984/db/_design/d/_view/random
Выберите случайное число 0 <= i < N
Загрузите i '-й документ:
http://localhost:5984/db/_design/d/_view/random?reduce=false&skip=i&limit=1

Этот подход плохой, потому что он недостаточно масштабируется для большого количества документов. Согласно в этом разделе "CouchDB - окончательное руководство" аргумент пропуска должен использоваться только с одноразрядными значениями.

Вышеприведенное решение должно было бы пройти через документы i, прежде чем возвращать выбранный. В SQL-выражениях это эквивалент полного сканирования таблицы, в отличие от поиска индекса.

Подход 2: случайный номер в документе

При таком подходе во время создания и хранения в документе создается случайное число для каждого документа. Пример документа:

{
  _id: "4f12782c39474fd0a498126c0400708c",
  rand: 0.4591819887660398,
  // actual data...
}

В представлении random есть следующая функция карты:

function(doc) {
  if (doc.rand) {
    emit(doc.rand, doc);
  }
}

Это шаги для выбора случайного документа:

Выберите случайное число 0 <= r < 1
Загрузите документ:
http://localhost:5984/db/_design/d/_view/random?startkey=r&limit=1
Если документ не возвращается (поскольку r больше, чем наибольшее случайное число, хранящееся в базе данных), оберните и загрузите первый документ.

Это очень быстро и отлично выглядит на первый взгляд. Однако есть серьезный недостаток: не все документы имеют одинаковые шансы на выбор.

В самом простом примере в базе данных есть два документа. Когда я выбираю случайный документ очень много раз, я хочу, чтобы каждый документ приходил наполовину. Пусть говорят, что документам были присвоены случайные числа 0,2 и 0,9 во время создания. Таким образом, документ A выбирается, когда (r <= 0.2) or (r > 0.9) и документ B выбирается, когда 0.2 < r <= 0.9. Шанс быть собранным не составляет 50% для каждого документа, но 30% для A и 70% для B.

Вы можете подумать, что ситуация улучшается, когда в базе данных больше документов, но на самом деле этого не происходит. Интервалы между документами становятся меньше, но изменение в размере интервала становится еще хуже: представьте три документа A, B и C со случайными числами 0.30001057, 0.30002057 и 0.30002058 (между другими документами нет других документов). Шансы выбора B выбираются в 1000 раз больше, чем C. В худшем случае двум документам присваивается одинаковое случайное число. Тогда только один из них может быть найден (тот, у которого нижний идентификатор документа), а другой по существу невидим.

Подход 3: комбинация 1 и 2

Решение, которое я придумал, сочетает скорость подхода 2 с справедливостью подхода 1. Вот он:

Как и в подходе 2, каждому документу присваивается случайное число во время создания, для представления используется одна и та же функция карты. Как и в подходе 1, у меня также есть функция уменьшения _count.

Это шаги для загрузки случайного документа:

Найдите общее количество документов N в представлении, вызвав:
http://localhost:5984/db/_design/d/_view/random
Выберите случайное число 0 <= r < 1
Вычислить случайный индекс: i = floor(r*N)
Моя цель - загрузить i -ный документ (как в подходе 1). Предполагая, что распределение случайных чисел более или менее равномерное, я предполагаю, что i -ный документ имеет случайное значение приблизительно r.
Найдите количество документов L со случайным значением ниже r: http://localhost:5984/db/_design/d/_view/random?endkey=r
Посмотрите, насколько далеко мы догадываемся: s = i - L
if (s>=0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=s&limit=1&reduce=false
if (s<0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=-(s+1)&limit=1&descending=true&reduce=false

Итак, фокус в том, чтобы угадать случайное число, присвоенное i -ному документу, посмотреть, как далеко мы вышли, а затем пропустить количество документов, по которым мы пропустили.

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

Если у вас есть лучшее решение, мне было бы очень интересно!

Ответ 2

Если производительность вставки не является проблемой, вы можете попытаться сделать число не случайным, например. сделайте его doc_count + 1 во время создания. Затем вы можете найти его со случайным числом 0 <= r < doc_count. Но это потребовало бы синхронизации создания документов или последовательности, внешней по отношению к couchdb, например. база данных SQL.

С наилучшими пожеланиями

Феликс

Ответ 3

Как насчет "злоупотребления" функцией сокращения вида?

function (keys, values, reduce) {
    if (reduce)
      return values[Math.floor(Math.random()*values.length)];
    else
      return values;
}

Ответ 4

Я согласен с @meliodas:

Здесь распределение опции 2 (n = 1000):

{ 0.2: 233,
  0.9: 767 }

И с заменой startkey/endkey на половину времени:

{ 0.2: 572,
  0.9: 428 }

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

Ответ 5

Подход 2b: порядковый номер в документе

Этот подход аналогичен подходу 2, упомянутому в этом ответе. Этот подход 2 использует случайные числа дважды (один раз в самом документе и один раз в процессе выбора документа). Этот подход 2b будет использовать только случайные числа в процессе выбора и использовать последовательные целые числа в документах. Вот как это работает:

Добавьте последовательные целые числа в ваши документы во время создания:

{
    _id: "4f12782c39474fd0a498126c0400708c",
    int_id : 0,
    // actual data...
}

другой документ

{
    _id: "a498126c0400708c4f12782c39474fd0",
    int_id : 1,
    // actual data...
}

и просто посчитайте по одному с каждым документом.

Представление random имеет ту же функцию карты (хотя вы можете изменить его имя на что-то отличное от "random"):

 function(doc) {
   if (doc.int_id) {
     emit(doc.int_id, doc);
   }
 }

Это шаги для загрузки случайного документа:

Найдите общее количество документов N в представлении по телефону:
http://localhost:5984/db/_design/d/_view/random
Выберите случайное число 0 <= r < 1
Рассчитать случайный индекс: i = floor(r*N)
Загрузите документ:
http://localhost:5984/db/_design/d/_view/random?startkey=i&limit=1

Таким образом, мы выбрали равномерное распределение int_id от 0 до N-1 по дизайну. Затем мы выбираем случайное число (от 0 до N-1) и используем его для этого четного распределения.

Примечание

Этот подход больше не работает, когда документы в середине или в начале удаляются. int_id должен начинаться с 0 и подниматься до N-1.