ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Какой-от не очень рандомный рандом
38 сообщений из 38, показаны все 2 страниц
  все  
Какой-от не очень рандомный рандом
    #38236435
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Стали замечать проблему, что часты коллизии.
Написал функцию по подобию используемой в проекте (в частности диапазон тот же).

Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
        for($j=0; $j<100; $j++)
        {
            $a = array();
            for($i=0; $i < 10000; $i++)
            {
                $rnd =  rand(0x10000,0xfffff);

                if(isset($a[$rnd])) {
                    echo "Collision: {$rnd}\n";
                }
                $a[$rnd] = true;
            }
        }



На локальном компьютере она не дает коллизий даже если использую для теста массивы длиной 10000.
На боевом же сервере коллизии так и прут. В тестовой функции их множество, даже если брать длину массива 1000.

В проекте же вообще берутся случайные числа примерно 1-10 раз в секунду. Причем коллизии как я понял чаще всего возникают в одно и то же время в параллельных скриптах.
Раньше использовали функцию uniqueid но решили от нее отказаться ввиду того что было много коллизий.


Функцию переписал так, но не на много лучше стало:

Код: php
1.
2.
3.
4.
    public static function uniqid()
    {
        return dechex(date('U')) . dechex(rand(0x10000,0xfffff));
    }
...
Рейтинг: 0 / 0
23.04.2013, 12:58
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236447
phpz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
phpz
Гость
Hett,

mt_rand() ?
...
Рейтинг: 0 / 0
23.04.2013, 13:04
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236553
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
На локальном компьютере mt_rand ведет себя значительно хуже. А на сервере я при подобном тесте не ощутил разницы.
...
Рейтинг: 0 / 0
23.04.2013, 13:46
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236581
Фотография r u
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
r u
Участник
Hett,

опишите исходную задачу. зачем вам так часто вызывать рандом?
чего хотите добиться
...
Рейтинг: 0 / 0
23.04.2013, 14:01
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236715
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Есть поток данных, которые записываются в БД (хранится примерно 2кк записей последних сейчас).
Ну записи добавляются постоянно, старые удаляются. Нужен уникальный ключ для записей, да такой, чтобы пользователи не могли на основании его знать сколько данных было добавлено. Собстна использовался uniqueid, но он стал лажать когда поток данных немножко возрос. Переписал вот как выше, по началу вроде лучше стало (хотя может стечение обстоятельств), а потом опять та же картина.

Вообще если так поглядеть на алгоритм, то шансов коллизий должно быть очень мало. Но за день проскакивает таких штук по 10.
...
Рейтинг: 0 / 0
23.04.2013, 15:00
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236783
phpz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
phpz
Гость
Hett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)
...
Рейтинг: 0 / 0
23.04.2013, 15:30
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236821
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
Hett
Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
        for($j=0; $j<100; $j++)
        {
            $a = array();
            for($i=0; $i < 10000; $i++)
            {
                $rnd =  rand(0x10000,0xfffff);

                if(isset($a[$rnd])) {
                    echo "Collision: {$rnd}\n";
                }
                $a[$rnd] = true;
            }
        }


У вас несколько меньше миллиона возможных значений, и вы хотите отсутствия коллизий для десяти тысяч выбранных значений? http://ru.wikipedia.org/wiki/Парадокс_дней_рождения#.D0.9E.D0.B1.D0.BE.D0.B1.D1.89.D0.B5.D0.BD.D0.B8.D1.8F
...
Рейтинг: 0 / 0
23.04.2013, 15:45
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236866
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
Если не осилите статью, можно примерно так прикинуть:
чтобы вероятность коллизий N чисел не превышала p, надо выбирать числа из диапазона N^2/p. Например, хотите чтобы в выборке из 10000 чисел вероятность коллизии была не больше 1% - выбирайте из 10000*10000/0.01 - миллиарда возможных значений.
...
Рейтинг: 0 / 0
23.04.2013, 16:05
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38236972
Фотография SmeL_md
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SmeL_md
Участник
Hett,
У меня была похожая ситуация на 2 разных серверах тогда я генерировал ключ длиной 32 символа от 0 до F.
Ну думал ну как могут быть коллизии :) хотя проверку коллизии делал. Так вот на двух серверах с нагрузкой образно говоря с разницей в 100 раз (почти в одно и тоже время разница месяц). механизм перестал генерировать уникальные ключи, т.е. генерировал то что уже когда то было.
Тогда я поступил так strtoupper(dechex(time())) и конкатенировал с оставшейся длинной ключа.
...
Рейтинг: 0 / 0
23.04.2013, 16:50
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237104
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
?Если не осилите статью, можно примерно так прикинуть:
чтобы вероятность коллизий N чисел не превышала p, надо выбирать числа из диапазона N^2/p. Например, хотите чтобы в выборке из 10000 чисел вероятность коллизии была не больше 1% - выбирайте из 10000*10000/0.01 - миллиарда возможных значений.

Дело в том, что это всего лишь тестовая функция и она не дает коллизий (по крайней мере мне не попались при многократном запуске) на моем локальном копьютере.
А вот на сервере из 100 тестов по 1000 рандомных значений получается примерно 15 коллизий.
В проекте же вообще они получаются из 10 записей и относительно очень часто.
...
Рейтинг: 0 / 0
23.04.2013, 17:51
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237110
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
phpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)

ну да, можно взять еще микротайм+рандом. Просто думал может кто сталкивался с этим и знает еще какие-то решения.
...
Рейтинг: 0 / 0
23.04.2013, 17:52
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237114
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
HettВ проекте же вообще они получаются из 10 записей и относительно очень часто.
Хотя 10 это вообще максимум который бывает очень редко. В среднем там 2-5 записей в секунду.
...
Рейтинг: 0 / 0
23.04.2013, 17:53
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237149
Фотография ScareCrow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ScareCrow
Участник
автор Просто думал может кто сталкивался с этим и знает еще какие-то решения.
GUID?
...
Рейтинг: 0 / 0
23.04.2013, 18:07
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237159
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
HettНа боевом же сервере коллизии так и прут.Гипотеза с потолка - процессор, случаем, не AMD?
...
Рейтинг: 0 / 0
23.04.2013, 18:16
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237167
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
miksoftHettНа боевом же сервере коллизии так и прут.Гипотеза с потолка - процессор, случаем, не AMD?
Два процессора Intel(R) Xeon(R) CPU E3-1270 V2 @ 3.50GHz
...
Рейтинг: 0 / 0
23.04.2013, 18:23
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237222
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Корочи на линуксе (в частносте убунте) такое странное поведение.
Я попробовал на домашнем компе,

Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
$i1 = 0;
for($j=0; $j<100; $j++)
{
    $a = array();
    for($i=0; $i < 10000; $i++)
    {
        $rnd = rand(0x10000,0xfffff);

        if(isset($a[$rnd])) {
//            echo "Collision: {$rnd}<br>";
            $i1++;
        }
        $a[$rnd] = true;
    }
}
echo ($i1 / count($a) * 100);


Показало 0.
А на вритуалке на этом же железе ~50.
...
Рейтинг: 0 / 0
23.04.2013, 19:02
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237428
phpz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
phpz
Гость
Hett,

Я бы этой строке кода сильно не доверял:
Код: php
1.
echo ($i1 / count($a) * 100);
...
Рейтинг: 0 / 0
23.04.2013, 22:58
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237541
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
HettДело в том, что это всего лишь тестовая функция и она не дает коллизий (по крайней мере мне не попались при многократном запуске) на моем локальном копьютере.
А вот на сервере из 100 тестов по 1000 рандомных значений получается примерно 15 коллизий.
В проекте же вообще они получаются из 10 записей и относительно очень часто.На винде тестируете? Ну это как раз на винде random в php не рандомный - выдает фиксированную последовательность из 32768 разных значений, которая потом повторяется по циклу. А для случайных чисел коллизии должны быть.
...
Рейтинг: 0 / 0
24.04.2013, 07:32
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237547
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
В статье на wiki обоснование. На пальцах - десять тысяч чисел - это сто миллионов пар. Сто миллионов раз берете пару случайных значений из одного миллиона возможных и проверяете что они не совпали.
Да, и числа выдаваемые функциями rand, mt_rand и т.п. - в любом случае не случайные :)
...
Рейтинг: 0 / 0
24.04.2013, 07:46
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237563
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
phpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)Если отрезать 5 символов, то на 10000 значений коллизии будут - я вам гарантирую.
...
Рейтинг: 0 / 0
24.04.2013, 08:32
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237566
Фотография r u
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
r u
Участник
HettНужен уникальный ключ для записей, да такой, чтобы пользователи не могли на основании его знать сколько данных было добавлено.
ну и зачем тогда так заморачиваться?
имеем в таблице PK id автоинкремент
на его основе делаем суррогатный ключ равный md5( $id.$SALT )
и непаримся
коллизии почти исключены, юзеры ничего угадать несмогут.
длинноват - но думаю это непроблема
...
Рейтинг: 0 / 0
24.04.2013, 08:34
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237567
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
HettphpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)

ну да, можно взять еще микротайм+рандом. Просто думал может кто сталкивался с этим и знает еще какие-то решения.Вообще-то для гарантированного отсутствия коллизий только одно решение - брать автоинкрементный счетчик. Шифровать его значение. В результатах шифрования ни в коем случае ничего не обрезать!
...
Рейтинг: 0 / 0
24.04.2013, 08:36
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237611
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Я хотел посвятить топик скорее вопросу рандома, придумать другой вариант без коллизий в общем-то не проблема)
...
Рейтинг: 0 / 0
24.04.2013, 09:43
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237613
phpz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
phpz
Гость
?phpzHett,

Ну взять md5(microtime(true)) и отрезать сколько надо. Правда, может будет тормозить :-)Если отрезать 5 символов, то на 10000 значений коллизии будут - я вам гарантирую.
Монстр:
Код: php
1.
$rnd = hexdec(substr(md5(microtime(true).rand()),rand(0,23),8));  // так делать не надо xD


А вообще-то может стОит /dev/urandom заюзать
Код: php
1.
$rand_bytes = mcrypt_create_iv(4, MCRYPT_DEV_URANDOM)
...
Рейтинг: 0 / 0
24.04.2013, 09:44
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237693
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
HettЯ хотел посвятить топик скорее вопросу рандома, придумать другой вариант без коллизий в общем-то не проблема)
Ну тогда еще раз читайте http://ru.wikipedia.org/wiki/Парадокс_дней_рождения и http://ru.wikipedia.org/wiki/Атака_«дней_рождения» до просветления. С выбранными вами диапазонами коллизии обязательно будут.
...
Рейтинг: 0 / 0
24.04.2013, 10:38
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38237912
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
?HettЯ хотел посвятить топик скорее вопросу рандома, придумать другой вариант без коллизий в общем-то не проблема)
Ну тогда еще раз читайте http://ru.wikipedia.org/wiki/Парадокс_дней_рождения и http://ru.wikipedia.org/wiki/Атака_«дней_рождения» до просветления. С выбранными вами диапазонами коллизии обязательно будут.

Будут, да. Но с какой периодичностью? Не 10 раз на дню, с учетом того, что берутся 2-3 записи в среднем в секунду. К тому же там добавляется таймштамп.
...
Рейтинг: 0 / 0
24.04.2013, 12:09
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238127
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
[quot Hett]?пропущено...
К тому же там добавляется таймштамп.Ну тогда у вас проблема в другом месте. http://www.php.net/manual/ru/function.srand.php Там конечно написано, что инициализация генератора происходит автоматически. Но что используется в качестве начального значения, не написано. А используется скорее всего тот же самый time(). Так что если два запроса придут одновременно, в двух параллельных потоках будет одинаково проинициализирован генератор случайных чисел, и вы получите одинаковое значение rand().
...
Рейтинг: 0 / 0
24.04.2013, 13:33
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238210
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Вот!
...
Рейтинг: 0 / 0
24.04.2013, 14:10
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238315
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
HettВот!Что вот? Вы же спросили, почему у вас коллизии в коде из первого сообщения. А что в реальности надо избавиться от коллизий совсем в другом коде, написали где-то мимоходом и сильно позже.
...
Рейтинг: 0 / 0
24.04.2013, 14:47
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238324
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Распределение должно быть равномерным?
...
Рейтинг: 0 / 0
24.04.2013, 14:49
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238354
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
HettРаспределение должно быть равномерным?Распределение чего?
...
Рейтинг: 0 / 0
24.04.2013, 14:59
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238403
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
Возьмите serialize($_SERVER), добавьте getmypid() и microtime(). Получите md5 от всего этого и используйте в качестве уникального идентификатора.
...
Рейтинг: 0 / 0
24.04.2013, 15:22
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238717
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
?HettРаспределение должно быть равномерным?Распределение чего?
Пардон, не нормальным, конечно же, а равномерным. Множества величин полученных в функцией рандом?
...
Рейтинг: 0 / 0
24.04.2013, 17:26
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238719
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
Ну вот, пожалуй надо отдохнуть, ведь изначально я уже правильно сформулировал.
В общем думаю ясно.
...
Рейтинг: 0 / 0
24.04.2013, 17:27
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38238723
Фотография Hett
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hett
Участник
?Там конечно написано, что инициализация генератора происходит автоматически
Да, там написано

авторУстанавливает начальное число генератора случайных чисел в seed или случайное число , если seed не указан.
Я понимаю, что это случайное число не случайно, но каким образом я бы мог сделать его еще случайнее с помощью инициализации srand() если эта инициализация уже проводилась?
...
Рейтинг: 0 / 0
24.04.2013, 17:29
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38239060
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
Hett, вообще-то нужны не случайные, а просто разные числа. Понятно, что какие бы преобразования с одинаковыми исходными данными не делались, результат будет одинаковый. Поэтому нужно найти что-то, что отличается от запроса к запросу. Текущее время это конечно хорошо, но может и совпасть. Можно добавить getmypid() - идентификатор процесса. На линуксе одновременные запросы обычно обрабатываются в разных процессах. Можно посмотреть на параметры самого запроса - с какого адреса и порта пришел: $_SERVER['REMOTE_ADDR'], $_SERVER['REMOTE_PORT']. Вряд ли два запроса одновременно придут с одного адреса и порта. Если в апаче загружен mod_unique_id, в $_SERVER['UNIQUE_ID'] должна быть уникальная строка. Можно в конце концов полезть в /dev/urandom под линуксом или в cryptoapi под виндой.
...
Рейтинг: 0 / 0
24.04.2013, 20:50
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38239155
phpz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
phpz
Гость
?Hett, вообще-то нужны не случайные, а просто разные числа. Понятно, что какие бы преобразования с одинаковыми исходными данными не делались, результат будет одинаковый. Поэтому нужно найти что-то, что отличается от запроса к запросу. Текущее время это конечно хорошо, но может и совпасть. Можно добавить getmypid() - идентификатор процесса. На линуксе одновременные запросы обычно обрабатываются в разных процессах. Можно посмотреть на параметры самого запроса - с какого адреса и порта пришел: $_SERVER['REMOTE_ADDR'], $_SERVER['REMOTE_PORT']. Вряд ли два запроса одновременно придут с одного адреса и порта. Если в апаче загружен mod_unique_id, в $_SERVER['UNIQUE_ID'] должна быть уникальная строка. Можно в конце концов полезть в /dev/urandom под линуксом или в cryptoapi под виндой.
Месье знает толк в извpащениях! (честно не мое xD)
...
Рейтинг: 0 / 0
24.04.2013, 22:32
| Ответить | Цитировать | Написать  
Какой-от не очень рандомный рандом
    #38301185
Фотография SmeL_md
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SmeL_md
Участник
Pseudo-Random vs. True Random оставлю это здесь
...
Рейтинг: 0 / 0
18.06.2013, 11:21
| Ответить | Цитировать | Написать  
38 сообщений из 38, показаны все 2 страниц
  все  
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Какой-от не очень рандомный рандом
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]