ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Какой-от не очень рандомный рандом
25 сообщений из 38, страница 1 из 2
  1  все
Какой-от не очень рандомный рандом
    #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
| Ответить | Цитировать | Написать  
25 сообщений из 38, страница 1 из 2
  1  все
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Какой-от не очень рандомный рандом
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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