Специфическая выборка элементов

[rotoZOOM]

Специфическая выборка элементов

Всем здравствуйте!

Есть задачка, которую пока не могу придумать как решить более рационально с точки зрения
производительности/памяти.

Начальные данные.
Есть список компаний.
Для любого посетителя сайта формируется рандомный порядок вывода этих компаний на экран, и такой порядок остается,
пока посетитель не уйдет с сайта (сессия).
Список выводится постранично.

Собственно задача.
Есть возможность установить спецразмещение для некоторых компаний на определенных позициях в этом списке.
Что это значит?
Пусть есть три компании: А, Б, В.
спецразмещения:
А на место 1 с весом 4
Б на место 1 с весом 6
В на место 3 с весом 1.

Это значит, что на первом месте нужно обязательно выводить А либо Б, причем А с вероятностью 40%, а Б с вероятностью 60%.
На третье место всегда идет В.
Остальные рандом.

Сейчас решаю так (костыль) - считываю все компании в память и выборку веду с помощью PHP.
Это мне простительно, так как компаний пока не больше 150-200, но при росте их числа
начнутся тормоза.
Кэш прикрутить надо, но он идет в последнюю очередь.

Вот собственно сам вопрос: можно ли сделать такого рода выборку средствами мускула, без большого числа запросов?

Спецразмещение можно засунуть, как в таблицу с компаниями (добавить два поля (место, вес)), так и вынести в отдельную таблицу, связав по айдишнику (место, вес, id_компании).

 

[baev]

можно ли сделать такого рода выборку средствами мускула, без большого числа запросов?

— да.
Вот, собственно, сам ответ.

(Тут вопросы ротации банеров соответственно их весам задавались неоднократно. Да и, вообще, задача — «типовая». Тупо забивается число показов пропорционально весу и при каждом показе списывается единица.)

 

[prolis]

Re: Специфическая выборка элементов

Автор оригинала: rotoZOOM
Для любого посетителя сайта формируется рандомный порядок вывода этих компаний на экран, и такой порядок остается,
пока посетитель не уйдет с сайта (сессия).

зачем так усложнять условия. Если всем посетителям задать один рандомный порядок (с учетом приоритетов), вероятность показа их пользователю не изменится.

 

[rotoZOOM]

prolis да, я тоже думал об этом. Но есть условие ТЗ в котором написано, что на каждую сессию необходим свой, рандомный порядок выдачи элементов с учетом спецразмещения, который не меняется в течении всей сессии.
Так получается для 10000 записей - этот порядок надо хранить для каждой сессии.
Сейчас обхожусь генератором псевдослучайных чисел (запоминаю на каждую сессию тока seed).
Но это работает, как я уже говорил, для небольшого числа записей и небольшого числа посетителей.

 

[prolis]

Автор оригинала: rotoZOOM
на каждую сессию необходим свой, рандомный порядок выдачи элементов с учетом спецразмещения, который не меняется в течении всей сессии.

А программист должен читать это так:

на каждую сессию необходим рандомный порядок выдачи элементов с учетом спецразмещения

- от "свойственности" они "рандомнее" не становятся

 

[rotoZOOM]

Не совсем понял, чем различаются эти два предложения, кроме как условия

который не меняется в течении всей сессии.

, которое, безусловно, является важным.

 

[prolis]

исчезло слово "свой" - цель не изменилась, а алгоритм упростился

 

[rotoZOOM]

не понимаю, чем и как упростился?

-~{}~ 22.10.10 15:52:

Если человек зашел на сайт, то у него как выдавалось:
5, 8, 11, 9, 1, 4
Так и должно выдаваться, пока сессия активна.
Закрыл браузер, открыл, зашел на сайт - и у тебя уже другой порядок выдачи.

 

[prolis]

Автор оригинала: rotoZOOM
Если человек зашел на сайт, то у него как выдавалось:
5, 8, 11, 9, 1, 4

должно быть:

Если человек зашел на сайт, то у него как выдавалось:
random(), random(), random(), random(), random(), random()

-так и будет выдаваться последовательность рандомов

 

[rotoZOOM]

или лыжи не едут ....
Что значит каждый random() ?
Любое случайное число?

 

[prolis]

Автор оригинала: rotoZOOM
Что значит каждый random() ?
Любое случайное число?

- ну а с помощью чего ты хотел случайность обеспечивать?

 

[rotoZOOM]

prolis Есть несколько способов. Либо средствами mysql (что очень не рекомендуется и правильно), либо средствами php, что при большом объеме данных и частых выборках тоже не есть хорошо + память. Вот и спрашивал как выкрутится из этой ситуации. Может кто сталкивался и есть стандартный способ. Если нет, будем искать компромисс.

 

[prolis]

Как тебе такой способ:
1. Создаем таблицу table (num,company_id)
2. Заполняем количеством записей, зависимым от веса, на твоем примере: 4 записи компании А, 6 компании Б, 1 компании В. Поле num - порядковый номер записи.
3. Тянем записи для клиента из php:

"... where num in (".rand(0,10).",".rand(0,10).")"

 

[rotoZOOM]

Вес относителен места, на котором необходимо расположить компанию.
Созрел один из вариантов решения.
Если допустить, что существует конечное число случайных выборок, причем не очень большое, например 10.
Тогда мы можем хранить эти выборки в отдельной таблице, типа как (sequence_number, position, company_id), где sequence_number - номер последовательности [0;9], position - позиция внутри конкретной последовательности, ну и company_id - это понятно что такое.
Тогда можно будет генерировать эти последовательности по событию (cron/удаление компании/добавление/изменение спецразмещения), а для конкретной сессии выбирать случайно одну из 10 последовательностей.
Генерировать последовательности с учетом спецразмещения.
Правда надо учесть такой фактор, что последовательность может "неожиданно" измениться во время сессии, но это тоже можно предусмотреть.

 

[prolis]

Автор оригинала: rotoZOOM
Тогда мы можем хранить эти выборки в отдельной таблице, типа как (sequence_number, position, company_id), где sequence_number - номер последовательности [0;9], position - позиция внутри конкретной последовательности, ну и company_id - это понятно что такое.

position зачем хранить, это по ТЗ должна быть случайная величина. В примере выше php возьмет на себя эту генерацию для каждого запроса.

Вес относителен места, на котором необходимо расположить компанию.

- а, это тогда мой косяк. Тогда ещё проще, вместо доп. таблицы добавить одно поле (sequence_number) и в запросе " order by [probability] desc"

 

[rotoZOOM]

position зачем хранить, это по ТЗ должна быть случайная величина.

position как раз и должен генериться для каждой выборки при помощи php.
А нужен он для того, чтобы запрос оканчивался на 'order by `position`' для конкретной sequence.
Нужна не просто случайная выборка, а случайная перестановка, так, чтобы в выборке каждая компания встретилась ровно 1 раз.

 

[prolis]

Для каждого пользователя, обратившемуся к списку нужен следующий запрос:

"select * from table
where sequence_number in (".rand(0,10).",".rand(0,10).")
order by [probability] desc"

Вторая строчка гарантирует, что для каждого пользователя список будет уникальным, а третья, то что если в выборку попадут прокаченные компании - они окажутся сверху.
Для гарантированного незадвоения одной компании в одном списке на php можно простейшей функцией сгенерить массив из уникальных случайных значений от 0 до N и загнать его в запрос.

 

[rotoZOOM]

Не, не прокатит. "Прокаченные" компании, они прокачены для своих мест. То есть например на третье место могут претендовать 2 компании с одинаковой вероятностью, а на первые два ни одной.
И вообще, кто у тебя такой sequence_number ?

 

[prolis]

sequence_number - это ты применил, означает порядкоый номер, для того что бы в php можно было брать записи сразу по номерам строк.
А вот насчет своих мест я сразу не понял. Значит список уж совсем не рандомный, надо подумать