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

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

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

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

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

Источник

4 ответа

Решение

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

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

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

Источник

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

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

Феликс

Источник

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

function (keys, values, reduce) {
    if (reduce)
      return values[Math.floor(Math.random()*values.length)];
    else
      return values;
}
Источник

Подход 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.

Источник

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

Вот распределение варианта 2 (n=1000):

{ 0.2: 233,
  0.9: 767 }

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

{ 0.2: 572,
  0.9: 428 }

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

Источник
Другие вопросы по тегам