Master-X
Форум | Новости | Статьи
Главная » Форум » Программинг, Скрипты, Софт, Сервисы » 
Тема: Алгоритм постоянной случайности
цитата
14/07/12 в 16:20
 Alexandur
Нужен алгоритм постоянного уникального набора случайных символов. Как правильно обозвать не знаю icon_smile.gif

Суть: имеем ключ, допустим 1. Алгоритм генерируют массив из 100 уникальных элементов случайным образом. Что-то вроде shuffle(range(0,99))
При ключе 2 - алгоритм генерирует массив, который сильно отличается от того, что с ключом 1 (т.н. лавинный эффект)
Если снова задать ключ 1 - сгенерируются точно такой же массив, как в первой случае. Т.е. значения распределяются случайным образом, но в жёсткой зависимости от ключа.

Смотрел на хэш-функции, но там возвращается неуникальный набор символов/значений.

Подскажите хотя бы направление, в каком искать. Но лучше готовую функцию icon_cool.gif
цитата
14/07/12 в 16:48
 idk2045
по хорошему надо инициализировать генератор случайных чисел твоим ключом.
однако насколько я знаю в пхп функции типа mt_srand($seed) перестали давать одинаковые последовательности при одинаковом ключе.
поэтому приходится делать это ручками. пока сходу не нашел готового, пойду завтракать, дальше посмотрим icon_smile.gif
цитата
14/07/12 в 18:13
 Yabuti
соленый md5 - не вариант?
вообще я нуб в таких алго, но md5(salt,signature) - первое, что пришло в голову smail54.gif
цитата
14/07/12 в 19:54
 Yacc
gimcnuk писал:
алгоритм постоянного уникального набора случайных символов

Код:
class set {
   public static function create( $keys, $length ) {
      $set = array();
      foreach( $keys as $key )
         for( $i = 0; $i < $length; $i += 1 )
            $set[ $key ][] = uniqid( md5( mt_rand() ) );
      return $set;
   }
}

$set = set::create( array( 'one', 'two' ), 10 );

var_dump( $set );
цитата
14/07/12 в 20:28
 Stek
честно говоря вообще не понял, что необходимо. "постоянная" и "случайность" - это полностью противоположные понятия.

Цитата:
Смотрел на хэш-функции, но там возвращается неуникальный набор символов/значений.

надо очень постараться, что бы получить одинаковые хеши от разных строк.
md5(uniqid().microtime(true)) по идее должен всегда давать разный хеш.
цитата
14/07/12 в 21:36
 idk2045
Yacc: у тебя в основе лежит mt_rand что означает при каждом новом вызове функции будет возвращать разную последовательность.
цитата
14/07/12 в 23:55
 freeek
обычный мд5, пусть с солью, вполне покроет вопрос, даже голову греть не стоит
цитата
14/07/12 в 23:59
 idk2045
freeek писал:
обычный мд5, пусть с солью, вполне покроет вопрос

мд5 32 символа выдает тока, дальше надо мутить еще че-то с ним
цитата
15/07/12 в 01:49
 Yacc
grozny писал:
Yacc: у тебя в основе лежит mt_rand что означает при каждом новом вызове функции будет возвращать разную последовательность.

Зачем новый вызов? Нужен ведь "постоянный уникальный набор". Один раз создал и пользуйся.
цитата
15/07/12 в 03:19
 idk2045
Yacc писал:
Один раз создал и пользуйся.

а, понял.. ну эт как-то некошерно если по-хорошему делать icon_smile.gif
обычно надо при любом вызове скрипта одни и те же данные генерить. удобная фича и часто используемая в более простом виде типа crc32($_SERVER['REQUEST_URI']) для одного уникального значения.
цитата
15/07/12 в 11:29
 Yacc
grozny писал:
как-то некошерно если по-хорошему делать

По-другому никак. icon_smile.gif
цитата
15/07/12 в 11:37
 AWD
gimcnuk писал:
Что-то вроде shuffle(range(0,99))

что-то вроде генерится так:
Код:
mt_srand(crc32($_YOUR_KEY)); //инициализируем мт твоим ключем

for($i=0; $i<100; $i++) //ну, допустим 100 итераций...
  $rnd_arr[] = mt_rand(0, 100); //каждый последующий вызов мт_ранд будет генерить "случайное" число, их последовательность будет постоянна в зависимости от ключа.
хотя так результаты будут не уникальными... icon_rolleyes.gif такое больше юзают, когда надо, например, постоянные "случайные" ссылки выводить на странице из базы... вообщем, гоню. не доперепонял задачу...
цитата
15/07/12 в 11:48
 Alexandur
Всем навешал, но решения пока нет. Абыдно, да icon_sad.gif

Yacc писал:
Один раз создал и пользуйся

Ну, дык, с тем же успехом можно запускать упомянутый shuffle(range(0,99)) и записывать результаты, кэшировать.

Stek писал:
надо очень постараться, что бы получить одинаковые хеши от разных строк

Хэши разные, но символы в них повторяются, а нужен набор неповторяющихся значений.

AWD: алгоритм хороший, только с повторами icon_sad.gif
цитата
15/07/12 в 11:49
 Alexandur
AWD писал:
такое больше юзают, когда надо, например, постоянные "случайные" ссылки выводить на странице из базы...

Ты раскрыл мой план icon_smile.gif
цитата
15/07/12 в 11:55
 AWD
тогда вот, берем то, что написал Yacc:, добавляем инициализацию мт_сранд-а и убиваем уникайди icon_biggrin.gif Код:
class set {
    public static function create( $keys, $length ) {
    $set = array();
    foreach( $keys as $key ) {
      mt_srand(crc32($key));
        for( $i = 0; $i < $length; $i += 1 )
          $set[ $key ][] = md5(mt_rand());
      }
      return $set;
    }
  }

$set = set::create( array( 'one', 'two' ), 10 );

var_dump( $set );
так работает icon_biggrin.gif
или если надо цифры в диапазоне выводить, то вот класс Код:
class set {
  public static function create( $keys, $length ) {
    $set = array();
    foreach( $keys as $key ) {
      $range = range(0, 99); //тут диапазон
      mt_srand(crc32($key));
      for( $i = 0; $i < $length; $i++) {
        $rnd = mt_rand(0, count($range)-1);
        $set[$key][] = $range[$rnd];
        unset($range[$rnd]);
      }
    }
  return $set;
  }
}
цитата
15/07/12 в 17:09
 Yacc
gimcnuk писал:
Ну, дык, с тем же успехом можно запускать упомянутый shuffle(range(0,99)) и записывать результаты, кэшировать.

Нет. Так будет не уникально и не криптостойко.

gimcnuk писал:
решения пока нет

Озвучь задачу как она есть, а не так как ты её видишь, тогда и решение будет.
цитата
15/07/12 в 20:13
 idk2045
AWD писал:
тогда вот, берем то, что написал Yacc:, добавляем инициализацию мт_сранд-а и убиваем уникайди

покурите мануал на сайте пхп, сранд давно уже выдает рандомную последовательность, начиная с какой-то там версии пхп.
цитата
15/07/12 в 20:21
 idk2045
gimcnuk: ладно, вот готовый вариант, все что тут предлагали херня smail101.gif

Код:
function getarray($key, $count, $limit = 10000)
{
   $res = array();
   do
   {
      $res []= (int) (abs(crc32($key)) / 2147483647 * $limit);
      $key = crc32($key);
   } while(count($res) < $count);
   return $res;
}

getarray(1, 50) всегда возвращает одинаковую рандомную последовательность из 50 чисел.
getarray(2, 50) всегда возвращает другую, но постоянную рандомную последовательность.
$limit - максимальный член последовательности, какой тебе нужен.
цитата
16/07/12 в 09:20
 AWD
grozny писал:
покурите мануал на сайте пхп, сранд давно уже выдает рандомную последовательность, начиная с какой-то там версии пхп.
покурил мануал на сайте пхп. Цитата:
При том же параметре последовательность значений будет отличатся от последовательности, сгенерированной в предыдущих версиях PHP
то есть, на пхп 5.2.1 и выше последовательность будет _другой_, нежели на предыдущих версиях, но никак не рандомной.
и вдогонку - задача стояла генерить _неповторяющиеся_ последовательности, а твой код дает повторения... думал двумя строчками отделаться? icon_smile.gif
можно, конечно, сделать проверку in_array Код:
   do
   {
      $tmp = (int) (abs(crc32($key)) / 2147483647 * $limit);
      if(!in_array($tmp, $res))
        $res[] = $tmp;
      $key = crc32($key);
   } while(count($res) < $count);
но нет никакой гарантии, что в один момент все это дело переклинит, ибо начнет генерить повторяющиеся данные... особенно, если лимит 1000, а значений нужно 999 - скорость генерации падает в ~10 раз c ~0,03 до ~0,2сек... ну это так, пример, а вообще, мало-ли, какой сид посеешь, что вообще машину положит, патамушта 48. нет, мало, лучше 49 smail101.gif ... не считаю твой вариант (да и свой) идеальным icon_biggrin.gif
цитата
16/07/12 в 11:05
 Alexandur
Yacc писал:
Нет. Так будет не уникально и не криптостойко.

Криптостойкость совсем не нужна, а вот почему неуникально-то?

Цитата:

Озвучь задачу как она есть, а не так как ты её видишь, тогда и решение будет.

AWD: уже догадался. Имеется н-ное количество страниц. Нужно для каждой страницы генерировать случайный набор неповторяющихся ссылок. Причём при каждом заходе на конкретную страницу, набор должен быть одним и тем же, с неизменным порядком ссылок.

Вариант с кешированием shuffle(range(0,99)) как раз подходит, но не нравится кеширование. Хотелось бы при перетаскивании с сервера на сервер забирать только алгоритм, а не таскать весь кеш. Ну и на разных сереверах чтоб выдавались одни и те же наборы. Как-то так.
цитата
16/07/12 в 15:14
 Yacc
gimcnuk писал:
Криптостойкость совсем не нужна, а вот почему неуникально-то?

Для твоей задачи достаточно уникально:

Код:
function shuffle_by_key( $key, $arr ) {
   srand( $key );
   shuffle( $arr );
   return $arr;
}

$arr = range( 1, 5 );
foreach( range( 1, 2 ) as $key ) {
    var_dump( shuffle_by_key( $key, $arr ) );
    var_dump( shuffle_by_key( $key, $arr ) );
}

icon_smile.gif
цитата
17/07/12 в 21:03
 idk2045
AWD писал:
то есть, на пхп 5.2.1 и выше последовательность будет _другой_, нежели на предыдущих версиях, но никак не рандомной.
и вдогонку - задача стояла генерить _неповторяющиеся_ последовательности, а твой код дает повторения... думал двумя строчками отделаться?

вот жеж бля.. кажется и правда mt_srand работает smail54.gif
а помнится вроде был косяк с этим какой-то... хз может и не в этом дело было
цитата
18/07/12 в 00:32
 Dr.Syshalt
gimcnuk писал:

Вариант с кешированием shuffle(range(0,99)) как раз подходит, но не нравится кеширование. Хотелось бы при перетаскивании с сервера на сервер забирать только алгоритм, а не таскать весь кеш. Ну и на разных сереверах чтоб выдавались одни и те же наборы. Как-то так.


А точно не нужно, чтобы это быстро работало?

А то ж на каждой странице, да при каждом заходе, да много вычислений...
цитата
18/07/12 в 01:57
 idk2045
кстати для схожих задач, когда например для страницы надо выбрать рандомом 100 записей из одной таблицы в БД, иногда полезно физически отсортить таблицу в mysql по рандому, это делается однократно а далее просто селектишь последовательно записи 0-100, 100-200 сразу пачкой.
цитата
18/07/12 в 10:23
 Alexandur
Dr.Syshalt писал:
А точно не нужно, чтобы это быстро работало?

В конечном итоге будет кешироваться вся страница, так что: it's alright, it's ok, it's an odyssee, dr. Mabuse, dr. Mabuse
Стр. 1, 2  >  последняя »


Эта страница в полной версии