Подумав еще немного, я нашел решение.Для полноты картины я сначала покажу два простых подхода и объясню, почему они несовершенны.Третье решение - это то, с которым я собираюсь.
Подход 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=falseif (s<0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=-(s+1)&limit=1&descending=true&reduce=false
Итак, уловка в том, чтобы угадать случайное число, присвоенное i -ому документу, посмотреть его, посмотреть, как далеко мы отошли, а затем пропустить количество документов, по которым мы пропустили.
Количество пропущенных документов должно оставаться небольшим даже для больших баз данных, поскольку точность предположения будет увеличиваться с увеличением количества документов.Я предполагаю, что s остается постоянным при расширении базы данных, но я не пытался и не чувствую себя достаточно квалифицированным, чтобы доказать это теоретически.
Если у вас есть лучшее решение, я бы оченьинтересно!