понедельник, февраля 18, 2008

Синхронизация случайных чисел для клиент-серверных приложений.

Посетила идея. Догадываюсь что она не нова (как раз, возможно, она всплыла из глубоких отложений моего серого хранилища данных), но чтобы не забыть - фиксирую.

Итак, есть задача случайным образом распределять какие-либо данные на клиентских приложениях. При этом должны генерироваться случайные, но одинаковые на всех клиентах числа. Для этого, при инициализации и синхронизации взаимодействия клиентов и сервера, сервер генерирует гамму случайных чисел и шлет ее всем клиентам. Клиенты сохраняют полученную гамму.
Клиенты имеют свои "прозрачные" методы random();, которые выдают случайное число. На самом деле, метод random(); при вызове попросту выбирает каждый последующий элемент из гаммы и возвращает полученное значение. После выборки последнего элемента, указатель перемещается на начало гаммы.

Для "подновления" генерируемых случайностей, можно (а во многих случаях нужно) подгружать новую гамму. При этом, процесс подновления можно легко встроить в протокол обмена данными. Периодически "пристраивая" свежую гамму в ответы сервера на запросы, требующие синхронизации клиентов, можно делать "свежие" вливания в вероятность случайных чисел.

Код класса псевдо-генератора прилагается.

4 комментария:

KOzerog комментирует...

Очень сложно. Проще написать свой рандом и к нему вдобавок метод который позволит установить начальный seed, что-нибудь типа
randomize(value:int = 0) {
if(value)
seed = value;
else
seed = getTimer();
}
А клиентам вначале рассылать соответственно нужный seed.
Исходников генераторов ПС чисел, по инету много.

ЗЫ: по ошибке этот комментарий запостил сначала в блог с кодом.

Racer комментирует...

То-есть написать генератор ПСЧ, который в какой-либо момент синхронизации одновременно на всех клиентах бы выдавал один результат?

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

KOzerog комментирует...

Таймер там для красоты стоит )), вдруг для других целей понадобится, чтобы самому не вводить начальное значение каждый раз. В данной задаче оно конечно нафиг не нужно, оставить только seed = value; Зря поставил, только запутал.
А вообще псевдослучайные числа на то и псевдо, что в отличие от настоящих случайных, у них каждое следующее число зависит от предыдущего. Вообще это недостаток, но в данном случае его можно повернуть себе на пользу )). Короче зная их природу, такой вот вариант напрашивается, дешево и сердито.

Racer комментирует...

Да нет, насчет таймера я всё правильно понял. Приведенный тобою код в нашем применении должен исполняться на сервере при генерации случайного seed, который в дальнейшем рассылается клиентам. Только таймер можно обычным рандомом заменить.

А в остальном - всё отлично.
Только как вычисление ПСЧ может сказаться на производительности? Если много итераций, например. Как всегда - работает закон сохранения энергии :)

Хотя в нашем применении - практически каждая итерация сопровождается синхронизацией, а время на синхронизацию клиентов по-любому значительно больше.