В последнее время прочитал в сети несколько статей (например эту) где эффективное и элегантное решение достигалось с небольшой помощью теории вероятностей.
Я попытался вспомнить использовал ли я когда нибудь ее для решения своих задач. И да, нашлась одна о которой хотелось бы рассказать.
Допустим, вы пишете сервис знакомств и хотите чтобы результаты поиска основной функции "найди мне вторую половинку" выдавали каждый раз новые результаты. Это естественное требования для сервиса такого рода. Например, мужчина ищет женщину, задает параметры поиска, смотрит на первую страницу результатов, если ему не нравится, листает дальше. В дальнейшем, при последующих заходах на сайт, тоже было бы очень неплохо выдавать ему разные результаты при том же самом запросе.
Это не такая уж большая проблема если у вас есть некое подобие сессии и вы сохраняете метки записей которые были ему показаны и ваша система не очень крупная. С увеличением нагрузки ситуация осложняется - вы уже не можете хранить в сессии такое количество данных или доставать их из какого то хранилища для каждого запроса и\или число запросов становится очень большим и скорость обработки запроса будет уменьшатся и\или каждый посетитель может менять параметры запроса и\иди данные поиска могут меняться и нужно их как-то синхронизовывать - при любых комбинациях этих факторов хранение показанных результатов и их обработка становится головной болью и может резко снизить производительность системы. К тому же, такой подход подразумевает много дополнительного кода.
Почему просто не хранить номер просмотренной страницы? Данные могут храниться в каком то упорядоченном виде (например отсортированными по алфавиту), а нам желательно делать выборку со всего набора.
Формально, мою задачу можно сформулировать следующим образом (это был не сервис знакомств):
Есть большое кол-во данных по которым производится поиск. Поиск производится по нескольким критериям. Эти критерии в общем случае меняются от запроса к запросу. Ранжирование не нужно. Обычное число результатов на каждый вызов - от сотен до десятков тысяч. Результаты должны быть представлены небольшими порциями по 20-50 штук. Полное число данных известно. Непосредственный поиск осуществлялся при помощи Lucene, на каждый подходящий результат из индекса вызывался наш слушатель с передачей ему идентификатора документа.
Основной идеей было произвольно подменять результаты в конечном списке после его предварительно заполнения первыми подходящими данными.
Пусть N - полное число данных (документов);
n - число записей удовлетворяющих параметрам поиска;
h - размер "выходного" списка данных - 20-50 штук.
Тогда вероятность каждой записи из множества n подходящих кандидатов быть представленными в конечно списке есть h/n (h<n). Если бы мы знали n для каждого запроса то можно было бы решить задачу так:
1. Заполнить результирующий список первыми h кандидатами.
2. С каждым новым кандидатом заменить с вероятностью h/n один из h результатов в списке (Как выбрать конкретный элемент для замены обсуждается ниже).
К сожалению, мы не знаем n в процессе поиска. Можно посчитать это число только после того как поисковая машина пробежалась по всему индексу. Возможное решение - запускать поиск два раза - первый раз для подсчета числа n. Но запускать поиск дважды это слишком дорогое удовольствие с точки зрения нагрузки на систему.
Я "пошел другим путем" - число n можно оценивать динамически по текущей статистике результатов. Если мы пробежались по D (из N) записей и имеем d кандидатов то оцениваем n из простой пропорции d/D ~ n/N. n~d*N/D. То есть n динамически меняется во время процесса.
Вероятность каждого нового кандидата быть представленным в конечном списке есть h/n=h*D/(d*N). Если кандидаты начинают попадаться более часто в индексе то оценочное значение n растет быстрее и мы более часто подменяем результаты и наоборот.
Все эти расчеты, конечно, работают идеально только для равномерно распределенных по индексу кандидатах. Если распределение очень неравномерное то и вероятность также будет не идеальной. Для сервиса знакомств это означает что для некоторых людей вероятность оказаться в результатах поиска будет выше/ниже чем у других. Но ошибка в вычислении вероятности велика только поначалу, когда мы прошли лишь небольшую часть индекса. Чем больше мы продвигаемся вперед и накапливаем статистику тем лучше становится оценка n. На практике распределение данных оказалось достаточно хорошим для использования этого метода.
Другой резонный вопрос в этом подходе - как выбрать элемент для замены в конечном списке.
Первая, наивная мысль была выбрать этот элемент произвольным образом генерируя число из диапазона [0, h-1]. Но в этом случае каждый элемент может быть заменен несколько раз, а другие, с большой долью вероятности не заменены ни разу, так как количество замен в среднем это n*h/n=h. Это противоречит всем предыдущим предположениям о вероятностях.
Фактически, если сделать именно так, то подозрительно большая часть в конечном результате будут из первых h результатов.
Хорошим решением данной проблемы оказалось выбирать произвольное число из диапазона [0, h-1] без повторения. В этом случае каждый кандидат будет иметь равные шансы быть замененным. Что если мы уже выбрали все индексы из этого диапазона? Тогда просто начинаем выбирать сначала - это не нарушит нашу логику так как среднее число замен n*h/n=h.
Как выбирать произвольные числа из набора без повторения [0, h-1]? Это одна из широко известных задач с собеседований в компании типа Google и их решение можно легко найти в сети.
Я попытался вспомнить использовал ли я когда нибудь ее для решения своих задач. И да, нашлась одна о которой хотелось бы рассказать.
Допустим, вы пишете сервис знакомств и хотите чтобы результаты поиска основной функции "найди мне вторую половинку" выдавали каждый раз новые результаты. Это естественное требования для сервиса такого рода. Например, мужчина ищет женщину, задает параметры поиска, смотрит на первую страницу результатов, если ему не нравится, листает дальше. В дальнейшем, при последующих заходах на сайт, тоже было бы очень неплохо выдавать ему разные результаты при том же самом запросе.
Это не такая уж большая проблема если у вас есть некое подобие сессии и вы сохраняете метки записей которые были ему показаны и ваша система не очень крупная. С увеличением нагрузки ситуация осложняется - вы уже не можете хранить в сессии такое количество данных или доставать их из какого то хранилища для каждого запроса и\или число запросов становится очень большим и скорость обработки запроса будет уменьшатся и\или каждый посетитель может менять параметры запроса и\иди данные поиска могут меняться и нужно их как-то синхронизовывать - при любых комбинациях этих факторов хранение показанных результатов и их обработка становится головной болью и может резко снизить производительность системы. К тому же, такой подход подразумевает много дополнительного кода.
Почему просто не хранить номер просмотренной страницы? Данные могут храниться в каком то упорядоченном виде (например отсортированными по алфавиту), а нам желательно делать выборку со всего набора.
Формально, мою задачу можно сформулировать следующим образом (это был не сервис знакомств):
Есть большое кол-во данных по которым производится поиск. Поиск производится по нескольким критериям. Эти критерии в общем случае меняются от запроса к запросу. Ранжирование не нужно. Обычное число результатов на каждый вызов - от сотен до десятков тысяч. Результаты должны быть представлены небольшими порциями по 20-50 штук. Полное число данных известно. Непосредственный поиск осуществлялся при помощи Lucene, на каждый подходящий результат из индекса вызывался наш слушатель с передачей ему идентификатора документа.
Основной идеей было произвольно подменять результаты в конечном списке после его предварительно заполнения первыми подходящими данными.
Пусть N - полное число данных (документов);
n - число записей удовлетворяющих параметрам поиска;
h - размер "выходного" списка данных - 20-50 штук.
Тогда вероятность каждой записи из множества n подходящих кандидатов быть представленными в конечно списке есть h/n (h<n). Если бы мы знали n для каждого запроса то можно было бы решить задачу так:
1. Заполнить результирующий список первыми h кандидатами.
2. С каждым новым кандидатом заменить с вероятностью h/n один из h результатов в списке (Как выбрать конкретный элемент для замены обсуждается ниже).
К сожалению, мы не знаем n в процессе поиска. Можно посчитать это число только после того как поисковая машина пробежалась по всему индексу. Возможное решение - запускать поиск два раза - первый раз для подсчета числа n. Но запускать поиск дважды это слишком дорогое удовольствие с точки зрения нагрузки на систему.
Я "пошел другим путем" - число n можно оценивать динамически по текущей статистике результатов. Если мы пробежались по D (из N) записей и имеем d кандидатов то оцениваем n из простой пропорции d/D ~ n/N. n~d*N/D. То есть n динамически меняется во время процесса.
Вероятность каждого нового кандидата быть представленным в конечном списке есть h/n=h*D/(d*N). Если кандидаты начинают попадаться более часто в индексе то оценочное значение n растет быстрее и мы более часто подменяем результаты и наоборот.
Все эти расчеты, конечно, работают идеально только для равномерно распределенных по индексу кандидатах. Если распределение очень неравномерное то и вероятность также будет не идеальной. Для сервиса знакомств это означает что для некоторых людей вероятность оказаться в результатах поиска будет выше/ниже чем у других. Но ошибка в вычислении вероятности велика только поначалу, когда мы прошли лишь небольшую часть индекса. Чем больше мы продвигаемся вперед и накапливаем статистику тем лучше становится оценка n. На практике распределение данных оказалось достаточно хорошим для использования этого метода.
Другой резонный вопрос в этом подходе - как выбрать элемент для замены в конечном списке.
Первая, наивная мысль была выбрать этот элемент произвольным образом генерируя число из диапазона [0, h-1]. Но в этом случае каждый элемент может быть заменен несколько раз, а другие, с большой долью вероятности не заменены ни разу, так как количество замен в среднем это n*h/n=h. Это противоречит всем предыдущим предположениям о вероятностях.
Фактически, если сделать именно так, то подозрительно большая часть в конечном результате будут из первых h результатов.
Хорошим решением данной проблемы оказалось выбирать произвольное число из диапазона [0, h-1] без повторения. В этом случае каждый кандидат будет иметь равные шансы быть замененным. Что если мы уже выбрали все индексы из этого диапазона? Тогда просто начинаем выбирать сначала - это не нарушит нашу логику так как среднее число замен n*h/n=h.
Как выбирать произвольные числа из набора без повторения [0, h-1]? Это одна из широко известных задач с собеседований в компании типа Google и их решение можно легко найти в сети.
Комментариев нет:
Отправить комментарий